艾伦·凯的 Eval/Apply 爱因斯坦时刻
Alan Kay's Eval/Apply Einstein Moment
有问题的代码是 eval 和 apply 的第一个版本，它看起来有点像现代 lisp（我知道）。
因为正确答案可能已知但已丢失（我的 google-fu 很不错，我至少搜索了 20 分钟）
我将尽快奖励第一个正确答案（我会查看编辑时间，所以不要试图作弊）250 点赏金。
我建议其他人也为赏金做出贡献，
记得上面的视频 Alan Kay said this stuff is reminiscent of the environment Einstein was in when he discovered the Theory of Relativity.
文中的代码是用M-Expressions写的。我正在开发一个翻译器，将 M 表达式翻译成 S 表达式（lisp 代码）@https://github.com/Viruliant/MccarthyMCEval-1.5。
无论如何，这里是第 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)))))))
有两个不同的问题：
第一：动态绑定作为一个bug
不太清楚他的意思，但大体上在麦卡锡的EVAL中使用dynamic binding可以看作是一个bug。他没有为变量实现词法作用域。例如，bug 出现在此处：
http://www-formal.stanford.edu/jmc/recursive/node3.html
查看函数 maplist 和 diff。两者都使用 x。这不会像所示那样工作，因为早期的 Lisp 提供了动态绑定。
一个更简单的例子，说明求值器使用了动态绑定
注意 eval. 的用法，这是 McCarthy 的 eval。
CL-USER 36 > (eval. '((lambda (f)
((lambda (x) (f))
'foo))
'(lambda () x))
nil)
这个returnsFOO，因为X的值是从动态绑定中查找的。
如果我们查看代码，它要求我们将函数作为列表传递：'(lambda () x))。这将评估为一个列表。稍后将通过 (f) 调用列表 - 不带参数。然后该列表被解释为 lambda 表达式 并且 x 将通过查看 x 的当前动态绑定来解析。 ((lambda (x) (f)) 'foo) 引入了 x 到 FOO 的绑定。到时候用到这个
在 60 年代的 Lisp 1.5 实现中，可能会写出类似于：
((lambda (f)
((lambda (x) (f))
'foo))
(function (lambda () x)))
请注意，(function (lambda () x)) 评估为标记、动态环境和函数的列表。不幸的是，Lisp 1.5 实现仍然使用 动态绑定 。所以这已经是正确的方向了，但是 bug 当时并没有真正修复。改善了将函数作为参数传递给其他函数的情况。
FUNARG 问题
在 60 年代/70 年代初期花了相当长的时间才弄清楚这个问题。它被称为 FUNARG 问题。例如，参见 Joel Moses 的论文：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 从 1975 年开始。
在 Common Lisp 中，默认使用 词法作用域，就像 Lisp 方言 Scheme 一样，上面的例子会出错（这里我们使用 Common Lisp 中的 eval , 稍微修改代码使其成为合法的 Common Lisp 代码):
CL-USER 43 > (eval '((lambda (f)
((lambda (x) (funcall f))
'foo))
(function (lambda () x))))
Error: The variable X is unbound.
正如您在 Common Lisp（和 Scheme）中看到的那样，(lambda () x) 是一个真正的 lambda 表达式，而不是 引用列表 和 (function (lambda () x)) 评估为 函数对象 - 如果有 绑定 ，那么它是一个 闭包 - 函数对象及其绑定。这个函数对象/clojure 被传递，然后通过 (funcall f) 调用。由于 x 没有引用（它是一个 自由变量 ）并且没有通过绑定查找，因此在执行代码时会出错。这就是我们想要的：我们想要词法绑定，而我们代码中的这个错误就是结果。这个错误在 McCarthy 的原始 Lisp 中没有发生是 bug 的结果之一。修复这个错误（花了十多年才完全满意），使我们能够在 Lisp 中使用 closures——就像在从 Scheme 中学到的 Common Lisp 中一样。
可能 Kay 也将 动态绑定 视为 bug。这是一个非常基本的问题，understanding/solving 它有助于设计和开发更好的编程语言。
请注意，典型的早期 Smalltalk 实现（例如 Xerox 的 Smalltalk 80）也使用动态绑定。
McCarthy 关于那个 bug
在 From LISP 1 to LISP 1.5 (1979) 中，麦卡锡写道（由我加粗）：
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).
这与第二个问题无关：
其二：同一本书不同版本EVAL的bug
请参阅 Paul Graham 的 The Roots of Lisp，了解本书后面对 EVAL 定义中错误的讨论。在第 12 页上，您找到了对 McCarthy 代码中一个错误的描述，该错误会导致对命名函数的参数进行双重计算。
这很可能是对动态范围错误的引用（自从
结果并没有按照预期的方式去做
类似于 lambda 演算):
eq[car[fn];LAMBDA] -> eval[caddr[fn];pairlis[cadr[fn];x;a]];
%^^^^^^^^^^^^^^^^^^^^^
并在编辑后的 semi-lisp-like 文本中：
((eq (car fn) lambda) (eval (caddr fn) (parlis (cadr fn) x a)))
;^^^^^^^^^^^^^^^^^^^^^^
但这根本没有帮助。修复必须不只是 那里，在
那个地方；你需要了解整个事情是如何运作的
真的跟着走，看看bug是怎么来的
作为正确方向的快速提示，这里的问题是
lambda 函数的主体在环境中进行评估（第二个
eval) 的参数是 current 环境的扩展，
导致动态范围。解决它---实现词法作用域
--- 涉及的不仅仅是这里的编辑，因为有关的信息
函数的词法范围已经丢失。
（任何关于 PL 的随机体面的书都应该有更多的细节。在
Lisp 的上下文，深入挖掘确实会让你了解整个 FUNARG
东西。）
update2: 这是论文中的代码，在所有 13[= 中用列表模式和理解（包括并行理解）用一些伪代码重写82=] 行代码（15 添加了 FUNARG 设备，下面讨论），全部在一个定义中：
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:) 以支持可变长度参数列表 (lambda p ....)，我们添加另一个子句，
[[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]
其中 pat | guard -> .... 在 guard 计算为 true 时触发 当 pat 匹配时。
更新： 这里有一个 video by Philip Wadler 他在 22:30 中谈到了那个“错误”，以及如何使用“错误的变量”（对于用于评估 lambda-body 的环境，a 而不是随后的伪代码中的 env）导致“动态绑定”而不是比“静态出价”。
我已经 re-written 书中代码（Lisp 1.5 程序员手册）中的原始 M-expressions 在一些 ad-hoc 伪代码中，这对我来说更容易理解，使用 : for cons or ., with pattern-matching, 等等，紧随其后。
实际上，我看不出任何 double-evaluation 问题。 apply 期望它的参数已经被评估，并且 eval 为它评估它们。
我认为该错误在原始论文中 "Recursive Functions of Symbolic Expressions"（更新： 是的！Rainer Joswig 在他的回答末尾提到了 Paul Graham 文章，其中指出这是参考论文中的代码)。
所以看起来 Alan Kay 的评论确实很可能是指动态范围界定。他提到查看“在第 13 页的底部”（因此， 在书中 ），这就是 evlis 定义所在的位置，它评估列表的元素，当前 环境。查看本书的第 70、71 页以了解此问题的解决方案，要求程序员 显式 使用新关键字 function 标记其 lambda 定义，以创建 funarg -tagged 列表将 lambda 与（或 closing 结束，如“闭包”）一起评估 function 形式时的环境 - 即定义环境lambda表格。
Moses 1970 称之为 binding 环境，仅讨论在 higher-order 函数调用中用作函数参数时隐式创建闭包（因此 "funarg" 绰号）。这也是 Perl 等术语中关于“深度和浅层绑定”（在我看来滥用术语）的更多现代讨论的背景。
但是看看书中的那个扩展版本，它似乎允许程序员明确地创建这样的实体，将它们存储在一个变量中，像任何一样传递它其他 第一个 class 实体。然后，当应用闭包（一个 funarg 标记列表）时，lambda 定义在 它的 环境中计算，而不是当前环境（Moses 1970 称之为 激活环境）。这让人非常接近于令人信服地模仿动态绑定的词法范围。
这是伪代码，遵循书中的代码：
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
看起来像
equal[x;y] =
[atom[x] -> [atom[y] -> eq[x;y]; T -> F];
equal[car[x];car[y]] -> equal[cdr[x];cdr[y]];
T -> F]
不处理 x 是缺点而 y 是原子的情况
编辑：如果找不到密钥，assoc 也将无法 return nil。
有问题的代码是 eval 和 apply 的第一个版本，它看起来有点像现代 lisp（我知道）。
因为正确答案可能已知但已丢失（我的 google-fu 很不错，我至少搜索了 20 分钟） 我将尽快奖励第一个正确答案（我会查看编辑时间，所以不要试图作弊）250 点赏金。
我建议其他人也为赏金做出贡献， 记得上面的视频 Alan Kay said this stuff is reminiscent of the environment Einstein was in when he discovered the Theory of Relativity.
文中的代码是用M-Expressions写的。我正在开发一个翻译器，将 M 表达式翻译成 S 表达式（lisp 代码）@https://github.com/Viruliant/MccarthyMCEval-1.5。
无论如何，这里是第 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)))))))
有两个不同的问题：
第一：动态绑定作为一个bug
不太清楚他的意思，但大体上在麦卡锡的EVAL中使用dynamic binding可以看作是一个bug。他没有为变量实现词法作用域。例如，bug 出现在此处：
http://www-formal.stanford.edu/jmc/recursive/node3.html
查看函数 maplist 和 diff。两者都使用 x。这不会像所示那样工作，因为早期的 Lisp 提供了动态绑定。
一个更简单的例子，说明求值器使用了动态绑定
注意 eval. 的用法，这是 McCarthy 的 eval。
CL-USER 36 > (eval. '((lambda (f)
((lambda (x) (f))
'foo))
'(lambda () x))
nil)
这个returnsFOO，因为X的值是从动态绑定中查找的。
如果我们查看代码，它要求我们将函数作为列表传递：'(lambda () x))。这将评估为一个列表。稍后将通过 (f) 调用列表 - 不带参数。然后该列表被解释为 lambda 表达式 并且 x 将通过查看 x 的当前动态绑定来解析。 ((lambda (x) (f)) 'foo) 引入了 x 到 FOO 的绑定。到时候用到这个
在 60 年代的 Lisp 1.5 实现中，可能会写出类似于：
((lambda (f)
((lambda (x) (f))
'foo))
(function (lambda () x)))
请注意，(function (lambda () x)) 评估为标记、动态环境和函数的列表。不幸的是，Lisp 1.5 实现仍然使用 动态绑定 。所以这已经是正确的方向了，但是 bug 当时并没有真正修复。改善了将函数作为参数传递给其他函数的情况。
FUNARG 问题
在 60 年代/70 年代初期花了相当长的时间才弄清楚这个问题。它被称为 FUNARG 问题。例如，参见 Joel Moses 的论文：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 从 1975 年开始。
在 Common Lisp 中，默认使用 词法作用域，就像 Lisp 方言 Scheme 一样，上面的例子会出错（这里我们使用 Common Lisp 中的 eval , 稍微修改代码使其成为合法的 Common Lisp 代码):
CL-USER 43 > (eval '((lambda (f)
((lambda (x) (funcall f))
'foo))
(function (lambda () x))))
Error: The variable X is unbound.
正如您在 Common Lisp（和 Scheme）中看到的那样，(lambda () x) 是一个真正的 lambda 表达式，而不是 引用列表 和 (function (lambda () x)) 评估为 函数对象 - 如果有 绑定 ，那么它是一个 闭包 - 函数对象及其绑定。这个函数对象/clojure 被传递，然后通过 (funcall f) 调用。由于 x 没有引用（它是一个 自由变量 ）并且没有通过绑定查找，因此在执行代码时会出错。这就是我们想要的：我们想要词法绑定，而我们代码中的这个错误就是结果。这个错误在 McCarthy 的原始 Lisp 中没有发生是 bug 的结果之一。修复这个错误（花了十多年才完全满意），使我们能够在 Lisp 中使用 closures——就像在从 Scheme 中学到的 Common Lisp 中一样。
可能 Kay 也将 动态绑定 视为 bug。这是一个非常基本的问题，understanding/solving 它有助于设计和开发更好的编程语言。
请注意，典型的早期 Smalltalk 实现（例如 Xerox 的 Smalltalk 80）也使用动态绑定。
McCarthy 关于那个 bug
在 From LISP 1 to LISP 1.5 (1979) 中，麦卡锡写道（由我加粗）：
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).
这与第二个问题无关：
其二：同一本书不同版本EVAL的bug
请参阅 Paul Graham 的 The Roots of Lisp，了解本书后面对 EVAL 定义中错误的讨论。在第 12 页上，您找到了对 McCarthy 代码中一个错误的描述，该错误会导致对命名函数的参数进行双重计算。
这很可能是对动态范围错误的引用（自从 结果并没有按照预期的方式去做 类似于 lambda 演算):
eq[car[fn];LAMBDA] -> eval[caddr[fn];pairlis[cadr[fn];x;a]];
%^^^^^^^^^^^^^^^^^^^^^
并在编辑后的 semi-lisp-like 文本中：
((eq (car fn) lambda) (eval (caddr fn) (parlis (cadr fn) x a)))
;^^^^^^^^^^^^^^^^^^^^^^
但这根本没有帮助。修复必须不只是 那里，在 那个地方；你需要了解整个事情是如何运作的 真的跟着走，看看bug是怎么来的
作为正确方向的快速提示，这里的问题是
lambda 函数的主体在环境中进行评估（第二个
eval) 的参数是 current 环境的扩展，
导致动态范围。解决它---实现词法作用域
--- 涉及的不仅仅是这里的编辑，因为有关的信息
函数的词法范围已经丢失。
（任何关于 PL 的随机体面的书都应该有更多的细节。在 Lisp 的上下文，深入挖掘确实会让你了解整个 FUNARG 东西。）
update2: 这是论文中的代码，在所有 13[= 中用列表模式和理解（包括并行理解）用一些伪代码重写82=] 行代码（15 添加了 FUNARG 设备，下面讨论），全部在一个定义中：
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:) 以支持可变长度参数列表 (lambda p ....)，我们添加另一个子句，
[[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]
其中 pat | guard -> .... 在 guard 计算为 true 时触发 当 pat 匹配时。
更新： 这里有一个 video by Philip Wadler 他在 22:30 中谈到了那个“错误”，以及如何使用“错误的变量”（对于用于评估 lambda-body 的环境，a 而不是随后的伪代码中的 env）导致“动态绑定”而不是比“静态出价”。
我已经 re-written 书中代码（Lisp 1.5 程序员手册）中的原始 M-expressions 在一些 ad-hoc 伪代码中，这对我来说更容易理解，使用 : for cons or ., with pattern-matching, 等等，紧随其后。
实际上，我看不出任何 double-evaluation 问题。 apply 期望它的参数已经被评估，并且 eval 为它评估它们。
我认为该错误在原始论文中 "Recursive Functions of Symbolic Expressions"（更新： 是的！Rainer Joswig 在他的回答末尾提到了 Paul Graham 文章，其中指出这是参考论文中的代码)。
所以看起来 Alan Kay 的评论确实很可能是指动态范围界定。他提到查看“在第 13 页的底部”（因此， 在书中 ），这就是 evlis 定义所在的位置，它评估列表的元素，当前 环境。查看本书的第 70、71 页以了解此问题的解决方案，要求程序员 显式 使用新关键字 function 标记其 lambda 定义，以创建 funarg -tagged 列表将 lambda 与（或 closing 结束，如“闭包”）一起评估 function 形式时的环境 - 即定义环境lambda表格。
Moses 1970 称之为 binding 环境，仅讨论在 higher-order 函数调用中用作函数参数时隐式创建闭包（因此 "funarg" 绰号）。这也是 Perl 等术语中关于“深度和浅层绑定”（在我看来滥用术语）的更多现代讨论的背景。
但是看看书中的那个扩展版本，它似乎允许程序员明确地创建这样的实体，将它们存储在一个变量中，像任何一样传递它其他 第一个 class 实体。然后，当应用闭包（一个 funarg 标记列表）时，lambda 定义在 它的 环境中计算，而不是当前环境（Moses 1970 称之为 激活环境）。这让人非常接近于令人信服地模仿动态绑定的词法范围。
这是伪代码，遵循书中的代码：
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
看起来像
equal[x;y] =
[atom[x] -> [atom[y] -> eq[x;y]; T -> F];
equal[car[x];car[y]] -> equal[cdr[x];cdr[y]];
T -> F]
不处理 x 是缺点而 y 是原子的情况
编辑：如果找不到密钥，assoc 也将无法 return nil。