vallog: 【Scheme】Y-Combinator（Yコンビネータ/不動点演算子）

【Scheme】Y-Combinator（Yコンビネータ/不動点演算子）
■Y-Combinator
「Y-Combinator」を理解するために書いたコードを元に、思考の過程を書く。
■参考
記事最下に記載。
■材料
再帰を伴う処理を基に書いていく。
通例通り階乗（http://ja.wikipedia.org/wiki/階乗）を求める「fact」関数を例に取る。
■その前に・・・
Y-Combinatorは何がしたいのか？
・無名（匿名）関数で再帰を行いたい。
⇒ 普通は「fact」関数の定義の中で「fact」呼び出しが行われる。
⇒ 「fact」という名前を使わずに再帰したい。
■注
１）、「;」で始まるコメントは出鱈目な英語です。（DrScheme（http://www.db.is.kyushu-u.ac.jp/enshu/）の日本語表示が気持ち悪いから）
２）、「;=>」は実行結果の出力
まずは与えられた数字の階乗を求める関数、「fact」を定義してみる。

;normal fact
(define fact
(lambda (n)
    (if (zero? n)
    1
    (* n (fact (- n 1))))))
(fact 5) ;=> 120

見慣れた感じ。 Schemeやったことなくても読めるはず。

;gate of normal fact
(define fact-maker
(lambda ()
    (lambda (n)
      (if (zero? n)
      1
      (* n (fact (- n 1)))))))
((fact-maker) 5);=> 120

factを直接呼び出したくない。 fact呼び出しをlambdaで包んで、fact-makerという名前をつけてみる。 factの名前を排除したかったが、結局最後のところでfactを呼び出している。 factへの入り口が変わったに過ぎない。

;receive fact
(define fact-maker
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))
((fact-maker fact) 5);=> 120

さっきfactを包むのに使ったlambdaに引数fを追加して呼び出し時にfactを渡してみる。これでfactは処理の「外」に出た。まだ処理の中にfactの残骸が見える。
(if (zero? n)
1
(* n (f (- n 1))))

;maker receive maker
(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1)))))))
((m m) 5);=>120

ここで、fact-makerはfactを置き換えるために作ったことを思い出してみる。 ((fact-maker fact) 5)を((fact-maker fact-maker) 5)としてみる。
ついでに「fact-maker」を「m」に置き換える（見づらかったので）。
fact-makerはfactを置き換えるためのものなので当然正常に動く。ただし、fact-makerはfactを引数に取っていた。置き換えると、fact-makerはfact-makerを引数に取らなければならない。
よって、fact-makerに渡されたfact-makerは引数fに割り当てられることになる。つまり、(f (- n 1))は((f f) (- n 1))となる。 ((fact-maker fact-maker) (- n 1)) ⇒ ((f f) (- n 1))

((m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1))))))) 5);=>120

呼び出しである((m m) 5)の引数であるmを直接mの中身と置き換えてみる。もちろん正常に動く。

(((lambda (f)
(lambda (n)
    (if (zero? n)
      1
      (* n ((f f) (- n 1))))))
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1))))))) 5);=>120

((m m) 5)のmを両方ともmの中身で置き換えてみる。かなり冗長だけど、名前を使わずに再帰できてるっぽい。

; (f 5) equals ((lambda (n) (f n)) 5) ; ((lambda (n) ((f f) n)) 5)
(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((lambda (n) ((f f) n)) (- n 1)))))))
((m m) 5);=>120

((f f) (- n 1))の(f f)のところがｶｯｺﾜﾙｲ。 (f (- n 1))にしたい。そのためのステップとして、(fact 5)と((lambda (x) (fact x)) 5)は同じなので、(f f)が(lambda (n) ((f f) n))となる。
(【scheme】schemeのlambdaラムダλ（http://ameblo.jp/valvallow/entry-10182420367.html）を見ればわかるように（わかりにくすぎる）)

(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))

(lambda (n) ((f f) n))を「外」に追い出して、fに渡すようにすると、m自体はこうなる。あとは、呼び出し時に(lambda (n) ((f f) n))を渡すようにすればいい。

((m m) 5)

とりあえず、この右側のmを(lambda (n) ((f f) n))に変えることができればOK。

((m
(lambda (n) ((f f) n))) 5);=> error

これは、(lambda (n) ((f f) n))がその場で評価されようとしてしまうから。

;gate of y-combinator
(lambda (p)
(m (lambda (n) ((p p) n))))

(lambda (n) ((f f) n))をmに渡す部分をlambdaにくるみ、fという名前をpに変更。

((m
(lambda (p)
(m (lambda (n) ((p p) n))))) 5);=> 120

今、((m m) 5)の右側のmを置き換えることに成功したのでこういうことになる。正常に動作。

(((lambda (p)
(m (lambda (n) ((p p) n))))
(lambda (p)
(m (lambda (n) ((p p) n))))) 5);=> 120

次に、((m m) 5)の左側のmも同様に置き換える。正常に動作。

;receive m receive 5
(((lambda (f)
((lambda (p)
(m (lambda (n) ((p p) n))))
(lambda (p)
(m (lambda (n) ((p p) n)))))) m) 5)

次に、mを「外」に追い出したいので、mに変わるfを引けるようにする。ここではまだfを引けるようにlambdaでくくりだしただけで、mは置き換えていない。

;replace m to received f ;this is the y-combinator
(lambda (f)
((lambda (p)
(f (lambda (n) ((p p) n))))
(lambda (p)
(f (lambda (n) ((p p) n))))))

mを外から引いたfに置き換えて完了。これがYコンビネータ（不動点演算子）らしい。 factの部分が完全に消えうせた。つまりfactも「再帰」から開放された。

;receive 5 reveive m to execute y-combinator
(((lambda (f)
((lambda (p)
(f (lambda (n) ((p p) n))))
(lambda (p)
(f (lambda (n) ((p p) n)))))) m) 5);=>120

階乗を求めるmとmの引数となる5を渡す。正常に動作する。

;named Y to y-combinator
(define Y
(lambda (f)
    ((lambda (p)
      (f (lambda (n) ((p p) n))))
    (lambda (p)
      (f (lambda (n) ((p p) n)))))))

Yコンビネータに名前をつける。でも冗長さが残っててｶｯｺﾜﾙｲ。（同じ処理が2回書いてある）

((Y m) 5);=>120
((Y m) 10);=>3628800

;twice ;(lambda (p) ; (f (lambda (n) ((p p) n)))) ; to once
(define Y
(lambda (f)
    ((lambda (h)(h h))
      (lambda (p)
        (f (lambda (n)((p p) n)))))))
((Y m) 5);=> 120

冗長な部分を排除したい。重複部分をlambdaでくくりだす。

;fibonacci
(define fib
(lambda (n)
    (if (<= n 2)
      1
      (+ (fib (- n 1))(fib (- n 2))))))
(fib 10);=> 55

フィボナッチ数列を求める普通の関数。今度はフィボナッチ数列のコードで試してみる。

;Y-Combinator fibonacci
(define fib
(lambda (f)
    (lambda (n)
      (if (<= n 2)
        1
        (+ (f (- n 1))(f (- n 2)))))))
((Y fib) 10);=> 55

正常に動作。
【全景】

;normal fact
(define fact
(lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))
(fact 5) ;=> 120
;gate of normal fact
(define fact-maker
(lambda ()
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1)))))))
((fact-maker) 5)
;receive fact
(define fact-maker2
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n (f (- n 1)))))))
((fact-maker2 fact) 5)
;maker receive maker
(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((f f) (- n 1)))))))
((m m) 5)
((m
(lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((f f) (- n 1))))))) 5)
(((lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((f f) (- n 1))))))
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((f f) (- n 1))))))) 5)
; (f 5) equals ((lambda (n) (f n)) 5)
; ((lambda (n) ((f f) n)) 5)
(define m2
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((lambda (n) ((f f) n)) (- n 1)))))))
((m2 m2) 5)
;(lambda (f)
; (f0 (lambda (n) ((f f) n))))
; is one of fact-maker
(define f0
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n (f (- n 1)))))))
;gate of y-combinator
(lambda (p)
(f0 (lambda (n) ((p p) n))))
((m
(lambda (p)
    (f0 (lambda (n) ((p p) n))))) 5)
(((lambda (p)
(f0 (lambda (n) ((p p) n))))
(lambda (p)
(f0 (lambda (n) ((p p) n))))) 5)
;receive f0 receive 5
(((lambda (f)
((lambda (p)
     (f0 (lambda (n) ((p p) n))))
   (lambda (p)
     (f0 (lambda (n) ((p p) n)))))) f0) 5)
;replace f0 to received f
;this is the y-combinator
(lambda (f)
((lambda (p)
     (f (lambda (n) ((p p) n))))
   (lambda (p)
     (f (lambda (n) ((p p) n))))))
;receive 5 reveive f0 to execute y-combinator
(((lambda (f)
((lambda (p)
     (f (lambda (n) ((p p) n))))
   (lambda (p)
     (f (lambda (n) ((p p) n)))))) f0) 5)
;named Y to y-combinator
(define Y
(lambda (f)
    ((lambda (p)
       (f (lambda (n) ((p p) n))))
     (lambda (p)
       (f (lambda (n) ((p p) n)))))))
((Y f0) 5)
((Y f0) 10)
;twice
;(lambda (p)
;       (f (lambda (n) ((p p) n))))
; to once
(define Y2
(lambda (f)
    ((lambda (h)(h h))
     (lambda (p)
       (f (lambda (n)((p p) n)))))))
((Y2 f0) 5)
;fibonacci
(define fib
(lambda (n)
    (if (<= n 2)
        1
        (+ (fib (- n 1))(fib (- n 2))))))
(fib 10)
;Y-Combinator fibonacci
(define fib2
(lambda (f)
    (lambda (n)
      (if (<= n 2)
          1
          (+ (f (- n 1))(f (- n 2)))))))
((Y fib2) 10)