lambda - 艾伦·凯的评估/应用爱因斯坦时刻

Question

艾伦·凯说过。
所讨论的代码是eval&apply的第1个版本，它看起来与现代lisp（我知道的）非常相似。
因为正确的答案可能是已知的，但却丢失了（我的google fu很不错，我已经搜索了至少20分钟）
我会尽快给第一个正确答案（我会看编辑时间，所以不要作弊）250分奖金。
我建议其他人也为赏金捐款，
记得在上面的视频中，他说这些东西让人想起他发现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时所处的环境。
文本中的代码是用M表达式编写的我在做一个翻译，把m-expressions翻译成S-expressions（lisp代码）@Alan Kay。
不管怎样，这是第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)))))))

Answer 1

有两个不同的问题：
第一：动态绑定是一个bug
不知道他是什么意思，但通常在麦卡锡的EVAL中，使用dynamic binding可以被视为一个bug他不为变量实现词法范围。例如，这里会显示错误：
http://www-formal.stanford.edu/jmc/recursive/node3.html
请参见函数maplist和diff。两者都使用x。这不会如图所示工作，因为早期的Lisp提供了动态绑定。
一个更简单的例子，它表明求值器使用动态绑定
注意eval.的用法，这是麦卡锡的eval。

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

这将返回 FOO，因为 X的值是从动态绑定中查找的。
如果我们查看代码，它要求我们将函数作为列表传递： '(lambda () x))。这将计算为一个列表。稍后将通过 (f)-调用该列表，不带任何参数。然后，该列表被解释为lambda表达式， x将通过查看 x的当前动态绑定来解析 x引入了 FOO到 ((lambda (x) (f)) '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世界中，这基本上是在方案中解决的，它默认地引入了词汇绑定。这个词汇绑定然后允许使用闭包来模拟对象系统（凯可能发现有用的东西）。看报纸：1975年的。
在普通LISP中，它默认使用象Lisp方言方案那样的词法范围，上面的例子将是一个错误（这里我们使用普通LISP的 eval，略微更改代码，使之成为合法的普通LISP代码）：

CL-USER 43 > (eval '((lambda (f)
                       ((lambda (x) (funcall f))
                        'foo))
                     (function (lambda () x))))

Error: The variable X is unbound.

在common lisp（and scheme）中可以看到， (lambda () x)是一个真正的lambda表达式，而不是一个带引号的列表， (function (lambda () x))计算为一个函数对象-如果有绑定，那么它是一个闭包-一个函数对象及其绑定。传递这个函数object/clojure，然后通过 (funcall f)调用它由于 x不引用任何内容（它是一个自由变量），并且不通过绑定查找，因此在执行代码时会发生错误。这就是我们想要的：我们需要词汇绑定，而我们的代码中的这个错误是一个后果。这个错误并没有在麦卡锡最初的lisp中发生，这是错误的一个结果。修复这个bug（需要十多年才能完全满足），使我们能够使用LISP中的闭包——就像普通LISP，它从方案中学习到。
可能Kay也将动态绑定视为一个bug这是一个非常基本的问题，理解/解决它，有助于设计和开发更好的编程语言。
注意，典型的早期Smalltalk实现（例如Xerox的Smalltalk 80）也使用动态绑定。
麦卡锡关于那个虫子的事
在 SCHEME: An Interpreter for Extended Lambda Calculus（1979年）麦卡锡写道（粗体由我）：
自由变量毫无疑问，James R.Slagle编写了以下LISP函数定义，并在它不能正常工作时抱怨：
函数的目标是找到满足p[x]的x的子表达式，并返回f[x]。如果搜索失败，则将计算不带参数的连续函数u[]，并返回其值。困难在于，当内部递归发生时，car[x]需要的值是外部值，但实际使用的是内部值。在现代术语中，词法范围被要求，动态范围被获得。
我必须承认，我认为这只是一个错误，并表示相信史蒂夫罗素将很快解决它。他确实解决了这个问题，但发明了所谓的FunARG设备，它把词汇环境和功能论证结合起来。类似的困难后来出现在Algol 60算法中，而Russell算法是解决这个问题的更全面的方法之一虽然它在解释器中工作得很好，但是在编译的代码中，全面性和速度似乎是对立的，这导致了一系列的妥协。不幸的是，时间不允许写一个附录给出问题的历史，感兴趣的读者被称为（摩西1970年）开始的地方。（大卫·帕克告诉我帕特里克·费舍尔也参与了FUNARG设备的开发）。
这与第二个问题无关：
第二：同一本书中eval的不同版本中的bug
参见paul graham的 From LISP 1 to LISP 1.5一书后面关于eval定义中的bug的讨论。在第12页中，您可以找到麦卡锡代码中的一个错误的描述，该错误导致对命名函数的参数进行双重求值。