Alan Kay's Eval/Apply Einstein Moment

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.

It is most likely a reference to the bug of dynamic scope (a bug since the result isn't doing what it's supposed to do if it's expected to be similar to the lambda calculus):

eq[car[fn];LAMBDA] -> eval[caddr[fn];pairlis[cadr[fn];x;a]];
                                    %^^^^^^^^^^^^^^^^^^^^^

And in the edited semi-lisp-like text:

((eq (car fn) lambda) (eval (caddr fn) (parlis (cadr fn) x a)))
                                      ;^^^^^^^^^^^^^^^^^^^^^^

But this is not helpful at all. The fix must come not just there, in that one place; and you need to understand how the whole thing works and really follow it, to see how the bug happens.

As a quick hint in the right direction, the problem here is that the lambda function's body is evaluated in an environment (the second argument to eval) which is an extension of the current environment, resulting in dynamic scope. Solving it --- implementing lexical scope --- involves more than just an edit here, since the information about the lexical scope of the function is already lost.

(Any random decent book on PLs should have much more details. In the context of Lisp, digging deeper will indeed get you to the whole FUNARG thing.)

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.