艾伦·凯的Eval/Apply爱因斯坦时刻

Question

Alan Kay说仔细阅读Lisp 1.5手册第13页上的代码，并找到唯一的一个bug，帮助他将计算机科学的理解提高了100倍。

所涉及的代码是第一个发布的eval和apply，看起来与现代lisp有些相似（据我所知）。

由于正确答案可能已知但已丢失（我的谷歌搜索能力还不错，至少已经搜了20分钟），我将尽快授予第一个正确答案（我将查看编辑时间，因此不要试图作弊）250点奖励。

我建议其他人也为赏金做出贡献，记住视频中艾伦·凯所说的，这些东西让人想起爱因斯坦发现相对论时所处的环境。

文本中的代码是用M-Expressions编写的。我正在开发一个翻译器，将M-Expressions翻译成S-Expressions（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)))))))

- GlassGhost

---

你认为可能是因为eval依赖于apply来评估函数位置中的一些内容，而不是直接评估它吗？也就是说，(eval '(foo x y z) a) 调用的是 (apply 'foo (evlist '(x y z) a) a)，而不是 (apply (eval 'foo a) (evlist '(x y z) a) a)。 - Joshua Taylor

@JoshuaTaylor 我不知道，但是希望在我为此设置250点赏金后，会有足够的人关注这个问题，也许我们可以达成对于这个bug的共识。 - GlassGhost

我认为你误解了他。他感到启发的不是“通过”找到错误，而是在紧密跟踪代码并巧合地发现“一个错误”的两个小时之后。也就是说，影响他的不是那个错误，而是整个代码。 - Will Ness

@WillNess 我从未说过我不想全面理解代码，我只是好奇这个 bug 是什么，并且想传播这个精彩的代码。 - GlassGhost

“无论如何，这是来自第13页的引用。” “不，现在不是。” 你知道你不能这样突然转换问题。 - Will Ness

@WillNess更新了问题，加入了单词“翻译”，我仍在努力完善自动翻译器，但实际上大部分翻译都是手动完成的，事实上第10页明确显示了从m表达式到s表达式的所有简单翻译。如果您发现任何错误，请通知我。如果您仍希望查看原始的m表达式，则可在文本的第13页或https://github.com/Viruliant/MccarthyMCEval-1.5/blob/master/evalquote-original-M-ex.ocr.txt上找到。 - GlassGhost

Answer 1

有两个不同的问题：

第一个：动态绑定被视为错误

不确定他的意思是什么，但一般来说，在麦卡锡的 EVAL 中使用 动态绑定 可以被视为一个错误。他没有为变量实现 词法作用域。例如，在这里可以看到 错误：

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

请参见函数 maplist 和 diff。 由于早期Lisp提供了动态绑定，因此这些都不能正常工作。

一个更简单的例子，展示了求值器使用动态绑定

请注意使用的 eval.， 它是来自麦卡锡的 eval。

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

由于从动态绑定中查找X的值，因此这会返回FOO。

如果我们看一下代码，它要求我们将一个函数作为列表传递：'(lambda () x))。这个表达式被计算为一个列表。稍后这个列表将通过(f)进行调用 - 没有参数。然后该列表将被解释为一个lambda表达式，并通过查找当前动态绑定的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 实现仍然使用了 动态绑定。因此，这已经是正确的方向，但那时并没有真正修复 错误。当将函数作为参数传递给其他函数时，情况有所改善。

FUNARG 问题

在60年代/70年代初期，人们花费了相当长的时间来解决这个问题。它被称为 FUNARG 问题。例如，可以查看 Joel Moses 的论文：The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem。有各种解决方案来创建 闭包 并使用词法绑定。通常解释器使用动态绑定，而编译器使用词法绑定。在 Lisp 世界中，这基本上在 Scheme 中得到了解决，它默认引入了 词法绑定。然后，这个 词法绑定 允许例如使用 闭包 来模拟 对象系统（Kay 可能认为这很有用）。请参见1975年的论文：SCHEME: An Interpreter for Extended Lambda Calculus。

在 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))计算为一个函数对象 - 如果有绑定，则它是一个闭包 - 一个函数对象及其绑定。这个函数对象/封闭值被传递，然后通过(funcall f)稍后调用。由于x指向无何物（它是一个自由变量）并且不通过绑定查找，所以执行代码时会发生错误。这就是我们想要的：我们想要词法绑定，我们代码中的这个错误是一个后果。在麦卡锡最初的Lisp中，这个错误没有发生，这是一个bug的结果之一。修复这个错误（需要超过十年才能完全满意），使我们能够在Lisp中使用闭包 - 就像在从Scheme学到它的Common Lisp中一样。

可能Kay也认为动态绑定是一个bug。这是一个非常基本的问题，理解/解决它有助于设计和开发更好的编程语言。

请注意，典型的早期Smalltalk实现（例如Xerox的Smalltalk 80）也使用了动态绑定。

麦卡锡关于这个bug的说法

在From LISP 1 to LISP 1.5（1979）中，麦卡锡写道（我加粗）：

d. 自由变量。James R. Slagle天真地编写了以下LISP函数定义，并抱怨它不能正常工作：

函数的目的是查找满足p[x]的x的子表达式并返回f[x]。如果搜索不成功，则将计算没有参数的连续函数u[]并返回其值。困难在于当发生内部递归时，car[x]的值是外部值，但实际使用的是内部值。用现代术语来说，需要词法作用域，但获得的是动态作用域。

我必须承认，我把这个困难看作是一个故障，并表达了对 Steve Russell 很快解决它的信心。他通过发明所谓的 FUNARG 设备来修复它，该设备将词法环境与函数参数一起使用。类似的困难后来出现在 Algol 60 中，Russell 的解决方案成为问题的更全面的解决方案之一。虽然它在解释器中运行良好，在编译代码中，全面性和速度似乎是相互矛盾的，并导致了一系列妥协。不幸的是，时间不允许编写附录来说明问题的历史，感兴趣的读者可以参考（Moses 1970）作为开始。（David Park 告诉我 Patrick Fischer 也参与了开发 FUNARG 设备）。

这与第二个问题无关：

第二个问题：同一本书中不同版本的 EVAL 中的错误

请参阅 Paul Graham 的Lisp 的根源 ，讨论了书中 EVAL 定义中的 bug。在第12页上，你会发现描述 McCarthy 代码中的一个漏洞，它导致对命名函数的参数进行了双重评估。

- Rainer Joswig

---

我相信这就是它！但是[evlis[cdr var1]var2]有多个实例，我仍然不确定哪一个。22、23和31行 https://github.com/Viruliant/MccarthyMCEval-1.5/blob/master/evalquote-original-M-ex.ocr.txt#L22 - GlassGhost

@GlassGhost：我更详细地解释了这个错误/问题是什么。 - Rainer Joswig

@WillNess：在Common Lisp中，LAMBDA是一个宏，它会扩展成(function (lambda ...))。这没有任何区别。 - Rainer Joswig

请参见第71页上的eq[car[form];FUNCTION]->list[FUNARG;cadr[form];a];。 - Will Ness

@WillNess：那是解释器使用的动态环境。 - Rainer Joswig

Answer 2

这很可能是对动态作用域bug的引用（自lambda演算以来的一个bug，因为结果并不像预期的那样运行）：

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

并在修改后的类似Lisp的文本中：

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

但是这并没有帮助到我们。修复问题不应该只定位于 那里，在那一个地方；你需要了解整个工作原理并真正跟进来查看 bug 是如何发生的。

作为正确方向上的快速提示，问题在于 lambda 函数体在 eval 的第二个参数所表示的环境中被计算，这个环境是当前环境的扩展，导致动态作用域。要解决它——实现词法作用域——需要更多编辑，因为函数的词法作用域信息已经丢失。

(任何一本与 PL 相关的好书都应该有更多细节。在 Lisp 的情况下，深入研究会让你了解整个 FUNARG 事物。)

- Eli Barzilay

Answer 3

更新2: 这是论文中的代码，使用一些带有列表模式和理解（包括并行理解）的伪代码进行重写，在所有13行代码（包括下面讨论的FUNARG设备，共15行代码）中，都在这里定义：

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更新：）为了支持使用（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]

当guard计算为true并且pat匹配时，pat | guard -> ....将触发。

---

更新：这里有一个Philip Wadler的视频，他在视频中谈到了那个“bug”，以及如何使用“错误的变量”（在伪代码中，用于评估lambda-body的环境，使用a而不是env）导致“动态绑定”而不是“静态绑定”（在22:30处）。

---

我已经将《Lisp 1.5程序员手册》中的原始M表达式以一些临时伪代码重写，使用:代替cons或.，带有模式匹配等，这样更容易跟进，下面即将展示。实际上，我看不出其中存在双重评估问题。apply期望其参数已经被评估，而eval会为其评估。我认为错误在于原始论文"Symbolic Expressions的递归函数"（更新：是的！Rainer Joswig在他的答案末尾提到了Paul Graham文章，指出这是针对论文中的代码）。

因此，很明显艾伦·凯的评论是指动态作用域。他提到在书中“在第13页底部”（所以，在书中），那里有evlis定义，它在相同的当前环境中评估列表元素。查看该书第70、71页，以获得解决方案，要求程序员使用新关键字function显式标记其lambda定义，创建打包lambda和环境（或闭合）的funarg标记列表，该环境在function形式被评估时 - 即lambda形式的定义环境。

Moses 1970将其称为绑定环境，仅讨论在高阶函数调用中用作函数参数时隐式创建闭包的情况（因此有了"funarg"名称）。这也是当代更多关于Perl等语言中"深度和浅度绑定"（在我看来误用术语）的背景。

但是，在书中查看扩展版本后，程序员似乎可以明确地创建这些实体，将它们存储在变量中，并像任何其他第一类实体一样传递它们。然后，当应用闭包（一个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

- Will Ness

Answer 4

看起来像是

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为cons且y为原子的情况。

编辑：如果未找到键，则assoc也将无法返回nil。

- Lex