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

Anaesthesia

Do you think it might be that eval depends on apply to eval some of the things in the function position, rather than evaluating it directly? I.e., (eval '(foo x y z) a) calls (apply 'foo (evlist '(x y z) a) a) rather than (apply (eval 'foo a) (evlist '(x y z) a) a). – Johansen

@JoshuaTaylor I don't know, but hopefully after I put the 250 point bounty on it there will be enough eyes that maybe we can agree on what the bug is. – Anaesthesia

I think you've misunderstood him. It is not "by" finding the bug that he felt enlightened, but "after those two hours" following the code closely and coincidentally finding the "one bug". I.e. what influenced him was not that bug, but the code as a whole. – Cassiani

@WillNess I never said I didn't want to understand the code as whole, I'm just curious what the bug was, and also wanted to spread the word about this wonderful piece of code. – Anaesthesia

"anyways here is the quote from page 13" not it's not, now. you know you're not supposed to switch the question on us like that. – Cassiani

@WillNess updated the question, added the single word "translated", I am still working on the automated translator and most of this translation was done by hand, in fact page 10 shows explicitly all the simple translation that is done from m-expressions to s-expressions. If you see any error please notify me. If you still wish to see the original m-expression it is available on page 13 in the text or at github.com/Viruliant/MccarthyMCEval-1.5/blob/master/… – Anaesthesia

Answer 1

update2: Here's the code from the paper, rewritten in some pseudocode with list patterns and comprehensions (including parallel comprehensions), in all of 13 lines of code (15 with the addition of FUNARG device, discussed below), all here in one definition:

apply f args = eval [f, ...[[QUOTE, a] | a <- args]] []  {- McCarthy-LISP-paper    -}

eval e a | atom e    = head [v | [n, v] <- a, n == e] 
         | otherwise = case e of
  [QUOTE,    x]     ->  x 
  [FUNCTION, x]     ->  [FUNARG, x, a]     {- enclose the definitional environment! -}
  [CONS,  x, y]     ->  [eval x a, ...eval y a] 
  [CAR,      x]     ->  head ( eval x a )
  [CDR,      x]     ->  tail ( eval x a )
  [ATOM,     x]     ->  atom ( eval x a ) 
  [EQ,    x, y]     ->  eval x a == eval y a 
  [COND, ...xs]     ->  head [eval c a | [t, c] <- xs, eval t a] 
  [[LAMBDA,p,b], ...xs] -> eval b [...[[n, eval x a] | n <- p | x <- xs], ...a]
  [[LABEL, n,x], ...xs] -> eval [x, ...xs]  [[n, [LABEL, n, x]], ...a]  
  [[FUNARG,f,d], ...xs] -> eval [f, ...[[QUOTE, eval x a] | x <- xs]] d   {- d (sic) -}
  [x,            ...xs] -> eval [eval x a, ...xs] a             {- fixing the bug,   -}
                {-  eval [eval x a, ...[eval x a | x <- xs]] a  -- args eval'd twice -}

(2021 update:) to support variable length argument lists with (lambda p ....), we add another clause,

  [[LAMBDA,p,b], ...xs] | atom p ->                                {- this one -}
                           eval b [ [p, [eval x a | x <- xs]], ...a]
  [[LAMBDA,p,b], ...xs] -> eval b [...[[n, eval x a] | n <- p | x <- xs], ...a]

where pat | guard -> .... fires when guard evaluates to true when and if pat matches.

---

update: here's a video by Philip Wadler where he talks (at 22:30) about that "bug", and how using the "wrong variable" (for the environment to be used in evaluating a lambda-body, a instead of env in the pseudocode that follows) leads to "dynamic binding" rather than "static biding".

---

I've re-written the original M-expressions from the code in the book (Lisp 1.5 programmers manual) in some ad-hoc pseudocode which is easier for me to follow, using : for cons or ., with pattern-matching, etc., which follows shortly.

Actually, I can't see any double-evaluation problem with it. apply expects its arguments already evaluated, and eval evaluates them for it.

I think the bug was in the original paper "Recursive Functions of Symbolic Expressions" (update: yes! Rainer Joswig mentions at the end of his answer the Paul Graham article, which states that this was in reference to the code in the paper).

So indeed it looks likely that Alan Kay's remark was in reference to the dynamic scoping. He mentions looking "at the bottom of pg 13" (so, in the book) and that's where the evlis definition is, which evaluates list's elements in the same, current environment. Look at the book's pages 70, 71 for the solution to this, requiring a programmer to explicitly tag their lambda definitions with a new keyword function, to create funarg-tagged lists packaging the lambdas together with (or closing over, as in "closure") the environment at the time the function form is evaluated - i.e. the definitional environment of that lambda form.

Moses 1970 calls it binding environment, discussing only implicit creation of closures when used as functional arguments in a higher-order function invocation (hence the "funarg" moniker). This is also the context in more contemporary discussions of "deep and shallow binding" (misusing the terminology, in my view) in the word of Perl etc.

But looking at that extended version in the book, it seems it would allow a programmer to create such entities explicitly, store them in a variable, pass it around as just any other first class entity. Then, when a closure (a funarg-tagged list) is applied, the lambda definition is evaluated in its environment, not the current one (what Moses 1970 calls activation environment). This gets one very close to convincingly imitating lexical scoping with dynamic binding.

Here's that pseudocode, following the code from the book:

evalquote fn x = apply fn x []    {- `x` a list of arguments -}

apply CAR ((x:_):_) a = x         {- `a` an association-list, the environment -}
 |    CDR ((_:x):_) _ = x
 |   CONS (x:y:_)   _ = x:y
 |   ATOM (x:_)     _ = atom x
 |     EQ (x:y:_)   _ = eq x y
 | fn xs a , atom fn        = apply (eval fn a) xs a
 | (LAMBDA  args body) xs a = eval body (pairlis args xs a)
 | (LABEL  fn lambda)  xs a = apply lambda xs ((fn:lambda):a)
   {- and the FUNARG device, pg 70: -}
 | (FUNARG lambda env) xs a = apply lambda xs env           {- not `a`, NB! -}

eval e a , atom e      = assv e a
 | (QUOTE e)   _       = e
 | (COND (t c) : cs) a = { eval t a -> eval c a ; eval (COND:cs) a }
   {- the FUNARG device, pg 71: -}
 | (FUNCTION lambda) a = (FUNARG lambda a)  {- enclose the definitional environment! -}
 | (e1:es) a , atom e1 = apply e1 (evlis es a) a 
 | (e1:es) a           = apply e1 (evlis es a) a  

evlis (m : ms) a           = eval m a : evlis ms  | [] _ = []
equal (x:xs) (y:ys)        = equal x y && equal xs ys
 |    x y , atom x, atom y = eq x y               | _ _  = F
subst x y z , equal y z = x
 |    _ _ z , atom z    = z
 |    x y (h:t)         = subst x y h : subst x y t
append (x:xs) ys        = x : append xs ys        | [] ys = ys
member x (y:_) , equal x y = T 
 |     x (_:ys)         = member x ys             | _ []  = F
pairlis (x:xs) (y:ys) a = (x:y) : pairlis xs ys a | _ _ a = a
assv x ((h:y):ys)       = { x==h -> y ; assv x ys }
sub2 ((x:v):xs) z   = { eq x z -> v ; sub2 xs z } | [] z  = z
sublis a y , atom y = sub2 a y    | a (y:ys) = sublis a y : sublis a ys

Cassiani

Answer 2

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.

Bosworth

I believe this exactly it! but there are multiple instances of [evlis[cdr var1]var2] I'm still uncertain which one. lines 22, 23, & 31 github.com/Viruliant/MccarthyMCEval-1.5/blob/master/… – Anaesthesia

@GlassGhost: I have edited the answer to make clear that the evlist isn't the problem Kay probably means. – Bosworth

@GlassGhost: I explained in more detail what the bug/problem is. – Bosworth

((lambda (f) ((lambda (x) (f)) 'foo)) (function (lambda () x))) looks wrong. function supposed to package the lambda with the current environment, which has no reference to x. Your example would work without the function. – Cassiani

@WillNess: in Common Lisp LAMBDA is a macro, which expands into (function (lambda ...)). There is no difference. – Bosworth

you were talking about Lisp 1.5 in the 60s though, in that snippet? – Cassiani

@WillNess: that one did not have lexical scope and no closures. – Bosworth

right, and so by using function to package the lambda with its definitional environment, one could come close to imitating the lexical scope. – Cassiani

see eq[car[form];FUNCTION]->list[FUNARG;cadr[form];a];, on pg. 71. – Cassiani

@WillNess: that's a dynamic environment used by the interpreter. – Bosworth

which is getting package into a FUNARG-tagged list, together with the lambda . – Cassiani

@WillNess: it does not solve the bug/problem, since it is no lexical environment. – Bosworth

absent mutation, it does. the fact remains, your code snippet would cause unresolved reference x error. – Cassiani

@WillNess: that's fine, but it is more important that there is a correct scoping and the bindings are resolved correctly. There is no way around it that Lisp 1.5 implements dynamic binding and FUNCTION does not help here. Lexical Closures were added later in Lisp. – Bosworth

looks like I was unduly over-cautious, citing "mutation" (was thinking about C#'s for-expressions woes). As you quote McCarthy himself in your answer, he said the FUNARG device actually solved the issue: "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." the only problem might remain with closure-returning functions but even it is solved with explicit use of FUNCTION. – Cassiani

@WillNess: as I said full lexical bindings show up much later. FUNCTION was a hack that provided dynamic closures as a list. It was thought to help with passing functions. It still did not generate first class functions (but a list) and was not intended for cases where functions are returned. – Bosworth

but what does list[FUNARG;cadr[form];a] do if not "packaging the (lexical) environment along with the functional argument"? Of course here the environment is not lexical, as it is monolithic and not segmented into frames (so would allow improper reference to outer vars which should fail in proper lexical scoping) but it comes darn close. – Cassiani

@Willness: it is a hack of a dynamic closure returned as a list. No first class lexical closure. – Bosworth

Answer 3

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.)

Brattishing

Answer 4

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.

Contaminate