そこでは Y コンビネータがどこから来たのか、ということについては書かなかった。
今回はYコンビネータがどこから来たのかについて書くつもりだ。
あらかじめ大筋を話してしまうと、Yコンビネータの導出は
1. 自分自身の名前を使っても良いので、簡単な再帰関数を定義する。
2. その定義から自分自身の名前をどうにかして外に追い出す
って感じで進めるので頭の片隅に置いておいてほしい。
じゃあまず n の階乗を計算する関数 fact を考えるところからはじめよう。
fact は再帰で簡単に定義すると下記のとおりだ。
(define (fact n)
(if (zero? n)
1
(* n (fact (- n 1)))))
実行すると正しい回答が返る(fact 5) ; => 120lambda計算を考えるときに define の形式が MIT スタイルでは分かりにくいので、
標準スタイル(シンボルにlambda式を評価したものを与える形式) で定義しなおしておく
(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
(fact 5) ;; => 120
この fact のlambda式の中からfactを追い出したい。ここで使うのは、この後ずっと基本となる変換テクニックだが、
関数を新たなlambdaでくるんでその引数として関数内で使うものを渡してやる、
という方法だ。
これで色々なものを関数外に追い出せる。
ここでは fact を一番外側のlambdaの引数 f として渡してやるように変換しよう
(define fact%
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
もちろん呼び出し側では fact を渡してやる必要がある。((fact% fact) 5) ;; => 120うまくいった。呼び出し側に fact が残っているがとりあえず気にしないでおこう。
呼び出し側をさっきの
(fact 5) ;; => 120と比べてみると fact == (fact% fact) であることが分かる。
新しい式の fact も置き換えてみると・・・
((fact% (fact% fact)) 5) ;; => 120これはずっと繰り返すことが可能だ。
((fact% (fact% (fact% (fact% fact)))) 5) ;; => 120でも、これじゃあいつまでも fact を取り除くことができない
ここで fact と fact% の形を比べてみると、
lambda でくるまれているかどうかだけでよく似ていることが分かる。
(define fact ;; (再掲)
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
(define fact% ;; (再掲)
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
そこで、 fact の代わりに使う関数として、もっと fact% の形に似せた関数 fact%2 を、 fact を lambda でくるんで作ってみる
(define fact%2
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1)))))))
fact%2 で fact を置き換えることを考えると、fact%2の呼び出し時には何か引数を渡してやる必要がある。fact%2 に渡されてきた f は fact%2 内部では使われてないので何でもいいんだけど、
(fact% fact) という形に似せて、fact% を渡して (fact%2 fact%) とすることにする。
(fact%2 fact%) は fact%2 の定義からして fact と等しいはずだ。
そこで (fact%2 fact%) で fact を置き換えることを考えると、
((fact% fact) 5) ;; => 120 (再掲)を次のように変形できる
((fact% (fact%2 fact%)) 5) ;; => 120うまくいった。もともと (fact% fact) == fact だったのだから、当然
((fact%2 fact%) 5) ;; => 120でもある
fact%2 の定義のなかの fact を何かに置き換えたい。
さっきも利用したけど、
fact == (fact%2 fact%) なのでコレを利用して、
(define fact%2 ;; (再掲)
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1)))))))
;; fact%2 の fact を (fact%2 fact%) で置き換えたものを考える。
;; それに fact%3 という新しい名前をつけると以下のようになる
(define fact%3
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((fact%3 fact%) (- n 1)))))))
という定義をもった fact%3 でもいいはずだ。((fact%3 fact%) 5) ;; => 120OK
fact%2, fact%3 はもともと fact% に似せてつくってあったはずだ。
なので fact% も fact%3 で置き換えられるかもしれない
((fact%3 fact%3) 5) ;; => 120うまく行くようだ。となると、 fact%3定義内の fact% も fact%3 で
置き換え可能なはず。
そのように fact%4 を書いてやると
(define fact%4
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((fact%4 fact%4) (- n 1)))))))
((fact%4 fact%4) 5) ;; => 120
うまく動く。ここで fact%4 定義内の f に何を渡しているかというと、 fact%4 だ。
したがって (fact%4 fact%4) という形で呼び出してやる限り、 fact%4
定義内の fact%4 を f で置き換えることができる
(define fact%5
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (- n 1)))))))
((fact%5 fact%5) 5) ;; => 120
これで再帰関数内から自身の名前を排除できた。fact%5 を使ってるじゃないかって？
大丈夫、((fact%5 fact%5) 5) を fact%5 の定義である lambda式で置き換えると
(((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
となり、どこにも fact%5 は現れていないが、計算できている。============================================================
(補足)
狐につままれた感じがするかもしれないけど、それぞれの変換におかしな所はない。
気になる場合は最初からここまでの変換を何度か往復してみよう。
人によっては
(define fact ;; (再掲)
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
(define fact% ;; (再掲)
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
((fact% fact) 5) ;; => 120
を見ただけで(define fact%5
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (- n 1)))))))
((fact%5 fact%5) 5) ;; => 120
への変換を理解できる人も居るようだ。むしろこっちのほうがわかりやすいって人も居るかもしれない。
============================================================
さて、このままでは (fact%5 fact%5) のように呼びださなければならないのがダサい。
そこで呼び出し側もlambdaでくるんでやると
(define Yc%
(lambda (f)
(f f)))
((Yc% fact%5) 5) ;; => 120
となる。こうなってくると、 fact%5 の定義内にある (f f) もダサいので外に出したくなる。
fact%5 の f の有効スコープ内、つまり (lambda (n) ... よりも外側で
新しく lambda (g) でくるみ、 g に (f f) を渡してやるようにする
(define fact%5 ;; (再掲)
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (- n 1)))))))
(define fact%6
(lambda (f)
((lambda (g)
(lambda (n)
(if (zero? n)
1
(* n (g (- n 1)))))) ;; ← g として渡された (f f) を呼び出す
(f f)))) ;; ← (lambda (g) ... の g に (f f) の結果を渡す
((Yc% fact%6) 5) ;; => エラー。残念ながら無限ループに陥ってしまう。
どうやら fact%6 内の (f f) を評価しようとして無限ループに陥ってしまうらしい。ここを評価させない方法はあるだろうか。
lisp でよくやる遅延データ構造化手法として macro 化か lambda でくるむ、という方法がある。
ここで使えるのは lambda 計算のみなので macro は使えない。lambdaでくるむことにする。
;;;; 注: 勘の良い人はピンときたと思うが、 Lisp で使うYコンビネータが正確
;;;; には Zコンビネータであり、Yコンビネータではないのはこれが理由だ。
fact%6内で (g (- n 1)) としている箇所が ((f f) (- n 1)) となって欲しいわけだから、
g == (lambda (x) ((f f) x)) となるようにすれば良さそうだ。
そのように fact%6 を定義しなおすと
(define fact%7
(lambda (f)
((lambda (g)
(lambda (n)
(if (zero? n)
1
(* n (g (- n 1))))))
(lambda (x)
((f f) x)))))
((Yc% fact%7) 5) ;; => 120
よし、うまくいった。ここで fact%7 内部を見るとfact% と同じ構造が埋まっていることに気付く
(define fact% ;; (再掲)
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (- n 1)))))))
fact% は自分自身の名前を使ってないので、置き換えてもルール違反じゃあない(define fact%8
(lambda (f)
(fact%
(lambda (x)
((f f) x)))))
((Yc% fact%8) 5) ;; => 120
ここで fact%8 全体を lambda でくるみ、fact% を外にだしてあげよう(define Yc%2
(lambda (g)
(lambda (f)
(g
(lambda (x)
((f f) x))))))
ちなみに名前はfact%9 としたいところだが、 fact 的要素はすでに外に出て行ってしまっているのでYc%2 とした。すると、
((Yc% (Yc%2 fact%)) 5) ;; => 120となる。うまくいっているようだ。
(Yc% (Yc%2 fact%)) からも fact% を外に簡単に出せそうなので、全体をlambdaでくるんで fact%を外に出す
(define Yc%3
(lambda (h)
(Yc% (Yc%2 h))))
((Yc%3 fact%) 5) ;; => 120
Yc%3 を構成する Yc%, Yc%2 を元のlambda式で置換してやると(define Yc%4
(lambda (h)
((lambda (f)
(f f))
((lambda (g)
(lambda (f)
(g (lambda (x)
((f f) x)))))
h))))
((Yc%4 fact%) 5) ;; => 120
となり、さらに Yc%4後半の lambda (g) の g には h が渡ってるだけなので剥がしてやると(define Yc%5
(lambda (h)
((lambda (f)
(f f))
(lambda (f)
(h (lambda (x)
((f f) x)))))))
((Yc%5 fact%) 5) ;; => 120
となる。これで fact% を受け取って再帰関数を生成関数するような関数、つまり Yコンビネータ を導出できた。
これは前半の (lambda (f) (f f)) をあらかじめ適用してYコンビネータとして見慣れた形にしてやってもよい
(define Yc
(lambda (h)
((lambda (f)
(h (lambda (x)
((f f) x))))
(lambda (f)
(h (lambda (x)
((f f) x)))))))
((Yc fact%) 5) ;; => 120
もちろん Yc, fact% という名前は lambda 式に便宜上名前を与えてるだけなので、(define fact
((lambda (h) ;; Yc
((lambda (f) ;; |
(h (lambda (x) ;; |
((f f) x)))) ;; |
(lambda (f) ;; |
(h (lambda (x) ;; |
((f f) x)))))) ;; -
(lambda (f) ;; fact%
(lambda (n) ;; |
(if (zero? n) ;; |
1 ;; |
(* n (f (- n 1)))))))) ;; -
(fact 5) ;; => 120
のようにすれば、関数名を一切使わずに再帰関数を定義できている。ここで終わってもいいんだけど、この Yc には一つ問題があるのでもう少し進めよう。
問題とは Yc はfact%が単一の引数を持つ場合にしか適用できないことだ。
つまり、fact の末尾再帰版(末尾再帰を知らない場合、ここでは蓄積変数accを使ったバージョンだと思えば良い)
は以下の通りだが、
(define (fact-iter acc n)
(if (zero? n)
acc
(fact-iter (* n acc) (- n 1))))
(fact-iter 1 5) ;; => 120
これを Yc を使って生成しようとしてもエラーになる(define fact-iter%
(lambda (f)
(lambda (acc n)
(if (zero? n)
acc
(f (* n acc) (- n 1))))))
((Yc fact-iter%) 1 5) ;; => エラー
これは最終的に fact-iter% 内に渡る f が Yc 内の(lambda (x) ((f f) x))であることが原因だ。この関数は x という単一の引数しか取っていない。
任意の数の引数を取れるようにするには
(lambda args (apply (f f) args))とすればよいので、 Yc を
(define Yc
(lambda (h)
((lambda (f)
(h (lambda args
(apply (f f) args))))
(lambda (f)
(h (lambda args
(apply (f f) args)))))))
と定義しなおしてやれば((Yc fact-iter%) 1 5) ;; => 120となる。これで Lisp(Scheme)で汎用的に使えるYコンビネータを定義できた。
Yコンビネータが出てくる文脈は普通 lambda 計算についての話だ。
lambda計算では、話を簡単にしたり、再利用性を高めたりするためだと思うんだけど、
大抵は可能な限りまでカリー化された関数、つまり1引数しかとらない関数で考える。
そういうわけで、Yコンビネータを紹介する文脈では最初の Yc の定義で十分なんだろうね。
(20150116追記) 上の定義にも問題はある。 apply が必要ってことだ。それに「コンビネータ」とは自由変数を持たないlambdaのことを言うらしいので、applyを使ってしまったら「コンビネータ」とは言えなくなってしまう。
さて、苦労してYコンビネータを導出したけど、実際のところSchemeはもちろん、多くのプログラミング言語で再帰関数を定義するときに(名前が指し示す場所にlambda式の評価結果を格納するという副作用の働きのおかげで)Yコンビネータは不要だ。
でも純粋な(副作用を持たない)関数の組み合わせだけでも再帰関数を組み立てることができる、というのはすごいことだ。
参考:
助かりました。ありがとうございますッ！
返信削除