RIP John McCarthy

November 1, 2011

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.

About these ads

Pages: 1 2

5 Responses to “RIP John McCarthy”

  1. Jussi Piitulainen said

    Let him be remembered, among other things, for the conditional expression. And for the art of the interpreter to describe programming language semantics, of course.

    This is Python 3 to implement a Scheme-like language: variables, int constants, lexically scoped functions and calls, and the McCarthy conditional. And definitions. Primitive operations can be added to the top level environment similar to the “<" which I put there just for the signum test.

    def define(var, exp, env): env[0][var] = evaluate(exp, env)
    
    def evaluate(exp, env):
        return ( exp if isinstance(exp, int)
                 else lookup(exp, env) if isinstance(exp, str)
                 else special(exp, env) if isinstance(exp[0], str) and lookup(exp[0], env) == "specop"
                 else call(exp, env) )
    
    def lookup(var, env): return env[0][var] if var in env[0] else undefined if env is top else lookup(var, env[1])
    
    def special(exp, env):
        if exp[0] == "fun":
            _, params, body = exp
    	return ("closre", params, body, env)
        else:
            for condition, consequent in zip(exp[1::2], exp[2::2]):
                if evaluate(condition, env): return evaluate(consequent, env)
            return undefined
    
    def call(exp, env):
        proc, *args = [ evaluate(sub, env) for sub in exp ]
        if proc[0] == "primop": return proc[1](*args)
        else:
            _, params, body, env = proc
            return evaluate(body, ( { param : arg for param, arg in zip(params, args) }, env ))
    
    top = ( { "<" : ("primop", lambda x, y : int(x < y)), "fun" : "specop", "if" : "specop" },
            "not an environment" )
    
    undefined = ("primop", lambda *x : "sorry")
    
    def test():
        "Returns (1, 0, -1), defines sgn in top"
        define("sgn", ["fun", ["x"], ["if", ["<", "x", 0], -1, ["<", 0, "x"], +1, 1, 0]], top)
        return evaluate(["sgn", 3], top), evaluate(["sgn", 0], top), evaluate(["sgn", -3], top)
    
    def test2():
        "Returns 41, defines cons, car, cdr in top"
        define("cons", ["fun", ["x", "y"], ["fun", ["c"], ["if", "c", "x", 1, "y"]]], top)
        define("car", ["fun", ["p"], ["p", 1]], top)
        define("cdr", ["fun", ["p"], ["p", 0]], top)
        return evaluate(["car", ["cdr", ["cons", 31, ["cons", 41, 59]]]], top)
    
  2. Jussi Piitulainen said

    The indentations looked more or less right before I submitted the code. Where did they go?

  3. Jussi Piitulainen said

    (Thanks for the fix.)

  4. [...] Lisp in Scheme An implementation of McCarthy’s original Lisp in Scheme. [...]

  5. [...] RIP John McCarthy « Programming Praxis [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: