4 
;; compute the max of a list of integers

(define Y
  (lambda (w)
    ((lambda (f)
       (f f))
     (lambda (f)
       (w (lambda (x)
            ((f f) x)))))))

((Y
  (lambda (max)
    (lambda (l)
      (cond ((null? l) -1)
            ((> (car l) (max (cdr l))) (car l))
            (else (max (cdr l)))))))
 '(1 2 3 4 5))

この構造を理解したい。誰かがこのコードについて明確で簡単な説明をすることができますか?

たとえば、Y の式を忘れたとします。どうすればそれを覚えて、作業を行った後でも再現できるでしょうか?

4

2 に答える 2

2

ここにいくつかの関連する回答があります（私による）：

基本的に、Yを と定義するλr.(λh.h h) (λg.r (λx.(g g) x))と、アプリケーションは次のようにY r還元されます。

Y r
(λw.(λh.h h) (λg.w (λx.(g g) x))) r
(λh.h h) (λg.r (λx.(g g) x))
h h
    ;where
        h = (λg.r (λx.(g g) x))       <----\
                                           |
(λg.r (λx.(g g) x)) h                      |
r (λx.(g g) x)             <-------------- | ----------\
    ;where                                 |           |
        g = h                         -----/           |
        ;so that                                       |
        (g g) = (h h) = r (λx.(g g) x)           ------/

したがってr、2 つの引数が必要です。1 つ目は呼び出される再帰関数を表し、2 つ目は実際の引数です。

        r = λf (λx. ....x.....(f y)...... )

それは次のように(Y r) x 減少します

(r (λx.(g g) x)) x
(r f) x
    ;where
        f   = (λx.(g g) x) 
        f y = (λx.(g g) x) y = (g g) y = (r f) y  ; f is "fixed point" of r

この定義f = (λx.(g g) x)は、 が呼び出されたときf yに呼び出される(g g) yことを意味し、その時点 gで自己適用され、r内部から「プル」され、引数付きで呼び出されgた結果が返されます。つまり、アプリケーションから生じるラムダ式の本体での呼び出しは、新しい引数を使用した同じ本体の呼び出しに変換されます。(r f)y(f y)(r f)(r f) yy

重要な実装の詳細は、それが同じ関数本体であるか、そのコピーであるかですが、セマンティクスは同じです。新しい引数値で同じ関数本体に入ることができます。

Y コンビネータの本質は、参照と自己適用による複製です。同じものを同じ名前で 2 回参照します。したがって、引数としてそれ自体を受け取るように手配します。

純粋なラムダ計算のように参照がなく、パラメーターが引数のテキスト コピーを受け取る場合 (つまり、テキストの書き換えによってリダクションが行われる場合)、同じコピーが複製されて渡され、self への引数として渡されるため、これは機能します。必要に応じて、次の反復で。

ただし、共有参照が使用できる場合ははるかに効率的です (同じ名前を使用する場合はすべて同じものを参照します)。自己参照関数の評価作成の環境モデルの下では、次のように単純です。

(let ((fact #f)) 
  (set! fact 
        (lambda (n) (if (< 2 n) 1 
                               (* n (fact (- n 1)))))) 
  fact)

実際、あなたの答えの定義は、適用順序 Y コンビネーターの定義です。通常の順序では、無限ループを引き起こすことなく eta-reduction を適用して、Ynorm = (λw.(λh.h h) (λg.w (g g)))標準的に次のように記述されたものを取得できます。

Ynorm = (λf.(λx.f (x x)) (λx.f (x x)))

確かに

Ynorm g
= (λx.g (x x)) (λx.g (x x))
= g ((λx.g (x x)) (λx.g (x x)))
于 2012-10-29T10:25:10.743 に答える
2

私がこれまでに見つけた最良の説明は、書籍「The Little Schemer」の第 9 章にあります。この章全体では、Y-Combinator がどのように機能するか、および任意の再帰プロシージャから開始してコンビネータを導出する方法を段階的に説明しています。 .

于 2012-10-28T23:21:04.360 に答える