TITLE: The Lisp 1.5 Universal Interpreter, in Racket AUTHOR: Eugene Wallingford DATE: June 03, 2016 3:07 PM DESC: ----- BODY:
John McCarthy presents Lisp from on High
"John McCarthy presents Recursive
Functions of Symbolic Expressions
and Their Computation by Machine,
Part I"
courtesy of Classic Programmer Paintings
Earlier this week, Alan Kay was answering questions on Hacker News and mentioned Lisp 1.5:
This got deeper if one was aware of how Lisp 1.5 had been implemented with the possibility of late bound parameter evaluation ...
Kay mentions Lisp, and especially Lisp 1.5, often whenever he is talking about the great ideas of computing. He sometimes likens McCarthy's universal Lisp interpreter to Maxwell's equations in physics -- a small, simple set of equations that capture a huge amount of understanding and enable a new way of thinking. Late-bound evaluation of parameters is one of the neat ideas you can find embedded in that code. The idea of a universal Lisp interpreter is pretty simple: McCarthy defined the features of Lisp in terms of the language features themselves. The interpreter consists of two main procedures: These procedures recurse mutually to evaluate a program. This is one of the most beautiful ideas in computing, one that we take for granted today. The syntax and semantics of Lisp programs are so sparse and so uniform that the McCarthy's universal Lisp interpreter consisted of about one page of Lisp code. Here that page is: Page 13 of the Lisp 1.5 Programmer's Manual, published in 1962.

Page 13 of the Lisp 1.5 Programmer's Manual

You may see this image passed around the Twitter and the web these whenever Lisp 1.5 is mentioned. But the universal Lisp interpreter is a program. Why settle for a JPG image? While preparing for the final week of my programming languages course this spring, I sat down and implemented the Lisp interpreter on Page 13 of the Lisp 1.5 manual in universal-lisp-interpreter.rkt, using Racket. I tried to reproduce the main procedures from the manual as faithfully as I could. You see the main two functions underlying McCarthy's idea: "evaluate an expression" and "apply a function to its arguments". The program assumes the existence of only a few primitive forms from Racket: 't means true, and nil means both false and the empty list. My Racket implementation uses #t and #f internally, but they do not appear in the code for the interpreter. Notice that this interpreter implements all of the language features that it uses: the same five primitive functions, the same two special forms, and lambda. It also defines label, a way to create recursive functions. (label offers a nice contrast to the ways we talk about implementing recursive functions in my course.) The interpreter uses a few helper functions, which I also define as in the manual. evcon evaluates a cond expression, and evlis evaluates a list of arguments. assoc looks up the value for a key in an "association list", and pairlis extends an existing association list with new key/value pairs. (In my course, assoc and pairlis correspond to basic operations on a finite function, which we use to implement environments.) I enjoyed walking through this code briefly with my students. After reading this code, I think they appreciated anew the importance of meaningful identifiers... The code works. Open it up in Racket and play with a Lisp from the dawn of time! It really is remarkable how much can be built out of so little. I sometimes think of the components of this program as the basic particles out of which all computation is built, akin to an atomic theory of matter. Out of these few primitives, all programs can be built. -----