それで、私は第9章の終わりを何度も読み返しました。小さな策略家、ここでは関数に対して適用可能な Y コンビネータが開発されていますlength。私の混乱は、長さの 2 つのバージョン (コンビネータが因数分解される前) を対比する 1 つのステートメントに集約されると思います。
A:
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0 )
(else (add1
((mk-length mk-length)
(cdr l))))))))
B:
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
170ページ（第4版）Aは次のように述べている
引数に適用すると関数を返します
一方、B
関数を返さない
その結果、自己適用の無限後退が発生します。私はこれに困惑しています。B がこの問題に悩まされているのなら、A がそれを回避できるとは思えません。
ベストアンサー1
素晴らしい質問ですね。DrRacket をインストールしていない人(私も含めて)
のために、 回答してみます。
まず、人間の目や頭で簡単に追跡できる、妥当な (短い) 変数名を使用しましょう。
((lambda (h) ; A.
(h h)) ; apply h to h
(lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1
((g g) (cdr lst)))))))
最初のラムダ項は、小さなオメガ、またはあなたコンビネータ何かに適用された場合、その用語の自己適用を引き起こします。したがって、上記は次の式と同等です。
(let ((h (lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst))))))))
(h h))
hを に適用するとh、新しいバインディングが形成されます。
(let ((h (lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst))))))))
(let ((g h))
(lambda (lst)
(if (null? lst) 0
(add1 ((g g) (cdr lst)))))))
これで適用するものがなくなったため、内部フォームが返されます。さらに、その上にあるlambda環境フレームへの非表示のリンク (つまり、それらのバインディング) も返されます。let
ラムダ式とそれを定義する環境のこの組み合わせは、閉鎖外部の世界にとっては、これは 1 つのパラメータの単なる別の関数ですlst。現時点では、これ以上の削減手順は実行されていません。
さて、そのクロージャ（list-length関数）が呼び出されると、実行は最終的に(g g)自己適用のポイントに到達し、上記と同じ削減手順が再び実行されます（再計算）。の 同じ閉鎖。ただし、それより前ではありません。
さて、その本の著者たちは、はいコンビネータなので、最初の式に何らかのコード変換を適用して、何らかの方法でその自己適用が自動的に実行されるように調整します。そのため、すべての再帰呼び出しに対してと記述するのではなく、(g g)通常の方法で再帰関数の適用を記述できます。(f x)((g g) x)
((lambda (h) ; B.
(h h)) ; apply h to h
(lambda (g)
((lambda (f) ; 'f' to become bound to '(g g)',
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)!
(g g)))) ; (this is not quite right)
数ステップの削減を経て、次のようになります。
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g)))))
(let ((g h))
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g))))
これは次の式と同等である。
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(g g)))))
(let ((g h))
(let ((f (g g))) ; problem! (under applicative-order evaluation)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))))
ここで問題が起こります。自己適用が(g g)早すぎると、前に内部のラムダはクロージャとしてランタイムシステムに返すこともできます。実行がそのポイントに到達したときにのみ、それを縮小したいのです。内部ラムダ式、後クロージャが呼び出されました。クロージャが作成される前に削減するのはばかげています。微妙エラー。 ：）
もちろん、gは にバインドされているのでh、(g g)は に簡約され、に(h h)適用して開始点に戻ります。ループ。hh
もちろん著者らもこのことは承知している。私たちそれを理解するためにも。
犯人は単純だ。それは評価の適用順序:評価する議論前にバインディングは関数の仮パラメータとその引数の価値。
そのコード変換は正しくなかった。通常の順序引数が事前に評価されない場合。
これは「イータ展開"、これは実際の呼び出しポイントまでアプリケーションを遅延させます。(lambda (x) ((g g) x))実際には次のように表示されます。"意思((g g) x)引数 " で呼び出されたときに呼び出しますx。
そして、実際には、コード変換は次のように行われるべきでした。
((lambda (h) ; C.
(h h)) ; apply h to h
(lambda (g)
((lambda (f) ; 'f' to become bound to '(lambda (x) ((g g) x))',
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)
(lambda (x) ((g g) x)))))
これで次の削減ステップを実行できます。
(let ((h (lambda (g)
((lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))
(lambda (x) ((g g) x))))))
(let ((g h))
(let ((f (lambda (x) ((g g) x)))) ; here it's OK
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst))))))))
クロージャは(lambda (lst) ...)問題なく形成されて返され、 が(f (cdr lst))呼び出されると (クロージャ内で)((g g) (cdr lst))期待どおりに縮小されます。
(lambda (f) (lambda (lst ...))最後に、の式はとC.のいずれにも依存していないことに気が付きます。したがって、これを取り出して引数にすると、次のようになります...hgはいコンビネータ:
( ( (lambda (rec) ; D.
( (lambda (h) (h h))
(lambda (g)
(rec (lambda (x) ((g g) x)))))) ; applicative-order Y combinator
(lambda (f)
(lambda (lst)
(if (null? lst) 0
(add1 (f (cdr lst)))))) )
(list 1 2 3) ) ; ==> 3
だから今、電話してはい関数に対して を使用することは、関数から再帰的な定義を作成することと同等です。
( y (lambda (f) (lambda (x) .... (f x) .... )) )
=== define f = (lambda (x) .... (f x) .... )
...しかし、letrec（または名前付きlet）を使用するとより良い- もっと効率的、自己参照環境フレームにおける閉包の定義。 全体はいこれは、それが不可能なシステム、つまり、名前物、創造するバインディング名前付き"ポインティング"物事に、参照する物事に。
ちなみに、ポイント物事に対する感受性こそが、高等霊長類を動物界の他の生物と区別するものだ、と私は聞いています。:)