TITLE: The Lisp 1.5 Universal Interpreter, in Racket
AUTHOR: Eugene Wallingford
DATE: June 03, 2016 3:07 PM
DESC:
-----
BODY:
|
|
"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:
- a procedure that evaluates an expression, and
- a procedure that applies a procedure to its arguments.
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.
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:
- the functions cons, car, cdr,
atom, and eq?
- the form lambda, for creating functions
- the special forms quote and cond
- the values 't and nil
'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.
-----