20

Alan Kay 说，仔细阅读代码并在 Lisp 1.5 手册第 13 页的代码中找到第一个也是唯一一个错误，帮助他更好地理解计算机科学 100 倍。

有问题的代码是eval&的第一个版本，apply它看起来很像现代 lisp（我知道）。

由于正确答案可能已知但丢失（我的 google-fu 很不错，我至少搜索了 20 分钟）我将奖励第一个正确答案（我将查看编辑时间，所以不要试图作弊）尽快获得 250 点赏金。

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

文中的代码是用 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)))))))
4

4 回答 4

14

有两个不同的问题：

第一：动态绑定作为一个bug

不确定他的意思，但一般在 McCarthy 的EVAL使用中dynamic binding可以看作是一个bug。他没有为变量实现词法作用域。该错误例如在这里显示：

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

见函数maplist和diff。两者都使用x. 如图所示，这不会起作用，因为早期的 Lisp 提供了动态绑定。

一个更简单的例子，它表明评估器使用动态绑定

注意使用eval.，这是eval来自 McCarthy 的。

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

这将返回FOO，因为 的值X是从动态绑定中查找的。

如果我们查看代码，它需要我们将函数作为列表传递：'(lambda () x))。这评估为一个列表。稍后将通过(f)- 调用列表，不带任何参数。然后该列表被解释为一个lambda 表达式，x并将通过查看当前动态绑定来解析x. 有xtoFOO引入的绑定((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 论文：LISP 中的函数功能，或为什么应该将 FUNARG 问题称为环境问题。有多种解决方案来创建闭包和使用词法绑定。通常解释器使用动态绑定，编译器使用词法绑定。在 Lisp 世界中，这基本上是在Scheme中解决的，它默认引入了词法绑定。这种词法绑定然后允许例如使用闭包来模拟对象系统（Kay 可能觉得有用的东西）。请参阅论文：SCHEME: An Interpreter for Extended Lambda Calculus from 1975。

在像 Lisp 方言方案一样默认使用词法范围的 Common Lisp 中，上面的示例将是一个错误（这里我们使用eval来自 Common Lisp 的代码，稍微更改了代码以使其合法的 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 中不会发生此错误是该错误的结果之一. 修复这个错误（花了十多年的时间才完全满意），使我们能够在 Lisp 中使用闭包——就像在 Common Lisp 中一样，它是从 Scheme 中学到的。

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

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

麦卡锡关于那个错误

在从 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的bug

参见 Paul Graham 的The Roots of Lisp以讨论本书后面的 EVAL 定义中的错误。在第 12 页上，您可以找到 McCarthy 代码中的一个错误的描述，该错误会导致对命名函数的参数进行双重评估。

于 2016-01-20T00:19:15.483 回答
4

update2：这是论文中的代码，用一些带有列表模式和推导（包括并行推导）的伪代码重写，共有13行代码（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 年更新：）为了支持可变长度参数列表(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]

where当求值到when 和 if匹配时pat | guard -> ....触发。guardtruepat

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

我已经用一些特别的伪代码重写了书中代码（Lisp 1.5 程序员手册）中的原始 M 表达式，这对我来说更容易理解，使用:for consor .，以及模式匹配等，其中紧随其后。

实际上，我看不出它有任何双重评估问题。apply期望它的参数已经被评估，并eval为它评估它们。

我认为这个错误出现在原始论文“符号表达式的递归函数”中（更新：是的！Rainer Joswig 在他的回答末尾提到了 Paul Graham 文章，其中指出这是参考论文中的代码）。

因此，看起来 Alan Kay 的评论很可能是针对动态范围界定的。他提到查看“第 13 页的底部”（所以，在书中），这就是定义所在，它在相同的当前环境evlis中评估列表的元素。查看本书第 70、71 页的解决方案，要求程序员使用 new 关键字显式标记他们的 lambda 定义，创建-tagged 列表将 lambdas 包装在一起（或关闭，如“closure”）评估表单时的环境 - 即该表单的定义环境。functionfunargfunctionlambda

Moses 1970将其称为绑定环境，仅讨论在高阶函数调用中用作函数参数时闭包的隐式创建（因此称为“funarg”绰号）。这也是更现代的 Perl 等词中关于“深浅绑定”（在我看来是滥用术语）的讨论中的上下文。

但是看看书中的那个扩展版本，它似乎允许程序员显式地创建这样的实体，将它们存储在一个变量中，就像任何其他第一类实体一样传递它。然后，当应用闭包（一个funarg-tagged 列表）时，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
于 2016-01-20T21:05:16.520 回答
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是缺点和y原子的情况

编辑：assoc如果找不到密钥，也将无法返回 nil。

于 2016-01-21T19:10:25.503 回答
4

它很可能是对动态范围错误的引用（一个错误，因为如果预期它类似于 lambda 演算，结果没有做它应该做的事情）：

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)))
                                      ;^^^^^^^^^^^^^^^^^^^^^^

但这根本没有帮助。修复不能只在那儿，在那个地方；你需要了解整个事情是如何工作的并真正遵循它，看看错误是如何发生的。

作为正确方向的快速提示，这里的问题是 lambda 函数的主体是在作为当前eval环境扩展的环境（ 的第二个参数）中评估的，从而产生动态范围。解决它——实现词法作用域——在这里不仅仅涉及编辑，因为关于函数词法作用域的信息已经丢失。

（任何关于 PL 的随机体面的书都应该有更多的细节。在 Lisp 的上下文中，深入挖掘确实会让你了解整个 FUNARG 的东西。）

于 2016-01-20T15:55:14.777 回答