lambda - Alan Kay の Eval/Apply Einstein Moment

Question

Alan Kay 氏は、コードをよく読んで、Lisp 1.5 マニュアルの 13 ページにあるコードの唯一のバグを見つけたことが、コンピューター サイエンスの理解を 100 倍向上させたと述べています。

問題のコードはeval&の最初のリリースで、applyモダンな Lisp のように見えます (私が認識しています)。

正解はわかっている可能性がありますが、失われているため (私の Google-fu はまともで、少なくとも 20 分間検索しました)、1 番目の正解を授与します (編集時間を確認するので、ごまかそうとしないでください)。できるだけ早く 250 ポイントのバウンティ。

他の人も賞金に貢献することをお勧めします.上のビデオから、アラン・ケイは、このものはアインシュタインが相対性理論を発見したときの環境を思い起こさせると言ったことを思い出してください.

本文中のコードはM式で書かれています。私は、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)))))))

Answer 1

2 つの異なる問題があります。

最初: バグとしての動的バインディング

彼が何を意味するのかはわかりませんが、一般的に McCarthy のEVAL使用法はbugdynamic bindingと見なすことができます。彼は変数の字句スコープを実装していません。バグは、たとえば次のように表示されます。

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

関数maplistとを参照してくださいdiff。どちらも使用しますx。初期の Lisp は動的バインディングを提供しているため、これは示されているようには機能しません。

エバリュエーターが動的バインディングを使用することを示す、より単純な例

McCarthyeval.のの使用に注意してください。eval

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

FOOの値はX動的バインディングから検索されるため、これは を返します。

コードを見ると、関数をリストとして渡す必要があります: '(lambda () x)). これはリストに評価されます。(f)後でリストは- 引数なしで呼び出されます。次に、リストはラムダ式として解釈さxれ、 の現在の動的バインディングを調べることで解決されxます。によって導入されたxtoのバインディングがあります。その時はこれが使われます。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、または Why the FUNARG Problem Should be Called the Environment Problemを参照してください。クロージャーを作成し、字句バインディングを使用するためのさまざまなソリューションがありました。多くの場合、インタープリターは動的バインディングを使用し、コンパイラーは字句バインディングを使用しました。Lisp の世界では、これは基本的にSchemeで解決され、デフォルトで字句バインディングが導入されました。このレキシカル バインディングにより、たとえば、クロージャを使用してオブジェクト システムをエミュレートできます。(Kay がおそらく便利だと思うもの)。論文を参照してください: SCHEME: An Interpreter for Extended Lambda Calculus from 1975.

Lisp方言スキームのようにデフォルトで字句スコープを使用するCommon Lispでは、上記の例はエラーになります(ここではevalCommon 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)実際のラムダ式であり、関数オブジェクトに評価されます- bindingsがある場合、それはクロージャです- 関数オブジェクトとそのバインディングです。この関数オブジェクト / clojure が渡され、後で を介して呼び出されます。は何も参照せず (自由変数です)、バインディングを介して参照されないため、コードを実行するとエラーが発生します。それが私たちが望んでいることです: レキシカル バインディングが必要であり、コード内のこのエラーはその結果です。McCarthy のオリジナルの Lisp でこのエラーが発生しないのは、バグの結果の 1 つです。(function (lambda () x))(funcall f)x. このバグを修正すると (完全に満足するまでに 10 年以上かかりました)、Scheme から学んだ Common Lisp のように、Lisp でクロージャを使用できるようになりました。

おそらく、Kay も動的バインディングをバグと見なしていたのでしょう。これは非常に基本的な問題であり、それを理解して解決することは、より優れたプログラミング言語の設計と開発に役立ちます。

典型的な初期の Smalltalk 実装 (Xerox の Smalltalk 80 など) も動的バインディングを使用していたことに注意してください。

そのバグについてのマッカーシー

From LISP 1 to LISP 1.5 (1979) McCarthy は次のように書いています (太字は私が書いています)。

d. 自由変数。James R. Slagle は、次の LISP 関数定義をプログラミングし、正しく動作しないと文句を言いました。

この関数の目的は、p[x] を満たす x の部分式を見つけて f[x] を返すことです。検索が失敗した場合、引数のない継続関数 u[] が計算され、その値が返されます。問題は、内部再帰が発生したときに、必要な car[x] の値が外部の値であるのに、実際には内部の値が使用されていたことです。現代の用語では、字句スコープが必要であり、動的スコープが取得されました。

私はこの問題を単なるバグと見なし、Steve Russell がすぐに修正してくれると確信していたことを告白しなければなりません。彼はそれを修正しましたが、関数引数とともに字句環境を取る、いわゆる FUNARG デバイスを発明することによってでした。同様の問題が後に Algol 60 に現れ、ラッセルのものは問題に対するより包括的な解決策の 1 つであることが判明しました。インタープリターではうまく機能しましたが、コンパイルされたコードでは包括性と速度が相反するように見え、これが一連の妥協につながりました。残念なことに、問題の歴史を示す付録を書く時間がなかったので、関心のある読者は開始点として言及されています (Moses 1970)。(デビッド・パークは、パトリック・フィッシャーも FUNARG デバイスの開発に関与したと私に話します)。

これは、2 番目の問題とは無関係です。

2 番目: 同じ本の EVAL の異なるバージョンのバグ

この本の後半にある EVAL の定義のバグに関する議論については、Paul Graham のThe Roots of Lispを参照してください。12 ページに、McCarthy のコードに含まれる、名前付き関数の引数の二重評価を引き起こすバグの説明があります。

Answer 2

のように見える

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 を返せません。

Answer 3

更新 2:これは論文のコードで、リスト パターンと内包表記 (並列内包表記を含む) を使用して疑似コードに書き直されたもので、13行のコードすべて (デバイスを追加した15FUNARG行、以下で説明) がすべて 1 つの定義になっています。

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]

wherepat | guard -> ....が whenおよび ifにguard評価されたときに発生します。truepat

---

更新:これはPhilip Wadler によるビデオで、彼はその「バグ」について (22:30 で) 話し、「間違った変数」をどのように使用するか (疑似コードではなくlambda-bodyを評価する際に環境を使用するため)これは、「静的入札」ではなく「動的バインディング」につながります。aenv

---

本(Lisp 1.5 プログラマーズ マニュアル) のコードから元の M 式:を書き直しました。すぐに続きます。cons.

実際、二重評価の問題は見当たりません。apply引数がすでに評価されていることを期待し、その引数をeval評価します。

バグは元の論文「シンボリック式の再帰関数」にあったと思います（更新：はい！Rainer Joswigは、回答の最後でPaul Grahamの記事に言及しており、これは論文のコードを参照していると述べています）。

したがって、実際、Alan Kay の発言は動的スコープに関するものである可能性が高いようです。彼は「pg 13 の一番下」(本の中) を見ていると述べており、そこに定義があり、同じ現在の環境evlisでリストの要素を評価します。これに対する解決策については、本の 70、71 ページを参照してください。プログラマーはラムダ定義に new キーワードで明示的にタグを付け、タグ付きリストを作成して、ラムダを一緒に (または「クロージャ」のように閉じて) パッケージ化する必要があります。フォームが評価されるときの環境- つまり、そのフォームの定義環境。functionfunargfunctionlambda

Moses 1970はこれをバインド環境と呼び、高階関数呼び出しで関数引数として使用された場合のクロージャーの暗黙的な作成についてのみ説明しています (したがって、"funarg"モニカ)。これは、Perl などの言葉における「深いバインディングと浅いバインディング」(私の見解では用語の誤用) のより現代的な議論のコンテキストでもあります。

しかし、本の拡張バージョンを見ると、プログラマーがそのようなエンティティを明示的に作成し、それらを変数に格納し、他のファースト クラスエンティティと同じように渡すことができるようです。次に、クロージャー (funargタグ付きリスト) が適用されると、ラムダ定義は現在の環境 (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