Yコンビネータの実装体系

Question

私は、関数型プログラミングのスキームには本当に新しいです。私は最近、ラムダ計算のY-コンビネータ機能に遭遇しました。このようなものはY ≡ (λy.(λx.y(xx))(λx.y(xx)))です。私はスキームでそれを実装したい、私はたくさん検索したが、私は上記の構造に正確に一致する実装が見つかりませんでした。私が見つけたそのうちのいくつかを以下に示す。

(define Y 
(lambda (X) 
    ((lambda (procedure) 
    (X (lambda (arg) ((procedure procedure) arg)))) 
    (lambda (procedure) 
    (X (lambda (arg) ((procedure procedure) arg))))))) 

と

(define Y 
    (lambda (r) 
    ((lambda (f) (f f)) 
    (lambda (y) 
     (r (lambda (x) ((y y) x))))))) 

あなたが見ることができるように、彼らはこのY ≡ (λy.(λx.y(xx))(λx.y(xx)))コンビネータ機能の構造と一致してはいけません。どのように私はそれを全く同じ方法でスキームに実装できますか？

Answer 1

レイジーラケットのようなレイジー言語では、通常のオーダーバージョンを使用できますが、Schemeのようなアプリケーションプログラミング言語では使用できません。彼らは無限ループに入ります。

Yの応用的バージョンは、多くの場合、Zコンビネータと呼ばれる：

(define Z 
    (lambda (f) 
    ((lambda (g) (g g)) 
    (lambda (g) 
     (f (lambda args (apply (g g) args))))))) 

さて、これが適用されるときに起こる最初の事は(g g)であり、あなたはいつもそれの体の拡大にアプリケーション全体を置き換えることができますので、私は本当に何も変わっていない

(define Z 
    (lambda (f) 
    ((lambda (g) 
     (f (lambda args (apply (g g) args)))) 
    (lambda (g) 
     (f (lambda args (apply (g g) args))))))) 

：関数の本体は、に書き換え得ることができます。まったく同じコードを実行するだけのコードです。このバージョンでは、複数の引数関数をサポートするためにapplyが使用されています。

(define ackermann 
    (lambda (m n) 
    (cond 
     ((= m 0) (+ n 1)) 
     ((= n 0) (ackermann (- m 1) 1)) 
     (else (ackermann (- m 1) (ackermann m (- n 1))))))) 

(ackermann 3 6) ; ==> 509 

これは、このようZで行うことができます：実装がまったく同じで、違いは、それ自体への参照が処理される方法である

((Z (lambda (ackermann) 
     (lambda (m n) 
     (cond 
     ((= m 0) (+ n 1)) 
     ((= n 0) (ackermann (- m 1) 1)) 
     (else (ackermann (- m 1) (ackermann m (- n 1)))))))) 
3 
6) ; ==> 509 

お知らせアッカーマン関数を想像してみてください。

EDIT

だから、評価が遅れる方法を求めています。あなたは、これはあなたがそれを(f (g g))でfを適用することができます前に、それが(g g)たを評価する必要があるので、Yは決して戻らないことに気づくでしょう引数を指定して適用されるかを見てみると

(define Y 
    (lambda (f) 
    ((lambda (g) (g g)) 
    (lambda (g) (f (g g)))))) 

：まあ、通常のオーダーのバージョンは次のようになります今度は(f (g g))などを評価します。すぐに(g g)は適用されません。 (g g)は関数になるので、fに実際の関数を生成して適用する関数を与えるだけです。 add1の機能をお持ちの場合は、代わりに使用できるラッパー(lambda (x) (add1 x))を作成すると動作します。同じように(lambda args (apply (g g) args))は(g g)と同じで、置換ルールを適用するだけで表示されます。ここでのヒントは、実際に使用されるまで、各ステップでの計算を効果的に停止することです。