Programming Praxis

John McCarthy, the inventor of Lisp, died on October 23, 2011. In his honor we will implement a Lisp interpreter in today’s exercise. He first described Lisp in an academic paper, and the LISP 1.5 Programmer’s Manual, published in 1962 but still in print, is an early definition of the language (the LISP 1.0 manual by Patricia Fox was dated 1960, which is usually cited as the birth year of Lisp, even though Lisp was formally specified as early as 1958). McCarthy defines the eval/apply yin/yang that is at the heart of Lisp on page 13, in what Alan Kay described as the Maxwell’s equations of software. We begin with the definition of apply:

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]]]

Apply interprets expressions. The first clause dispatches on the various built-in functions of Lisp, calling the underlying language (in this case, Lisp, since this is a meta-circular evaluator) to evaluate the function. The second clause evaluates functions defined by lambda by calling eval. The third clause is special; it evaluates recursive functions defined by label by first adding the function to the environment, then calling apply recursively to evaluate the new function. Apply uses an auxiliary function pairlis to insert function definitions in the environment a; as an example, pairlis[(A B C);(U V W);((D . X) (E . Y))] evaluates to ((A . U) (B . V) (C . W) (D . X) (E . Y)):

pairlis[x;y;a] = [null[x] → a; T → cons[cons[car[x];car[y]];
                 pairlis[cdr[x];cdr[y];a]]]

Eval handles statements, which are known as special forms in the parlance of Lisp. In a function, the elements of an expression are all evaluated before the function at the head of the expression is called, but in a statement the order of evaluation may change; for instance, in an if statement only one of the two consequents is evaluated. Here is eval:

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]]

Eval handles two special forms: Quote handles its argument literally rather than evaluating it as an expressions. Cond executes code conditionally, checking the predicate of each clause until it finds one that is true, when it evaluates the associated expression. Eval uses three auxiliary functions. The first is assoc, which performs a lookup in an environment; for instance, assoc[B;((A . (M N)), (B . (CAR X)), (C . (QUOTE M)), (C . (CDR X)))] evaluates to (B . (CAR X)):

assoc[x;a] = [equal[caar[a];x]→car[a]; T → assoc[x;cdr[a]]]

Evcon interprets a cond statement, evaluating the predicate of each clause, then evaluating the expression associated with the first predicate that is true:

evcon[c;a] = [eval[caar[c];a] → eval[cadar[c];a];
             T → evcon[cdr[c];a]]

Evlis evaluates the elements of a list, in order, returning a new list with the results of each evaluation:

evlis[m;a] = [null[m] → NIL;
             T → cons[eval[car[m];a];evlis[cdr[m];a]]]

Finally, evalquote is the entrance to the evaluator:

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

Your task is to implement a simple Lisp interpreter in the style of John McCarthy. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2