Yes, that was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!”

This quote appears many places on the web, but the code itself is harder to find. What *is* this amazing half page of code?

The Lisp 1.5 Manual, which was written by John McCarthy et al in 1961, is available at softwarepreservation.org. In it, the "Maxwell's equations" define a universal Lisp function `evalquote`

that can evaluate any given function:

evalquote[fn;x] = apply[fn;x;NIL]where

apply[fn;x;a] = [atom[fn] -> [eq[fn;CAR] -> caar[x]; eq[fn;CDR] -> cdar[x]; eq[fn;CONS] -> cons[car[x];cadr[x]]; eq[fn;ATOM] -> atom[car[x]]; eq[fn;EQ] -> eq[car[x];cadr[x]]; T -> apply[eval[fn;a];x;a]]; eq[car[fn];LAMBDA] -> eval[caddr[fn];pairlis[cadr[fn];x;a]]; eq[car[fn];LABEL] -> apply[caddr[fn];x;cons[cons[cadr[fn]; caddr[fn]];a]]] eval[e;a] = [atom[e] -> cdr[assoc[e;a]]; atom[car[e]] -> [eq[car[e],QUOTE] -> cadr[e]; eq[car[e];COND] -> evcon[cdr[e];a]; T -> apply[car[e];evlis[cdr[e];a];a]]; T -> apply[car[e];evlis[cdr[e];a];a]] evcon[c;a] = [eval[caar[c];a] -> eval[cadar[c];a]; T -> evcon[cdr[c];a]] evlis[m;a] = [null[m] -> NIL; T -> cons[eval[car[m];a];evlis[cdr[m];a]]]

The above code is defined in a meta-language (M-expressions), which can be straighforwardly translated into S-expressions. Functions in M-expressions use square brackets and have arguments separated by semicolons. M-expressions conditionals are of the form `[predicate -> value; predicate -> value; ...]`

. M-expression `label`

is analogous to `defun`

or `define`

.

The point of all this is that M-expressions are the code that operates on the S-expression data, but the M-expression meta-language and S-expression data actually coincide. Thus, code and data are the same thing in Lisp, and a half-page of code is sufficient to define a basic Lisp interpreter in Lisp given a few primitives (`car, cdr, cons, eq, atom`

). The code presents a Meta-circular evaluator for Lisp; see (SICP chapter 4.1 for more details on metacircular evaluators. (Unfortunately, this won't give you a working Lisp interpreter for free; things such as the garbage collector, the list primitives, and parsing need to be implemented somewhere. Also note that this metacircular evaluator doesn't give you niceties such as arithmetic.))

To understand the above code, `apply`

takes a function and argument, while `eval`

acts on a form. The last argument to these is an association list for the environment, which stores the values of bound values and function names. In brief, `apply`

implements `CAR`

, `CDR`

, `CONS`

, `ATOM`

, and `EQ`

in terms of the primitives. It implements `LAMBDA`

by pairing up the variables and arguments and passing them to `eval`

. It implements `LABEL`

(which defines a function) by adding the function name and definition to the association list.

The code for `eval`

processes a form in a straightforward manner. It handles the `QUOTE`

form by returning the quoted value. It handles `COND`

by evaluating the predicates with the help of `evcon`

. Otherwise, it interprets an atom as a variable and returns the value. If given a list, it interprets this as a function application; the arguments are evaluated with `evalis`

and the function is evaluated by `apply`

.

The above code is not quite complete; it relies on some other simple functions that were previously defined in the manual, such as `equals`

and `cadr`

Less obvious functions are `pairlis[x;y;a]`

pairs up lists `x`

and `y`

and adds them to association list `a`

. `assoc[x;a]`

looks up `x`

in association list `a`

. `sublis[a;y]`

treats association list `a`

as a mapping of variables to values, and replaces variables in S-expression `y`

with the associated variables. These functions can be straightforwardly built from the primitive functions.

(By the way, I'm pretty sure the comma in `eq[car[e],QUOTE]`

is a typo, but that's how it is in the original.)

Early eval definitions were like doomed, all had bugs. Definition of McCarthy's Lisp in McCarthy's Lisp can be of interest.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThank you for your post; since you care about typos while copying the code from the original book, be aware of your own typo in the part of the code for the "apply" function where "parlis" should be written "pairlis"; Regards.

ReplyDeleteThanks, Anonymous. I've fixed the typo,

ReplyDelete