Alan Kay's Eval/Apply Einstein Moment

Question

Alan Kay said that reading the code closely and finding the 1 and only bug in the code on page 13 of the Lisp 1.5 manual, helped him understand Computer Science by a factor of 100 better.

The code in question is the 1st release of eval & apply that looks anything remotely like modern lisp (that I'm aware of).

Since the correct answer is likely known but lost (my google-fu is decent and I've searched for 20 mins at least) I will award the 1st correct answer (I will be looking at edit times so don't try to cheat) a 250 point bounty As Soon As Possible.

I would suggest others contribute to the bounty as well, remember from the video above Alan Kay said this stuff is reminiscent of the environment Einstein was in when he discovered the Theory of Relativity.

The code in the text is written in M-Expressions. I'm working on a translator to translate from M-expressions to S-expressions (lisp code) @https://github.com/Viruliant/MccarthyMCEval-1.5.

Anyways here is the translated quote from page 13:

;______________________________________Lisp Meta-Circular Evaluator S-Expression
;this code is written in the order it appears on pages 10-13 in the Lisp 1.5 Manual 
;and is translated from the m-expressions into s-expressions

(label mc.equal (lambda (x y)
    (mc.cond
        ((atom x) ((mc.cond ((atom y) (eq x y)) ((quote t) (quote f)))))
        ((equal (car x)(car y)) (equal (cdr x) (cdr y)))
        ((quote t) (quote f)))))

(label mc.subst (lambda (x y z)
    (mc.cond
        ((equal y z) (x))
        ((atom z) (z))
        ((quote t) (cons (subst x y (car z))(subst x y (cdr z)))))))

(label mc.append (lambda (x y)
    (mc.cond 
        ((null x) (y))
        ((quote t) (cons (car x)) (append (cdr x) y)))))

(label mc.member (lambda (x y)
    (mc.cond ((null y) (quote f))
    ((equal x (car y)) (quote t))
    ((quote t) (member x (cdr y))))))

(label mc.pairlis (lambda (x  y  a)
    (mc.cond ((null x) (a)) ((quote t) (cons (cons (car x)(car y))
    (pairlis (cdr x)(cdr y) a)))))

(label mc.assoc (lambda (x a)
    (mc.cond ((equal (caar a) x) (car a)) ((quote t) (assoc x (cdr a))))))

(label mc.sub2 (lambda (a z)
    (mc.cond ((null a) (z)) (((eq (caar a) z)) (cdar a)) ((quote t) (
    sub2 (cdr a) z)))))

(label mc.sublis (lambda (a y)
    (mc.cond ((atom y) (sub2 a y)) ((quote t) (cons (sublis a (car y))))
    (sublis a (cdr y)))))

(label mc.evalquote (lambda (fn x)
    (apply fn x nil)))

(label mc.apply (lambda (fn x a)
    (mc.cond ((atom fn) (
        (mc.cond
            ((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)))
            ((quote t) (apply (eval (fn a)x a))))))
        ((eq (car fn) lambda) (eval (caddr fn) (parlis (cadr fn) x a)))
        ((eq (car fn) label) (apply (caddr (fn)x cons (cons (cadr (fn)))
            (caddr fn))a)))))

(label mc.eval (lambda (e a)
    (mc.cond
        ((atom e) (cdr (assoc e a)))
        ((atom (car e)) (mc.cond
            ((eq (car e) quote) (cadr e))
            ((eq (car e) cond) (evcon (cdr e) a))
            ((quote t) (apply (car e) (evlis (cdr e) a) a))))
        ((quote t) (apply (car e) (evlis (cdr e) a) a))))))

(label mc.evcon (lambda (c a)
    (mc.cond 
        ((eval (caar c) a) (eval (cadar c) a))
        ((quote t) (evcon (cdr c) a)))))

(label mc.evlis (lambda (m a)
    (mc.cond
        ((null m) (nil))
        ((quote t) (cons (eval (car m) a) (evlis (cdr m) a)))))))

Answer 1

There are two different issues:

First: Dynamic binding as a bug

Not sure what he means, but generally in McCarthy's EVAL the use of dynamic binding can be seen as a bug. He does not implement lexical scope for variables. The bug shows up for example here:

http://www-formal.stanford.edu/jmc/recursive/node3.html

See the functions maplist and diff. Both use x. This won't work as shown, since the early Lisp provides dynamic binding.

A simpler example, which shows that the evaluator uses dynamic binding

Note the use of eval., which is the eval from McCarthy.

CL-USER 36 > (eval. '((lambda (f)
                        ((lambda (x) (f))
                         'foo))
                      '(lambda () x))
                    nil)

This returns FOO, since the value of X is looked up from the dynamic binding.

If we look at the code, it requires us to pass a function as a list: '(lambda () x)). This evaluates to a list. Later the list will be called via (f) - with no arguments. The list then is interpreted as a lambda expression and x will be resolved by looking at the current dynamic binding for x. There is the binding of x to FOO introduced by ((lambda (x) (f)) 'foo). This will be used then.

In the Lisp 1.5 implementation from the 60s, one might write something similar to:

((lambda (f)
   ((lambda (x) (f))
    'foo))
 (function (lambda () x)))

Note that (function (lambda () x)) evaluates to a list of a marker, dynamic environment and the function. Unfortunately the Lisp 1.5 implementation still used dynamic binding. So that was already the right direction, but the bug wasn't really fixed then. Improved was the situation when one was passing functions to other functions as arguments.

The FUNARG problem

It took quite some time during the 60s/early 70s to figure out this problem. It was known as the FUNARG problem. See for example Joel Moses paper: The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem. There were various solutions to create closures and to use lexical binding. Often the interpreter used dynamic binding and the compiler used lexical binding. In the Lisp world this was basically solved in Scheme, which introduced lexical binding by default. This lexical binding then allows for example to use closures to emulate object systems (something that Kay probably finds useful). See the paper: SCHEME: An Interpreter for Extended Lambda Calculus from 1975.

In Common Lisp, which uses lexical scope by default like the Lisp dialect Scheme, above example would be an error (here we use the eval from Common Lisp, with slightly changed code to make it legal Common Lisp code):

CL-USER 43 > (eval '((lambda (f)
                       ((lambda (x) (funcall f))
                        'foo))
                     (function (lambda () x))))

Error: The variable X is unbound.

As you can see in Common Lisp (and Scheme), (lambda () x) is a real lambda expression, not a quoted list and (function (lambda () x)) evaluates to a function object - if there are bindings, then it is a closure - a function object and its bindings. This function object / clojure is passed and then later called via (funcall f). Since the x refers to nothing (it is a free variable) and is not looked up via bindings, an error occurs when the code is executed. That's what we want: we want lexical binding and this error in our code is a consequence. That this error does not happen in McCarthy's original Lisp is one result of the bug. Fixing this bug (which took more than a decade to full satisfaction), enables us to use closures in Lisp - like in Common Lisp, which learned it from Scheme.

Probably Kay also saw dynamic binding as a bug. This is a very fundamental problem and understanding/solving it, helped to design and develop better programming languages.

Note that typical early Smalltalk implementations (example Xerox' Smalltalk 80) also used dynamic binding.

McCarthy about that bug

In From LISP 1 to LISP 1.5 (1979) McCarthy writes (bold by me):

d. Free variables. In all innocence, James R. Slagle programmed the following LISP function definition and complained when it didn't work right:

The object of the function is to find a subexpression of x satisfying p[x] and return f[x]. If the search is unsuccessful, then the continuation function u[] of no arguments is to be computed and its value returned. The difficulty was that when an inner recursion occurred, the value of car[x] wanted was the outer value, but the inner value was actually used. In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained.

I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument. Similar difficulties later showed up in Algol 60, and Russell's turned out to be one of the more comprehensive solutions to the problem. While it worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises. Unfortunately, time did not permit writing an appendix giving the history of the problem, and the interested reader is referred to (Moses 1970) as a place to start. (David Park tells me that Patrick Fischer also had a hand in developing the FUNARG device).

This is unrelated to the second problem:

Second: bugs in a different version of EVAL in the same book

See Paul Graham's The Roots of Lisp for a discussion of a bug in a definition of EVAL later in the book. On page 12 you find a description of a bug in McCarthy's code which causes double evaluation of arguments to a named function.

Answer 2

it looks like

equal[x;y] =
        [atom[x] -> [atom[y] -> eq[x;y]; T -> F];
         equal[car[x];car[y]] -> equal[cdr[x];cdr[y]];
         T -> F]

doesn't handle the case where x is a cons and y is an atom

edit: also assoc will fail to return nil if the key is not found.