Vladimir Sedach

Have Emacs - Will Hack

March 13, 2009

I think I finally understand what Alan Kay is saying about Lisp

Joe Marshall recently wrote a series of very entertaining blog posts telling the story of his first experiences with Lisp:

I had a similar experience with Lisp - reading the first few chapters of Structure and Interpretation of Computer Programs changed my outlook on computers and computer programming. By the time that happened (the summer of 2002, right before I started university), I had dabbled in C, although I was not particularly interested in computer programming.

The funny thing is I was exposed to Scheme my freshman year through Mike Zamansky's MCS1 at Stuyvesant High School. That experience was not particularly memorable, even less so was one of the other programming languages used in the course (Python, I think?). On the other hand the course also taught a whole bunch of really neat stuff in StarLogo.

When it came time to university, after successfully challenging out of the intro to CS course before classes started, I decided that since the course catalog descriptions for the computer science classes did not seem to look anything like what was in Structure and Interpretation, I would probably be better off investing my time in a math degree. The algebra and calculus examples in Structure and Interpretation were my first exposure to elegant computational mathematics, and I guess I can say Structure and Interpretation changed my outlook on math as well.

What does this have to do with Alan Kay?

Yesterday before falling asleep I was plagued by the question: why don't I enjoy using Haskell as much as Lisp? Haskell is purely functional, it features a really neat and unobtrusive type system, which when taken together with the great pattern-directed invocation programming style provides a better alternative to object-oriented programming. It is a really great programming language.

Could the reason be the ugly syntax? No, that is easy to fix. The type system does not bother me. There is a template system for both Haskell and Liskell syntax that provides preprocessor-style macros, but monads actually provide a much more powerful way of building control abstractions than macros do.

The only thing I could think of that Lisp has that Haskell cannot provide is a dynamic runtime system. It is as if Lisp comes with a really neat invisible virtual machine.

Among the many nice things Alan Kay says about Lisp, the term late binding comes up often. Practitioners of programming languages that Alan Kay did not have in mind when he invented the term "object-oriented" have taken it upon themselves to equate this to the concept they term dynamic binding, which they define to be type-directed dispatch done at runtime.

This is a textbook example of cargo cult programming. Dynamic types and runtime dispatch are not axioms of Lisp and Smalltalk, they are the emergent properties of self-describing computational systems. The key is that the definition of Lisp is written in Lisp. The "invisible virtual machine" in Lisp is Lisp. That is what Alan Kay means by late binding.

Why isn't Haskell self-describing? The reason is that there are actually two computational systems behind Haskell: one for the language itself (semantics of well-typed Haskell terms, Turing-complete), and one underlying the type system for the language (the algorithm for deciding whether a Haskell program is well-typed, and the data the algorithm operates on: the type rules that come with Haskell, the type rules defined by type declarations in the program, and the whole program itself). If type systems could be expressed in a metacircular way by the systems they were trying to type, they would not be able to express anything about types (restrictions on computations) of that system.

You can read more about the metacircular definition of Lisp in several books. The first of these is the original Lisp 1.5 Programmer's Manual; Alan Kay has called the metacircular definition of Lisp provided there "Maxwell's Equations of Software." Structure and Interpretation of Computer Programs includes a section on constructing a metacircular evaluator, and a whole chapter based around extending that evaluator with non-determinism and logic programming. The most thorough examination of the metacircular evaluation formulation of Lisp I have come across is present in John Allen's highly recommended 1978 book, Anatomy of Lisp.