素晴らしい質問です。DrRacketが機能していない人（私自身も含む）のために、私はそれに答えようとします。
まず、人間の目/心で簡単に追跡できる、いくつかの正気の（短い）変数名を使用しましょう。
((lambda (h) ; A.
(h h)) ; apply h to h
(lambda (g)
(lambda (lst)
(if (null? lst) 0
(add1
((g g) (cdr lst)))))))
最初のラムダ項は、リトルオメガまたはUコンビネータとして知られているものです。何かに適用されると、それはその用語の自己適用を引き起こします。したがって、上記は同等です
(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)自己適用のポイントに到達し、上記で概説したのと同じ削減手順が再び実行されます。しかし、それ以前ではありません。
さて、その本の著者はYコンビネータに到達したいので、最初の式にいくつかのコード変換を適用して、その自己アプリケーション(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
もちろん、作者はこれを知っています。彼らは私たちにもそれを理解してほしいと思っています。
したがって、原因は単純です。これは、評価の適用順序です。つまり、関数の仮パラメーターとその引数の値でバインディングが形成される前に、引数を評価します。
そのとき、そのコード変換は完全には正しくありませんでした。引数が事前に評価されていない通常の順序で機能します。
これは、「 eta-expansion 」によって簡単に修正できます。これは、実際の呼び出しポイントまでアプリケーションを遅延させます。実際には、「引数を指定して呼び出されたときに呼び出します(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.のいずれにも依存しないことに注意してください。だから私たちはそれを取り出して議論にし、そして... Yコンビネータを残すことができます：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を呼び出すことは、関数から再帰的定義を作成することと同じです。
( y (lambda (f) (lambda (x) .... (f x) .... )) )
=== define f = (lambda (x) .... (f x) .... )
...しかし、使用するletrec（またはletという名前の）方が優れています—より効率的で、自己参照環境フレームでクロージャを定義します。Yの全体は、それが不可能なシステムの理論的な演習です。つまり、物に名前を付けることができない場合、物を参照して物を「指す」名前のバインディングを作成します。
ちなみに、物事を指す能力は、高等霊長類を他の動物界⁄生き物と区別するものです。:)
