Monday, March 29, 2010

Programming Languages: an Interpreter-based Approach

The title of this post is the name of a wonderful book by Samuel Kamin of the University of Illinois (birthplace of HAL 9000).

I learned about it reading Peter Norvig's blog. Kamin has introduced a fresh new way of teaching programming language theory: the no-syntax, interpreter-based approach.

Tradditionaly, programming language theory in Computer Science is taught either (or both) via compiler construction (the Dragon Book approach) and/or via computer language surveys (the Sebesta approach, of which Programming Language Pragmatics, by Michael L. Scott, is a better example).

Instead of spending a lot of time with syntatic issues which are not that interesting, Kamin presents interpreters for several languages with very different semantics but all using a Lisp-like syntax, which is the easiest to parse (for computers, at least). So, for example, Kamin shows a subset of Smalltalk with real Smalltalk semantics but written in s-expressions.

The interpreters in Kamin's book are written in Pascal. The same approach was taken by two modern books which substitute Pascal with Scheme: Essentials of Programming Languages, by Friedman and Wand, and Programming Languages, Application and Interpretation, by Krishnamurthi (a free book, check it out).

These professors don't just write about the different languages: they teach how to, and make you (through the exercises) implement interpreters for each of them. Again, a very smart shortcut: if you don't need to generate code, but just execute an abstract syntactic tree, you can do a lot more conceptual exploration in one semester. I bet most people who take a course based on either the compiler or the survey approaches never get to understand how continuations actually work and are implemented, at least not in that same course.

Recently I took a course at IME-USP based on the Krishnamurthi book and it was the most exciting learning experience I've had after the Art and Programming Workshop. I'm very proud to say I got a 10 in both courses (that's an A+ in Brazil).

Art and Programming Workshops

Yesterday (2010-03-28) I finished teaching my second Processing at SESC. SESC is a chain of very active centers for culture where shows, plays, courses and lots of other activities happen.

Tony de Marco was my co-pilot in that workshop. Tony is an award-winning font designer, and the founder of Macmania and Magnet, two computer magazines to which I contributed many articles. He took the picture above.

Tony and I were students of Etienne Delacroix, the particle-physicist turned artist who taught PSI- 2615, Art and Programming Workshop, a full semester course at POLI/USP, a famous engineering school in Brazil. In the class each student had to build his own computer from discarded computer parts, and make it run some software with expressive intent. I wrote a sequencer in Tcl/Tk, originally intended to program a row of LEDs for a POV display, but it ended up being adapted to drive a little drum section made of cans and bottles.

Etienne taught me how JavaScript can be simple, that "which first language?" is a silly question because teaching several languages in parallel works, and that any technology starts as a fusion of science and handicraft. The engineering comes later. This last point he illustrated with this picture of the first transistor, the most important invention of the XX century: