TITLE: What Penn and Teller Have in Common With a Compilers Course AUTHOR: Eugene Wallingford DATE: April 11, 2012 4:06 PM DESC: ----- BODY: Early this morning (and I mean early!), Alfred Thompson posted What Do Magic and Computer Science Have in Common?, relaying that Alex Suter of Industrial Light & Magic will give the closing keynote at this summer's Computer Science and Information Technology conference. That sounds pretty cool. The title of his entry conjured up other thoughts for me, though, especially in light of something I said in class yesterday. Recently, I used a superhero reference in a blog entry. That is how many people feel when they use a program to accomplish something meaningful -- like a superhero. I feel that way, too, sometimes. However, like many other people, I am more prone to magical imagery. To someone who has not learned to code, a program is like an incantation, capable of making the computer do something mystical. There is a long tradition of magical imagery in computer science. The Hacker's Dictionary tells us that a wizard is someone who knows how a complex piece of software or hardware works (that is, who groks it). A wizard can do things that hackers and mere mortals cannot. The entry for "wizard" has links to other magical jargon, such as heavy wizardry incantation>/A> and magic itself.

Structure and Interpretation of Computer Programs

I tell my Programming Languages students that this is a course in which the "high priests" of computer science reveal their secrets, that after the course students will understand the magic embodied in the interpreters and compilers that process their programs. I should probably refer to wizards, rather high priests, given that so many of the course's ideas are covered masterfully in SICP. Lots of CS courses reveal magic, or propose it. A course in compliers finishes the job of Programming Languages, driving program translation all the way down to hardware. Artificial Intelligence describes our best ideas for how to make a computer do human-like magic: reasoning, recognizing patterns, learning, and playing Jeopardy!. In my compliers class yesterday, I was showing my students a technique for generating three-address code from an abstract syntax tree, based in large part on ideas found in the Dragon book (surely not a coincidence). I wrote on the board this template for a grammar rule denoting addition:

    E → E₁ + E₂

    E.place := makeNewTemporaryIdentifier()
    E.code  := [ E₁.code ]
               [ E₂.code ]
               emitCode( E.place " := " E₁.place " + " E₂.place )

When I finished, I stepped back, looked it over, and realized again just how un-magical that seems. Indeed, when in written in black on white, it looks pretty pedestrian.

That made me think of another connection between magic and computer science, one that applies to practitioners and outsiders alike. Taking an AI course or a compilers course is like having Penn and Teller explain to you how they made a person disappear or a ball levitate in thin air. For some people, that kills any joy that might have in watching the act. They don't want to know. They want to be amazed. And, knowing that something is implemented -- often in a way that doesn't seem especially artful, performed with an obvious misdirection -- prevents them from being amazed. That can happen in CS, too. My friends and I came in to our AI course wide-eyed and wanting to be amazed -- and to build amazing things. We studied search and logical resolution, Bayes' Theorem and decision tree induction. And it all looked so... pedestrian. Many of my friends lost their sense of wonder then and there. Without the magic of AI, they were just as interested in operating systems or databases. More interested, really, because AI had let them down. It all looked like parlor tricks. But there is a second kind of person in the world. Lots of people love to watch Penn and Teller explain a trick. They want to know how it works. They want to watch again, knowing how it works, to see if they can notice the deception. If they don't, they are amazed again. If they do, though, they still feel wonder -- at the skill of the magicians, at the design of the illusion, and even at the way their mind wants to trick them at the moment of execution. I am of this second kind, for magic and especially for computer science. Yes, I know that compilers and AI programs are, at their cores, implemented using techniques that don't always look all that impressive in the light of day. Sometimes, those techniques look pretty boring indeed. Yet I am still amazed when a C compiler takes in my humble instructions and creates machine code that compresses a musical file or fills out my tax return. I am amazed when Watson crunches through gazillions of bytes of data in a second or two and beats two most worthy human opponents to the buzzer. I like to hear my friends and colleagues de-mystify their current projects with nitty-gritty details. I still feel wonder -- at their skill, at the cleverness of their designs, and even at the moment the program runs and makes something out of what seems like nothing. That's one thing magic and computer science have in common. ~~~~ IMAGE 1: a photo of the cover of Structure and Interpretation of Computer Programs. Source: the book's website. IMAGE 2: a publicity still of magicians Penn and Teller. Source: All-About-Magicians.com. -----