"Meta-recursion"

Far too many times during Assignment 1, I found myself wishing I could make just a tiny change to GUIController, knowing that I wasn't allowed to, and getting all hung up on that. I realize that, in the real world, there will certainly be times in which I would have to build something to work with someone else's untouchable piece of code. But the thing that irks me is that the scripts I had to write were needed to make the GUI functional, and yet this piece of framework for the untouchable-and-perfect GUI was not documented in what it was supposed to do. But enough about that assignment, that's long gone.

So I learned something interesting about recursion, by way of happening upon something confusing in my lab. Because I like super-simple examples, imagine the following code:

def add_strings(x:list of str) -> str:
""" Takes a list of strings, and sticks them together.
Recursively.
"""
if len(x) == 2:
return x[0] + x[1]
else:
return stick_together(x)

def stick_together(y: list of str) -> str:
return add_strings(y[:-1]) + y[-1]

Okay, before some of you get mad, let me just say that I chose a simple example for a reason.

For the rest of you: what is going on here? One function calls another, which calls the first one. Could this be, *gasp*, meta-recursion???
Let's break it down. Consider this function:

def add_strings2(x: 'list of str') -> str:
if len(x) == 2:
return x[0] + x[1]
else:
return add_strings2(x[:-1]) + x[-1]

Well that was easy. But see, these two are the same function. The secret is that stick_together is a helper function -- one that contains the recursive call. This was really not obvious to me the first time I encountered it, because the functions were a lot more complicated (after a good deal of thought, we were able to make it into a single function). I can't decide whether there's a good reason to know this or not, but now, it just seems trivial.


Ok another recursion question: when do you NOT want to use it?

Let's use the recursive list-summing function as an example:

def r_sum(nested_num_list):
    tot = 0
    for element in nested_num_list:
        if type(element) == type([]):
            tot += r_sum(element)
        else:
            tot += element
    return tot
[Stolen from this page linked to from the course website]

The obvious answer is that you don't need recursion when a simple for-loop will do. If you know that your input will never be nested, then writing this function is far to complex for what you really need to do (hint: try the builtin sum()).

I can think of another reason, though:

>>> mylist = [0]
>>> mylist += mylist,
>>> mylist
[0, [...]]
>>> mylist[1]
[0, [...]]
>>> mylist[1] is mylist
True

This is a list containing a reference to itself. mylist is [0,mylist]. The sum of these elements has got to be zero, right? Because it contains no non-zero numbers? Well, try it.

>>> r_sum(mylist)

Yeah. This problem is a little too big for recursion. Sorry.


RANDOM SLOGS OF THE WEEK! (explanation here)
The unambitious marking scheme:
C - Average. Probably not worth looking at, unless you want to read all of the slogs.
B - Above Average. One or two neat things. Maybe try it  if you're looking for content on those particular topics.
A - Excellent. Lots on interesting ideas that aren't easy to find elsewhere. Probably worth visiting; I'd expect to find more interesting content here in the future.
D - Below Average. Not reader-friendly. Maybe take a look to make sure you're not making the same mistakes.
F - Fail. Fatally flawed; for example, not having any content. I hope I don't find any of these.

Third Week by VVXiyang Rain

• Well, there's only one post. Strike one.
• The post starts with "OK so this is the first time that I write my slog..." Helpful.
• And it ends with "Hope things will get better." Well, so do I.
• Actually the middle is pretty odd as well, it contains ambiguous statements such as "But sadly I did worst in Class in 108". 
• Seriously though, this is very "I did this today"-style. Like going down a checklist: I did this, then this, then this, etc. Nothing exciting.
• There are no spaces between sentences. Anywhere. Seriously?
• The title. "Third Week". Is that a reference to the fact that he hasn't used it since the third week of the course, the date of the only posting commemorated forever in the url? I mean, I can only hope it's not a Nazi Germany pun. 
• Rating: D-    I've had enough.

Slogging Through 148 by Neil

• Neil brings a very out-of-field approach to computer science. For those of you who are struggling to find interesting things to write about, I bet you could take a few pointers from this guy.
• I like his writing style. :)
• Rating: B+   And a good one at that. This could easily be an A.

CSC148 SLOG by TheCoder

• Not a lot of content (two posts overall)
• TheCoder does a lot of reiterating concepts. However, the author does a good job of being concise and relevant.
• TheCoder does a lot of train-of-thought checklisting, another thing which is generally annoying. Again, the author does a good job of being concise and relevant with it, keeping it in check.
• Rating: C+   I get the impression that this person could write a good blog, but doesn't want to do one on this topic.

CSC and I

• Snazzy! The blog looks good. And that is definitely a plus.
• The content is the most checklist-y I think I've encountered so far. The most reflective comment I can find is "It looks cool".
• A general note: don't say that you hope you will be able to solve a problem -- and then never tell us. The interesting part comes in hearing how the difficult thing was solved.
• Another note: you don't need to tell us that you find something confusing. That's really not interesting or meaningful to read about. But the things is, I'm pretty sure that I've done that myself, here. So I'll leave that as a takeaway for everyone, and try not to hold it against the author.
• The subtitle says that he/she dedicates the blog to keep track of, among other things, "how I overcome every problems [sic]". Typo aside: the blog simply doesn't do that. It talks about lots of problems, but almost no solutions. I disapprove of lying to your readers right at the top of the page. 
• Rating: C-

CSC148 by Angel

• No content. Not even hummingbirds can save you from that.
• Rating: F

If you have questions about my stuff, hate me because I insulted your blog, or just fancy a chat, feel free to comment.

--David

More and more slogs

Morning all!

I'd like to start with a shout-out to spinningmind over at Computer Science Journal for putting in some favourable words for me. Further, he/she discovered my blog while writing a post, which he apparently published the day before I published the page of mine to which he linked. Impressively precocious! Things that this person likes include talking about slogging, linking to other slogs, browsing "a random sample of the SLOGs listed", and actually having interesting content, all of which are quite commendable.

See, I've actually learned something from this person. Like me, spinningmind started by asking themselves a question about slogs: in this case, "what about when I'm writing on a specific topic and want to find out what others have said about it?" I never thought about that. That's an interesting question. I would actually like to be able to tell you what everyone is writing about. That wouldn't be that hard to answer, would it? I'm gonna come back to this one...

Anyways, here's what I'm doing. As outlined here, I'm going to generate a random sample of the slogs to visit. As outlined there, I want to spend my time here writing about slogs, because that's something you should all be interested in; further, talking about the slogs of specific, random other people has got to be socially acceptable, because the profs have more-or-less decreed it so (as they expect us to find slogs to talk about from the listing). Well, it's about time I actually got around to doing any of that. Onward!

I'm going to review random slogs. And I'm going to make this a thing, do it all the time. Just for you guys, of course. I'm not a grader or an expert, so I won't be doing anything fancy. I want to write a few sentences on each. About anything that would make it notable compared to the hundreds of slogs out there, or anything I dislike that you would probably want to fix if you were the author (I'm going to be picky). Finally, I will rank them, so that you all know where they stand, and which ones are most worth your time. I'm hoping to learn what it is that people write about, and what it is that makes good slogs good and bad slogs not-good. And that should be relevant to all of you -- and to me, too.

An unambitious marking scheme:
C - Average. Probably not worth looking at, unless you want to read all of the slogs.
B - Above Average. One or two neat things. Maybe try it  if you're looking for content on those particular topics.
A - Excellent. Lots on interesting ideas that aren't easy to find elsewhere. Probably worth visiting; I'd expect to find more interesting content here in the future.
D - Below Average. Not reader-friendly. Maybe take a look to make sure you're not making the same mistakes.
F - Fail. Fatally flawed; for example, not having any content. I hope I don't find any of these.

What am I waiting for? Break out the script!

AlexT.148Log by Solo.Player.

• Short entries (unsure whether or not this is a good thing).
• A focus on class content, lots of suggestions on how to get more comfortable with it. 
• Lots of records of personal thoughts, like a train-of-thought to-do list; reads a bit like a diary. 
• Changed font for his most recent entry for no apparent reason (try to keep it consistent).
• Rating: C+

CSC148H Slog by B

• Draws really cool correlations between course concepts and philosophical concepts.
• The first post in particular presents some legitimately interesting ideas that have enough depth to them that he probably could have written much much more on the subject had he chosen to flesh it out.
• Received a poorly-thought-out TA comment on that post, recommending that he write posts with fewer tangents rather than more ideas. B seems to have taken that to heart, the posts get shorter and shorter, with the most recent being only a single paragraph. I personally am of the viewpoint that sufficiently interesting tangents are nothing but bonus material.
• The blog is made up of well-structured paragraphs. Given this, I'm surprised that B even managed to write something that "do not aid this goal", as the TA said. Maybe pay a little more attention here.
• The text is a little content-dense for a blog (long sentences, little to no filler). I'd recommend splitting up paragraphs into smaller pieces.
• Rating: A-     --I'll be checking back.

CSC148 sLOG by godough

• A single paragraph of content. Huh.
• At least, a straightforward, clean writing style.
• The paragraph is far too big, longer than any I've written here. He could have at least pretended to have more.
• Rating: D

CSC148 Winter sLOG by Tailong He

• Really short entries. Honestly, that's neither good nor bad.
• Talks about his labs.
• Reads like a checklist. Today he did A, B, C. Last week, D, E, and F. Nothing too exciting.
• Rating: C

cantkeepcalmandcarryoncuzimaprogrammer

• "Nothing Found". Oh dear. I guess he/she really can't carry on. Classy.
• Rating: F

That's all for today, folks. I'd love to hear from you in the comments :)

--David

SLOGs (bonus: urllib tutorial)

Alright. I'm gonna maybe rant a bit, but I've got some good stuff for you guys, I promise. (I suppose you can just skip down if you really must...)

This course is challenging us to do exactly what I'm doing here, to blog about our experience with the course. And exactly that: we're not here to blog about computer science, as we're not qualified. We're here to write about what we are qualified to write about. And so while we happily go about ourselves, writing about our own personal experiences with our own personal introductions to the world, at some point it occurs to us that the introductory-computer-science-experience blog is kinda niche, as far as blogs go. Who reads stuff like that? (Who's my audience? I care about that.) People who've always wondered what it's like to take a computer science course, but never have? Or maybe people who are currently taking an introductory computer science course, and are looking for emotional validation?

But wait -- there's more! Have you seen this page? Man, there are a heck of a lot of people blogging about the exact same thing as me. Surely there can't possibly be enough people interested in these that they'll all get read...

Oh, right. "...your peers in this course will read your journal, and compare your experience to theirs". Okay. So you guys are pretty much all sloggers, just like me. I can deal with that. Sweet.

Wait. We're supposed to find other slogs... by using the list of slogs. So we're going to anonymously refer to each others' expositions of emotional validation. That sounds awkward. No, it can't be, that's the idea. Right?

Alright. New question. I don't want to read all the slogs. There are far, far too many. But how do I pick? You know, I have a strong, strong suspicion that the most referenced slogs will be the ones at the top of the [alphabetical] list. Let me do a quick check... none of the top four have comments. Hmmm... Okay, maybe the ones with clever names will be popular.. checking... nope, I guess that isn't true either. Alrighty, or maybe there just isn't a lot of commenting going on (so maybe those sites are actually the most visited, but I don't know how to check that). I hear procrastinating is a thing.

Well, never fear! Now I know my audience! You're all looking for slogs to comment on! Aha! Aren't I clever?

No, seriously, let's give you some. But no bias. I'm not going to just pick the ones at the top. Every so often I'm going to go through that giant list, pick a few at random, then evaluate them. That sounds a bit tedious... so let's automate it.

import urllib.request

Now, as you already know, I'm not an expert on this, and I'm going to cheat a bit maybe, but I want to show you that python can indeed access webpages. This is how you can do it. This works.

slogsite = "http://www.cdf.toronto.edu/~heap/148/W14/slog.html"
x = urllib.request.urlopen(slogsite)
lines = x.readlines()

And there you have it. Now you have the information you need.
You'll notice that the elements of lines are of type 'bytes'. Now, there's probably a good way to deal with that in python, but let's not go in deeper than we have to.

lines = [str(i) for i in lines]

After some careful inspection, I see that the slog urls start on the line containing "The SLOGs (courSe bLOGs) below are by students in Winter 2014 CSC148". Also, there are exactly two lines after the last url.

for i in range(len(lines)):
    if "The SLOGs (courSe bLOGs) below" in lines[i]:
        place = i
        break

lines = lines[place:-2]

Now, I really only want the urls. Again, I'm sure there's a really good way to do this. But hey, who doesn't love the good old brute-force method?

urls = ()

for line in lines:
    start = line.index("href=")
    end = line.index(">http")
    urls += line[start + 6: end - 1],

Beautiful, isn't it? Not really. But at least it works. At least until the instructors decide to reformat their website. (But they made the site automatedly, right? I mean, surely they didn't ask a grad student to type in all 518 or so urls...) 
And finally, the random part.

import random

You know the drill. However, for my own nefarious purposes, I want some user-specified number of urls, not just one. So I'll ask.

k = input("How many urls would you like?\nEnter the number '0', or a natural number between 1 and {}, please. ".format(str(len(lines))))

Now I use the randomness. Also, error-checking. 

try:
    random_urls = random.sample(urls,int(k))
    
except ValueError:
    print("http://en.wikipedia.org/wiki/Natural_number")
    random_urls = []

And now I print.

for i in random_urls:
    print(i)

And there you go. Running it gives you one or more slog urls, all ready for copy-pasting into your browser.

Man, I have more to say on the subject still. Like, you know, actually looking at some of these slogs, and talking about them. I will soon, I promise. But I've written a ton, and the code snippet inserts make it look even longer. Next time ;)

Thanks for bearing with me. If you have a comment, please please please comment. Alternatively, if you really are looking for emotional validation, I suppose I can try to help with that, too.

-- David

Automated Testing

So obviously testing is an integral part of program development. Code doesn't work on the first time. Us coders screw up. Because despite all of the behind-the-scenes shortcuts and my obviously-beautiful writing style and everything else that's done to keep it all easy to understand and intuitive, sometimes it's just not intuitive enough. But I digress.

The problem is: how do I make sure that my program does what I think it should do? The answer, equally simple: try it. The obvious, naive way to do this is to take on the role of the user, and literally try it. And this is where automated testing comes in -- there will come some point where program complexity gets high enough that writing more code to test your main code is simpler than the alternative of doing it manually (for, you know, the same reason that some tasks get so finicky or repetitive that the time and effort spent writing the program is easier to put in than would be required to do it manually). I can imagine there being a trade-off, though; here's a list of things to possibly  consider:

• The obvious one: if the testing process is very short, you probably don't need automated testing. When the time required to write a thorough test is trivial compared to the time required to automate testing, I cannot see myself doing that automation without a good reason.

• If the testing process will have to be repeated many times, that's a point for automation. Imagine a project where functionality will be added incrementally: the older functions would have to be tested when they are first created, and then again whenever a change was made to ensure nothing had been broken. In this case, I can see automated testing being helpful over time.

• If a test requires a lot of iteration, or requires a lot of time to run, then I would probably choose to automate testing. But that's the main criteria I'd consider when deciding whether or not to automate anything, hm?

• If automated testing requires the usage of the same code as your actual program, then that testing is probably not doing much. Imagine the ersatz example program:
  
  x = [1, 2, 3]
  
  And the associated test snippet:
  
  def test_correct_value(self):    self.assertEqual(x, [1, 2, 3])
  
  Why are you even doing this? The clarity is already in your code; you can read it and feel confident you haven't misinterpreted it. In fact, you actually demonstrated that particular skill while writing the test case. Back to the premise, automated testing is useful when intuitive understanding is difficult. Here, it's not accomplishing anything.

• Finally, I can imagine some scenarios where your program is designed to solve some problem that you don't already know the answer to, to optimize something, for example. You would have to test the component functions, of course; for those I could decide how to test based on other criteria (though at this point I think the complexity has probably reached that threshold). But how to test your whole program, when you don't actually know what the output should be? Again, you can test your program for runtime errors and incorrectly-formatted output, but did it give you the right answer?

• At some point, you will have to just run your program and see what it gives you. It is possible to catch bugs -- I've done it -- that show answers that could technically be correct, but are suspicious-looking enough to catch your attention (for example, imagine this optimization program as a chess engine: what if it turns out that the program will only ever move knights?) Sometimes, stupid-answers will be your only chance to catch a bug in a complex program, and it's hard to imagine automated testing clever enough to catch all of them. Other times, at some level, you'll just have to trust that you've done your best, that you've evaluated every case you can, and hopefully you won't have missed anything.