$Id: ycombinator.html,v 1.6 2002/06/27 23:37:39 aamine Exp $
[ruby-list:35058] に刺激を受けて Y combinator を解読してみた。 こんなもん読むくらいなら以下の参考ページを読んだほうがいい。
参考にした (というかほとんどそのままな) ページ (英語)
再帰関数は再帰するときに自分自身を名前で呼ぶのが普通である。 これをなんとかして名前を使わず、関数そのものを呼ぶように させたい。
まず単純な fact (階乗) を以下に示す。言語は Scheme である。
(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
ここから名前をなくすために、まず普通に書いた fact と同じ中身の 関数を返す関数を作る。
(define fact-maker
(lambda ()
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1)))))))
fact 呼び出しも引数にしてくくりだしてしまう。
(define fact-maker
(lambda (proc)
(lambda (n)
(if (zero? n)
1
(* n (proc (- n 1)))))))
しかしこれをどう呼び出せばいいだろう。
(fact-maker 5)
ではまずい。関数が返って終わりだ。
再帰し続ける限り (呼び出しが続く限り) fact が必要なわけだから、 引数に fact-maker が必要だ。また最初の一回だけでなく fact-maker は 常に「次」の関数に引数として fact-maker を渡し続けないといけない。 と考えると、まず一発目の呼び出しは
((fact-maker fact-maker) 5)
でなければいけないし、fact-maker の中身の proc 呼び出しの ところでも同じく (proc proc) でなければならない。
(define fact-maker
(lambda (proc)
(lambda (n)
(if (zero? n)
1
(* n ((proc proc) (- n 1)))))))
これで (1) 関数の生成 (2) 呼び出し (3) 次の引数に fact-maker を渡す、 の三つが連鎖して行われるようになり、正常に値を求められる。
しかしこれではまだ fact-maker という名前が残っているし、 必ず (proc proc) と書かなければいけないのも悔しい。 (fact (- n 1)) だったところを単純に fact を引数化して (proc (- n 1)) と書き換えれば済むようにしたい。そこで今度は (fact-maker fact-maker) 自体を生成する関数を作ることを 考えよう。これには、
(f 5)
と
((lambda (x) (f x)) 5)
の評価値が同じであるという技を使う。 (この二つの違いはと言うと、上のほうが「即座に」値を求めている のに対して下は lambda をかますことで評価を少し先送りしていることだ。 評価される時期は (Schemeでは) 異なるが、λ抽象としての評価値は同じである)
この技を適用すると、
((proc proc) real-arg)
この式は次のように書きなおせる。
((lambda (arg) ((proc proc) arg)) real-arg)
だから fact-maker は次のように書き直しても評価値は同じだ。
(define fact-maker
(lambda (proc)
(lambda (n)
(if (zero? n)
1
(* n ((lambda (arg) ((proc proc) arg)) (- n 1)) )
)))))
ここで proc ではなく最初から今展開した lambda を引数にとる ようにすれば、この部分を外に出して階乗計算部分だけ残すことが できる。関数名は fact0 に、引数名は proc から f に変えよう。
(define fact0
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
;; くくりだされた部分 (fact-maker いっこぶん)
(lambda (proc)
(fact0 (lambda (arg) ((proc proc) arg))))
ところで、わざわざ lambda でくくって出すのではなく (proc proc) を そのまま抜き出してはいけないのだろうか。これは、いけない。実際 やってみると無限ループに陥る。そもそもやりたいことは (proc proc) が f の「中」で評価されることであって、(proc proc) をそのまま抜き出すと f の「外」で評価されてしまう。
あとは呼び出し側の (fact-maker fact-maker) を修正すればいい。 fact-maker 一個分に相当する表現はわかっているから、それを 二回書いてリストにするだけだ。
((lambda (proc)
(fact0 (lambda (arg) ((proc proc) arg))))
(lambda (proc)
(fact0 (lambda (arg) ((proc proc) arg)))))
さらに fact0 は名前なのでくくりだせる。
(lambda (f)
((lambda (proc)
(f (lambda (arg) ((proc proc) arg))))
(lambda (proc)
(f (lambda (arg) ((proc proc) arg))))))
これで完成である。 あとは fact0 をあわせればうまくいく。
;;; 名前を付けただけ
(define Y
(lambda (f)
((lambda (proc)
(f (lambda (arg) ((proc proc) arg))))
(lambda (proc)
(f (lambda (arg) ((proc proc) arg)))))))
;;; 自分自身を受け取る fact
(define fact0
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
((Y fact0) 5) ; 答えは 120
この Y を Y combinator って言うんだってさ。ふーん。 ちなみにコンビネータっていうのはプログラム意味論の用語。手続き名も 含む「変数」がすべて束縛変数である (引数になっている) λ式のこと。 そういうλ式はまわりの環境に依らずに同じ動作ができる……つまり完全に 自分自身の意味が固定されている。