Alan Kay 的 Eval/Apply Einstein Moment [英] Alan Kay's Eval/Apply Einstein Moment
问题描述
Alan Kay 说 仔细阅读代码并找到第 13 页代码中的第一个也是唯一的错误Lisp 1.5 手册，帮助他将计算机科学的理解提高了 100 倍.
有问题的代码是 eval 的第一个版本 &apply 看起来有点像现代 lisp(我知道).
因为可能知道正确答案但丢失了(我的 google-fu 不错，我至少搜索了 20 分钟)我将尽快奖励第一个正确答案(我将查看编辑时间，所以不要试图作弊)250 点悬赏.
我建议其他人也为赏金做出贡献，记得上面的视频 Alan Kay 说这东西让人想起环境 Einstein 在发现 相对论.
文中的代码是用M-Expressions编写的.我正在研究一个翻译器，将 M 表达式转换为 S 表达式(lisp 代码)@https://github.com/Viruliant/MccarthyMCEval-1.5.
无论如何，这里是第 13 页的译文:
;______________________________________Lisp Meta-Circular Evaluator S-Expression;这段代码是按照它在 Lisp 1.5 手册第 10-13 页上出现的顺序编写的;并从 m 表达式转换为 s 表达式(标签 mc.equal (lambda (x y)(mc.cond((atom x) ((mc.cond ((atom y) (eq x y)) ((quote t) (quote f)))))((等于(car x)(car y)) (等于(cdr x) (cdr y)))((引用 t) (引用 f))))))(标签 mc.subst (lambda (x y z)(mc.cond((等于y z) (x))((原子 z) (z))((quote t) (cons (subst x y (car z))(subst x y (cdr z)))))))(标签 mc.append (lambda (x y)(mc.cond((null x) (y))((quote t) (cons (car x)) (append (cdr x) y)))))(标签 mc.member (lambda (x y)(mc.cond ((null y) (quote f))((等于 x (car y)) (引用 t))((quote t) (成员 x (cdr y))))))(标签 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)))))(标签 mc.assoc (lambda (x a)(mc.cond ((equal (caar a) x) (car a)) ((quote t) (assoc x (cdr a))))))(标签 mc.sub2 (lambda (a z)(mc.cond ((null a) (z)) (((eq (caar a) z)) (cdar a)) ((quote t) (sub2 (cdr a) z))))))(标签 mc.sublis (lambda (a y)(mc.cond ((atom y) (sub2 a y)) ((quote t) (cons (sublis a (car y))))(sublis a (cdr y))))))(标签 mc.evalquote (lambda (fn x)(应用 fn x nil)))(标签 mc.apply (lambda (fn x a))(mc.cond ((原子 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)))))(标签 mc.eval (lambda (e a)(mc.cond((原子 e) (cdr (assoc e a)))((atom (car e)) (mc.cond((eq (car e) 报价) (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))))))(标签 mc.evcon (lambda (c a)(mc.cond((eval (caar c) a) (eval (cadar c) a))((quote t) (evcon (cdr c) a)))))(标签 mc.evlis (lambda (m a)(mc.cond((null m) (nil))((quote t) (cons (eval (car m) a) (evlis (cdr m) a))))))))有两个不同的问题:
第一:动态绑定是一个错误
不确定他的意思，但通常在麦卡锡的EVAL中，动态绑定的使用可以被视为一个bug.他没有为变量实现词法作用域.bug 出现在这里，例如:
http://www-formal.stanford.edu/jmc/recursive/node3.html
查看函数maplist 和diff.两者都使用 x.这不会像所示的那样工作，因为早期的 Lisp 提供了动态绑定.
一个更简单的例子，它表明评估器使用动态绑定
注意 eval. 的使用，这是 McCarthy 的 eval.
CL-USER 36 >(评估.'(((拉姆达(f)((λ (x) (f))'foo))'(拉姆达() x))零)这将返回 FOO，因为 X 的值是从动态绑定中查找的.
如果我们看代码，它需要我们将一个函数作为列表传递:'(lambda () x)).这评估为一个列表.稍后将通过 (f) 调用该列表 - 不带参数.然后该列表被解释为一个 lambda 表达式，并且 x 将通过查看 x 的当前动态绑定来解析.((lambda (x) (f)) 'foo) 引入了 x 到 FOO 的绑定.这将被使用.
在 60 年代的 Lisp 1.5 实现中，人们可能会写一些类似的东西:
(((lambda (f)((λ (x) (f))'foo))(函数(拉姆达()x)))请注意，(function (lambda () x)) 计算结果为标记、动态环境和函数的列表.不幸的是，Lisp 1.5 实现仍然使用动态绑定.所以这已经是正确的方向，但是 bug 那时还没有真正修复.改进了将函数作为参数传递给其他函数的情况.
FUNARG 问题
在 60 年代/70 年代初，我们花了很长时间才弄清楚这个问题.它被称为FUNARG 问题.例如，参见 Joel Moses 论文:LISP 中 FUNCTION 的功能，或为什么会出现 FUNARG 问题应该称为环境问题.有多种解决方案来创建闭包和使用词法绑定.通常解释器使用动态绑定，编译器使用词法绑定.在 Lisp 世界中，这基本上在 Scheme 中得到解决，它默认引入了词法绑定.这个词法绑定允许例如使用闭包来模拟对象系统(Kay可能觉得有用的东西).请参阅论文:SCHEME: An Interpreter for Extended Lambda Calculus 1975 年.
在 Common Lisp 中，它默认使用 词法范围，就像 Lisp 方言方案一样，上面的例子将是一个错误(这里我们使用来自 Common Lisp 的 eval，用稍微更改代码以使其成为合法的 Common Lisp 代码):
CL-USER 43 >(eval '(((lambda (f)((lambda (x) (funcall f))'foo))(函数(拉姆达()x))))错误:变量 X 未绑定.正如你在 Common Lisp(和 Scheme)中看到的，(lambda () x) 是一个真正的 lambda 表达式，而不是一个引用列表 和 (function (lambda () x)) 计算结果为 function object - 如果有 bindings，那么它是一个 closure - 一个函数对象及其绑定.这个函数对象/clojure 被传递，然后通过 (funcall f) 调用.由于 x 不引用任何内容(它是一个 自由变量)并且没有通过绑定查找，因此在执行代码时会发生错误.这就是我们想要的:我们想要词法绑定，而我们代码中的这个错误就是一个结果.这个错误在 McCarthy 的原始 Lisp 中没有发生是 bug 的结果之一.修复这个错误(花了十多年才完全满意)，使我们能够在 Lisp 中使用闭包——就像在 Common Lisp 中一样，它是从 Scheme 中学到的.
可能 Kay 也将动态绑定视为一个错误.这是一个非常基本的问题，理解/解决它有助于设计和开发更好的编程语言.
请注意，典型的早期 Smalltalk 实现(例如 Xerox 的 Smalltalk 80)也使用了动态绑定.
McCarthy 关于那个错误
在 从 LISP 1 到 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 定义中的错误.在第 12 页上，您可以找到 McCarthy 代码中一个错误的描述，该错误导致对命名函数的参数进行双重评估.
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)))))))
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.
这篇关于Alan Kay 的 Eval/Apply Einstein Moment的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
