* Programming language: Lisp. One of the most important programming
languages, and probably the most important if we discuss parentheses.
* Author: John McCarthy, the creator of Lisp.
* Article: Recursive Functions of Symbolic Expressions, Communications
of the ACM, April 1960, probably the most important article on Lisp.
* Place: definition of arguably the most important function ever: eval.
The holiest place for programmers not afraid of parentheses!
|
Yet, parentheses do not match there.
This is not typical Lisp S-expression, it is so called "meta expression".
Here is original version of the article:
|
And here is the same mismatch in the version retyped using Latex.
|
I'll not say where is the error. I'll leave you to play
with that. Here is the text, so you can copy and paste it in
your editor. The simplest way to check my claim that there is
an error is that your editor counts left and right brackets.
Notepad++ says there are 68 left and 66 right brackets here.
|
eval[e; a] = [
atom [e] -> assoc [e; a];
atom [car [e]] -> [
eq [car [e]; QUOTE] -> cadr [e];
eq [car [e]; ATOM] -> atom [eval [cadr [e]; a]];
eq [car [e]; EQ] -> [eval [cadr [e]; a] = eval [caddr [e]; a]];
eq [car [e]; COND] -> evcon [cdr [e]; a];
eq [car [e]; CAR] -> car [eval [cadr [e]; a]];
eq [car [e]; CDR] -> cdr [eval [cadr [e]; a]];
eq [car [e]; CONS] -> cons [eval [cadr [e]; a]; eval [caddr [e];
a]]; T -> eval [cons [assoc [car [e]; a];
evlis [cdr [e]; a]]; a]];
eq [caar [e]; LABEL] -> eval [cons [caddar [e]; cdr [e]];
cons [list [cadar [e]; car [e]; a]];
eq [caar [e]; LAMBDA] -> eval [caddar [e];
append [pair [cadar [e]; evlis [cdr [e]; a]; a]]]
|
Some puritans might insist that it is brackets mismatch and not
parentheses mismatch. Wikipedia thinks that brackets are one type
of parentheses.
Of course, I cannot say that it is one of the most important
parentheses mismatches in history of programming. It had no effect
whatsoever, as far as I know.
Herbert Stoyan wrote about this error, and it is mentioned
in Latex version of the McCarthy's article, 1995.
Similar error in Lisp I. Programmer's Manual.
It is brought to my attention that intern unofficial publication,
"LISP I. Programmer's manual" from March 1960, has different definition:
|
However, it is also likely wrong. Look at the line with
LABEL, and two occurrences of cdr[e]. With some help of Shubert
who commented this post, I believe that the it should be:
|
eval[e; a] =
[
atom [e] -> assoc [e; a];
atom [car [e]] ->
[
eq [car [e]; QUOTE] -> cadr [e];
eq [car [e]; ATOM] -> atom [eval [cadr [e]; a]];
eq [car [e]; EQ] -> [eval [cadr [e]; a] = eval [caddr [e]; a]];
eq [car [e]; COND] -> evcon [cdr [e]; a];
eq [car [e]; CAR] -> car [eval [cadr [e]; a]];
eq [car [e]; CDR] -> cdr [eval [cadr [e]; a]];
eq [car [e]; CONS] -> cons [eval [cadr [e]; a]; eval [caddr [e]; a]];
T -> eval [cons [assoc [car [e]; a]; evlis [cdr [e]; a]]; a]
];
eq [caar [e]; LABEL] -> eval [ cons [caddar [e]; cdr [e]];
cons [list [cadar [e]; car [e]]; a]
];
eq [caar [e]; LAMBDA] -> eval [caddar [e];
append [pair [cadar [e];
evlis [cdr [e]; a]
];
a
]
]
]
|
Similar error in Memo 8.
It is very interesting that error existed also in the third document,
memo of AI project on MIT, 1959, which contains different definition of eval:
|
See also Mark Stock's link in comments of this post.
|
An editor which shows matching parentheses is a useful tool here. The missing close parenstheses appear to be in the last two eq clauses -- the ones with LABEL and LAMBDA. Change to:
ReplyDeleteeq [caar [e]; LABEL] -> eval [cons [caddar [e]; cdr [e]]; cons [list [cadar [e]; car [e]; a]]);
eq [caar [e]; LAMBDA] -> eval [caddar [e]; append [pair [cadar [e]; evlis [cdr [e]; a]; a]]])
I've used ')' to show where I inserted characters. I note that Paul Graham's implementation of eval in Common Lisp has parenthenses in these places.
If I am reading Paul Graham's implementation of eval in Common Lisp correctly, I think that the ')' goes in a different place for LABEL
ReplyDeleteeq [caar [e]; LABEL] -> eval [cons [caddar [e]; cdr [e]]; cons [list [cadar [e]; car [e]); a]];
I think that the second cons function takes two parameters:
list [cadar [e]; car [e]]
a