Tall, Dark, and Mysterious

4/13/2005

In Which Our Protagonist Learns The Importance Of The Base Case

File under: When We Were Young, Queen of Sciences. Posted by Moebius Stripper at 6:35 pm.

Mike, by way of Michele, shares 25 of his favourite memories from Sesame Street, which reminds me of the time Big Bird made me cry.

I was three years old. By this point in my life, the residents of Sesame Street had educated me about as well as any community of puppets could reasonably be expected to educate any small child. Family legend has my father holding me, age fifteen months, as he selected an ice cream treat from the Dickie Dee vendor outside our Virginia home. I don’t know if I recognized the varieties of snacks, but apparently I could make some sense of their names. “I,” I enunciated, pointing. “C. E. C…”

Incredulous, my father informed my mother, “She knows letters.” Since neither of them had thought to teach me the alphabet by that point, Cookie Monster and his friends were quickly credited with this development. I soon learned the rest of the alphabet with the aid of refrigerator magnets and blocks. A few months later, I was reading.

With the alphabet under my belt, I turned my attention to the Count’s endless enumeration of everything under the sun, and within less than a year I could rattle off the integers from one to two hundred in sequence. Two hundred exactly, by the way, and no further. Why I knew that one hundred and one came right after one hundred but was unable to extrapolate any further I have no idea, but my parents had good reason for not furnishing that connection: so proud was I of my ability to count to two hundred that I would count to two hundred on the telephone, to my grandparents, every single time they called. Long distance. And this was back in the olden days when long distance cost an arm and a leg, so when it became clear that I was not to tire of my long distance counts to two hundred, my mother gently pointed out that maybe my grandparents didn’t want to hear me count to two hundred over the phone anymore. I threw a fit; didn’t they love me? By the way, Mom and Dad, I stand by that tantrum, because what the hell is the point of grandparents if not to have someone to listen to - and enjoy listening to - some two-and-a-half-year-old kid count to two hundred over the phone, even if it’s costing them fifty cents a minute to hear it?

Anyway, my point here is, by the time I was three I already knew how to read and how to count, so I guess I was old enough to learn computer science - specifically, recursion - and fortunately, Big Bird was on hand to teach me.

Big Bird was painting a bench. He’d just finished applying the last coat of paint, and his friends were admiring his handiwork. As he replaced the paint brush, he explained - concerned citizen that he was - that it was necessary to warn any passers-by that this was a freshly-painted bench. This made sense to me, because I remembered a previous episode in which whatshisface, the mime, sat down on a freshly-painted bench and got white stripes all over his black suit. Big Bird would have none of that, so he produced a blank piece of paper and wrote WET PAINT on it, and hung it by the bench. His only writing implements, however, were the paint and paintbrush he’d brought with him, so after creating the WET PAINT sign he realized that the sign itself contained wet paint, and so he needed to create another WET PAINT sign, to warn people about the first sign. So he created the second sign, and - apparently having learned nothing from his experience with the first sign - realized that he’d need a new one.

I watched this intently, and suddenly it dawned on me: every WET PAINT sign demanded another. I got it, but Big Bird didn’t. I got worried; would he be doing this forever? Or would someone give him a crayon and tell him to use it for the next sign?

Soon the scene ended, and I distractedly watched for the next few minutes as the mime explained the WALK/DON’T WALK signs, and as the Count showed that it doesn’t matter how you arrange the blocks because you still have the same number of them, and as someone didn’t want to share his cookie with Cookie Monster until Kermit came by to teach a lesson about sharing. Whatever. I didn’t care, because I was concerned that Big Bird was still making WET PAINT signs.

Cut to the next scene: Big Bird surrounded by hundreds - maybe even two hundred - WET PAINT signs, happily making another one because the last one was still wet. And no one handed him a damned crayon, and the episode ended right there.

I burst into tears.

My mother, startled (her toddler was bawling at the end of Sesame Street, after all), hurried into the family room and asked me what was wrong, and I blubbered something about the endless production of WET PAINT signs and how Big Bird would be making them forever because each sign told him to make another one. FOREVER. I couldn’t think of anything worse than spending one’s entire life making WET PAINT signs, and I worried that that was to be Big Bird’s fate. It troubled me more than I could put into words. That happy yellow bird, doing this for the rest of his life. And he showed such promise! Would he never get to have a family? go to the park again? And what of Snuffleuppagus?

Mom obviously hadn’t been expecting this, but she quickly assured me that no, Big Bird wasn’t going to spend his whole life making WET PAINT signs. As a matter of fact, he stopped soon after that episode of Sesame Street ended. Because, uh, Grover told him he didn’t have to make the signs anymore. In fact, just you wait, honey, tomorrow on Sesame Street Big Bird will be doing something completely different.

Will he really? I sniffled.

Yes, honey, he will. I promise.

How do you know?

Because, said Mom, I know all of the people on Sesame Street and they told me what they were going to be doing tomorrow.

And you know, I may have known how to read and count to two hundred, and I may have known all sorts of shapes - not just the easy ones like circle and square and triangle, but also trapezoid and pentagon and parallellogram - by the time I was three, but let me tell you, I ate that shit right up. Okay, cool. Big Bird wouldn’t be making WET PAINT signs forever. Mom said so herself. I could sleep at night.

The next day, I saw that Mom had been right, because there on TV was Big Bird singing a song about cooperation and there were no WET PAINT signs anywhere in sight. Good old Grover. Mom knew everything, apparently.

It wasn’t until several years later that I learned that the sort of structure displayed by the self-producing WET PAINT signs - a set of instructions that includes the instruction to follow itself - had a name: recursion. During my first year of university, some boring CS prof whose name I forget explained this all in the most monotonous way imaginable, and told us that if we wrote a recursive function then it would call itself until it had a good reason not to, that is, a base case that ensured it would stop, infinite loops are bad, yadda yadda, blah blah.

And all I could think of was a computer that would be making WET PAINT signs forever and ever because there was no IF CRAYON branch to lead into a ALL SIGNS ARE DRY base case.

It still bothered me, a decade and a half later, and I took pains to ensure that all of my recursive functions would terminate in good time.

That was Sesame Street’s contribution to computer science. Its contribution to real analysis, unfortunately, had not been subjected to peer review: I remember the Count arranging ten blocks in a row, in a pyramid, in a square, informing us that no matter how you placed them, they’d add up to the same number.

Sure, Count. With a series that converges absolutely.

33 Comments

  1. That’s great. I quoted you in my livejournal.
    You’re my hero :)

    - rosona — 4/13/2005 @ 7:52 pm

  2. Wow. Someone else who was proud of their ability to count to two hundred exactly. Cool.

    - Dr. Matt — 4/13/2005 @ 8:27 pm

  3. While a bit older at the time, I suppose, I recall being very proud of being able to count to six hundred. Oddly enough howerver, I thought that “hundred” and “one hundred” were two totally different numbers, and so I would always count that set of a hundred integers twice.

    I’ve never really been sure where I got that idea from.

    - Simon — 4/13/2005 @ 9:18 pm

  4. Rosona - no link? ;)

    And, wow, now that I think about it, no wonder it’s so challenging figuring out how best to educate young children. Who can imagine what could be going on in their heads?

    - Moebius Stripper — 4/13/2005 @ 9:34 pm

  5. Awesome. I know that Sesame Street occasionally disturbed me when I was little, but I no longer remember what exactly. I’ll have to ask my parents what they remember.

    - Alison — 4/13/2005 @ 11:08 pm

  6. I oppose Turing complete languages. Epigram is an experimental language where all recursion must be provably well-founded.

    - r6 — 4/14/2005 @ 12:38 am

  7. Recursion for Dummies

    My mother is an accountant. In the process of becoming an accountant, my mother learned to divide the world into two kinds of people: People who get debits and credits, and people who don’t. You can simplify this to: People…

    - Ilyka Damen — 4/14/2005 @ 1:36 am

  8. My dad would have told me that eventually Big Bird got distracted, the paint on the last WET PAINT sign dried while he was distracted, and thus the recursion ended. But I was more into the groovy, groovy Electric Company and 3-2-1 Contact when I was little. The Electric Company taught me the word “trampoline”.

    Of course, I once explained to a 4-yr-old kid that Red Rover was just like a Range Rover, except that it was red.

    I haven’t had much chance to argue with Maureen yet, other than to tell her that X isn’t Y, it’s X, and besides the alphabet can’t have two Ys because we’d get all confused. She still doesn’t listen to me. Now she spends her free time singing the alphabet song over and over. And in the song she says X, but when I show her an X, she insists it’s a Y. Or maybe she’s asking me “Why?” It’s so hard to tell.

    - meep — 4/14/2005 @ 3:35 am

  9. I guess it is my engineering instinct, but I was waiting for mom to mention that eventually big bird would run out of paint.

    RE: Who can imagine what could be going on in their heads?

    Well, it is an art, but not that difficult to learn. A friend of mine, commenting on an Iron gate my dad had just put up said “I hope you bolted that to the house really well.” To which my dad said “Oh, it’s not that heavy.” My friends response was “Not because it’s heavy, but because the kids will be riding it across the driveway.”

    Not ten minutes later when my kids came down the street and saw the new gate they immediately jumped on for a test drive. Astounded, my dad asked “How the $%^W did you know?” My friends response was “Because if I was a kid, that’s what I would do. I know what kids like, after all I was one once!”

    I suggest that many adults are already halfway to the goal of thinking like a kid — they already believe anything others tell them.

    - AK — 4/14/2005 @ 8:58 am

  10. Rosona - no link? ;)

    Ah, I tend to friends-lock my journal just by reflex. I can make that entry public; nothing incriminating in it(ok it’s public now):

    http://www.livejournal.com/users/pixie_of_spite/109282.html

    There have been two comments left so far.

    If you ever develop a livejournal or a like for reading others livejournals, let me know and I’ll friend you. I’ve got some good math rants sometimes.

    - rosona — 4/14/2005 @ 9:44 am

  11. *clap, clap, clap*

    that was awesome. now i’m off to find a similarly evocative Sesame-Street-based metaphor to use in my physics classes…

    - dr. dave — 4/14/2005 @ 1:32 pm

  12. This is the most charming blog entry I’ve ever read. I hope you don’t mind if I tell students your story in my lower-division CS classes.

    - Jonathan — 4/14/2005 @ 3:45 pm

  13. Jonathan - not at all, go for it. Glad I could be of assistance ;)

    r6 - remind me what a Turing complete language is? I’m sure I knew at some point, but as I was not taught this by Sesame Street, the lesson didn’t stick.

    - Moebius Stripper — 4/14/2005 @ 4:04 pm

  14. I really don’t have much to add, except this story really brightened my day. Thanks.

    - Independent George — 4/14/2005 @ 4:43 pm

  15. Ok, I lied. When I was little (I don’t recall the exact age), I thought that the number after 199 was 1000.

    - Independent George — 4/14/2005 @ 4:44 pm

  16. That kind of reminds me of how when I was little, I thought that when my mother had another baby, she’d be a grandmother.

    - Moebius Stripper — 4/14/2005 @ 4:47 pm

  17. A Turing-complete language is a programming language that is equivalent in computational power to a Universal Turing Machine. A ‘problem’ with Turing-complete languages is that it is possible to write programs that do not terminate: like Big Bird, programs can loop forever. On the other hand, programs written in a language like Epigram *must* halt; any use of recursion must be well-founded (and a compiler can check this). Epigram isn’t as ‘powerful’ as a Turing-complete language, but its advocates believe that most solutions to practical problems can be written in Epigram anyway.

    I must confess that my knowledge of Epigram is based on 15 minutes of Googling, so I’m almost certainly missing some of the finer points of the Epigram vs. Turing-Complete languages debate. I think the basic details are correct, though… r6 can correct me if I’m wrong

    - Nitish — 4/14/2005 @ 6:01 pm

  18. Btw, wasn’t the precalculus exam today? How did it go…or will you not know until you begin grading?

    - Nitish — 4/14/2005 @ 8:28 pm

  19. Nitish: You are correct. Note that a Turing Machine happens to be exactly as powerful as a number of other models of computation we’ve thought of. I actually believe that Turing Machines are a terrible way to teach decidability, because they’re terribly unintuitive to reason about; there are many easier formulations. I think, for instance, that Random Access Machines are easier to reason about.

    The Church-Turing thesis says that any mechanical device is only as powerful as a Turing machine. As my prof for Theoretical Aspects of CS put it, this thesis is just religion; it’s not a statement that you can prove.

    I do tend to be skeptical of languages where you have to prove that your program always terminates. a) non-termination doesn’t seem to me to be close to a significant source of program errors in general (of course, termination is required if you want to get total correctness rather than partial correctness); and b) current techniques for proving that programs terminate still require a lot of work for showing that relatively simple programs terminate; I’ve been to more than one talk about termination analysis this year…

    - plam — 4/14/2005 @ 8:49 pm

  20. The nice thing about a turing machine, compared to (say) a random-access machine, is that the infinite state space is nicely encapsulated in a way that’s easy to wrap your brain around. You can move the tape as far as you want in either direction, but the non-tape state is always one of finitely many known states. With a random-access machine you’d need to be able to access the entire (infinite) memory space, which means you need to be able to work with unbounded-size index values, which makes everything get messy pretty quickly.
    I think lambda calculus is the best of the bunch, but most people say I’m just weird.

    And if every program had to halt, I’d be out of a job; most of the programs I get paid to write are expected to keep running until the system is powered down.

    - dave — 4/15/2005 @ 12:10 am

  21. Brought to you by the letter N and the number N 1

    Moebius Stripper recalls how Big Bird taught her recursion. My mother, startled (her toddler was bawling at the end of Sesame Street, after all), hurried into the family room and asked me what was wrong, and I blubbered something about

    - Ernie's 3D Pancakes — 4/15/2005 @ 1:36 am

  22. Wow, So that’s what recursion is! Sweet!! Thanks!

    - Shinobi — 4/15/2005 @ 7:56 am

  23. The project I work on has in its credits: “This software has been brought to you by the letter x and the number π.”

    - Ron Avitzur — 4/15/2005 @ 8:32 am

  24. dave: Yes! I originally wrote lambda calculus, but then I was like, well, people are going to think I’m weird, so I replaced it by a RAM.

    - plam — 4/15/2005 @ 11:10 am

  25. […] re apparently marking their calendars with my students’ exam dates, but in any case, yes, it’s tru […]

  26. This is a math blog… preferring lambda calculus to Random Access Machines is *normal* :-)

    - Nitish — 4/15/2005 @ 3:54 pm

  27. Too bad I didn’t find this thread when it was more active… but… On the topic of Turing-Completeness and termination, I have two comments:

    1. Many important real-world programs don’t ever terminate. They simply do whatever they need to do, and then wait until they need to do something again.

    2. Charity is a programming language that doesn’t have general recursion. Every program is guaranteed to terminate, up to input. There is no need to provide proofs of termination in Charity!

    - Leon — 4/17/2005 @ 9:10 pm

  28. Leon - Most real-world functions do terminate. Only a handful of functions don’t terminate, and even these are mostly co-recursive so they are always productive.

    Leon - I expect recursion in Charity and Epigram work in the same way. In both cases you need to prove the function terminates, but in both cases the proof is implicit in the way you structure the function.

    plam - It is intresting that the requirement that all recursion is well-founded is just a nice side-effect of the language design rather than an explicit design goal. Languages like Epigram use one language to both program with and to reason (about programs) with. The easiest way of making the logic consistent is to require that all functions always terminate. The easiest way of making all functions always terminate is to make the recursion well-founded.

    - r6 — 4/18/2005 @ 9:31 am

  29. I just read this and I’ve been laughing for the last ten minutes. My office mate is looking at me funny. Here’s another example fron the world of children’s literature: In “The Cat in The Hat Comes Back”, The Cat in The Hat has a smaller cat under his hat. This, being Little Cat A, has a smaller cat in his hat, namely Little Cat B, and so on. Unfortunately, the alphabet is finite, and so Little Cat Z has something called VOOM under his hat, which fortunately instantly cleans messy rooms. Sure wish I had a Little Cat Z for my cesk.

    There is/was a modern fiction author named John Barth (I don’t know if he’s still alive or not) who seems convinced that he himself is a character in a work of fiction. In a short story called “Life-Story”, he wonders about the author who is writing his story. Then it occurs to him that that author might himself be a character in a work of fiction, and have an author writing about him, and so on up the line. At this point Barth decicdes he has a duty as an author to write stories about fictional characters writing stories about fictional etc. This quickly becomes a two-way infinite recursion. As I recall, Barth got about ten levels down on his end of the recursion before he evidently ran out of paper or something.

    Hey, it was mind-blowing stuff for a college freshman!

    - Cousin Dave — 4/19/2005 @ 1:03 pm

  30. Do you know about the computer scientist who starved to death in the shower?

    He read the instructions on his bottle of shampoo: “Lather, rinse, and repeat.”

    - Eric jablow — 4/19/2005 @ 9:56 pm

  31. Eric, that’s terrible.

    Great comments, all. Everyone should now reread all of them. ;-)

    - Moebius Stripper — 4/20/2005 @ 8:49 am

  32. Aw!

    Maybe I like this so much because I’d have reacted exactly the same way as a tot. Anyway, I put a link to this in my LJ.

    - Wyvern Rampant — 4/23/2005 @ 4:28 pm

  33. For those too old for Sesame Street, there’s always The Family Guy: I’m watching an episode, a rerun, in which Peter tells his son, “Everything I’ve ever said is a lie.” (Pause) “Except that. And that. And that. And that.” (Pause) “And that.”

    - Moebius Stripper — 5/31/2005 @ 9:10 pm

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.