Y コンビネータとは何か？
あなたはどんな言葉でも使う事が出来ます。しかし、知らない言葉を使う時は、今まで知っている言葉で説明できなくてはなりません。
例えば、「カニ」と「コロッケ」と「クリーム」だけを知っている時、あなたは「カニクリームコロッケ」について語る事が出来ます。「『カニクリームコロッケ』とは、『カニ』の味のする『クリーム』の入った『コロッケ』である。」しかし、「かぼちゃコロッケ」については語る事は出来ません。なぜなら「かぼちゃ」について何も知らないからです。
さてここで問題。「皮」や「剥いだ物」について知っている時、次の説明は適当でしょうか？「『タマネギ』とは、『タマネギ』の『皮』を剥いた物である。」私たちは、タマネギの皮を剥いてもタマネギである事を知っています。しかし、タマネギを説明するのにタマネギを話題に出しても良いものでしょうか？インチキ臭い感じがしませんか？こういうのを再帰的定義と言います。
ある物を定義するためには、すでに知っている単語で説明しなくてはいけません。これはいたってまともな考え方です。では例えばこの強引なタマネギの例や、いわゆる「鶏が先か卵が先か？」問題についてどう考えれば良いでしょう。鶏や卵の事を知らない宇宙人に、卵は鶏から生まれて鶏は卵から生まれて。。。という循環を説明するのはどうしたら良いでしょう？これを解決するのが Y コンビネータです。
Y コンビネータを使った階乗
ただ、比喩の話はここまでで、以下プログラミングの話です。多分宇宙人も空気の読める人なら Y コンビネータは要らないと思います。しかし、コンピュータはそういうわけには行かないのでこういう理屈が居るのです。以下自習記録。ようはコピペ。言語には scheme を使います。
階乗は普通こういう風に定義します。
(define (fact n) (if (zero? n) 1 (* n (fact (- n 1))))) (print (fact 10))
これは fact を定義するのに fact を使ってるので「インチキ」です。しかしこのインチキ成分だけを抽出した次のような関数を考えます。
(define (Y f) (f (lambda (arg) ((Y f) arg))))
これを使って階乗を定義する事が出来ます。make-fact の中には自己参照はありません。つまり、make-fact は正当な定義です。
(define (make-fact f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))) (print ((Y make-fact) 10))
この、インチキ成分の事を Y コンビネータと呼びます。しかし、これではインチキを押し込めただけで、インチキには変わりないじゃないか！とお叱りを受けると思います。しかしここで登場する驚愕の事実。何と Y コンビネータは再帰を使わなくても定義出来るのです！
(define (Y f) ((lambda (proc) (f (lambda (arg) ((proc proc) arg)))) (lambda (proc) (f (lambda (arg) ((proc proc) arg))))))
これはすごい！はっきり言って、なんでこうなるのかさっぱり分かりませんが、再帰的な関数を再帰無しで定義出来るという事実には衝撃を受けました。これを知るまで、何でみんな Y コンビネータの事を大騒ぎしてるのか理解できませんでした。
Y コンビネータは何の役に立つのか？
実は病気で俺様言語の実装を中断するまで、再帰関数を再帰無しで定義出来ないと思い込んでいたのです。なんしか私にとっては Haskell が唯一の正義だったので。で、はいはい再帰はプリミティブね。と思っていたんだけど、なんか気分悪ーと言う気持ちが付きまとうわけです。なぜなら再帰関数を実装するには副作用が必要だからです。例えば fact の例だと、fact を定義する前に fact への参照が要るわけですから、まず fact のメモリを確保して、関数を定義してしまってから先ほど確保した fact に代入しないといけないわけですが、関数型言語の実装に副作用が必要なんてこんな気分の悪い事はありません。もしも lambda が唯一のプリミティブなら処理系が超シンプルになるのに。。。という美的理由がまずその一。
あと、最適化にも絶大な威力を発揮します。と、ちょっとこれは自信が無いのでよく分かってからまた書く予定。
結局、何の役に立つかと言う答えはまだ良く分からないのですが、予感としては自然界の超重要原理になる貫禄充分です。再帰はプログラミングのみならず、生命や宇宙の構造をつかさどる大原理です。その大原理が、
- Y = λg. (λx. g (x x)) (λx. g (x x))
(wikipedia にあった定義) という美しい姿をしているという事には感動を覚えます。
おまけ。不動点とは？
Y コンビネータは、別名不動点結合子と呼びます。なぜこんな呼び方をするのか書きます。不動点というのは、ある関数について、何度も繰り返し呼んでも結果が変わらない値の事です。例えば、f(x) = x^2 の不動点は 1 です。なぜかと言うと、1 = f(1) = f(f(1)) = f(f(f(1))) = ... という風に繰り返し呼んでも結果が変わらないからです。
話は突然変わりますが、私は幼少の頃電卓で遊ぶのが大好きで、特に同じ操作を繰り返しても不動点に陥らない操作を探すのが好きでした。例えば適当に 0.1234 と打ち込んで x のボタンを狂ったように押し続けると誤差の関係で最後は 0 になってしまうのですが、操作によっては割と面白いパターンが生まれるのです、後年藤本由紀夫氏がこれを使ってサウンドパフォーマンスをしているのを見たときは驚愕しました。関係ない話終わり。
つまり不動点 x とは、関数 f について f(x) = x になるような値の事を言います。では、x が値ではなくて関数だったらどうでしょう。ある高階関数 f について、f(x) = x となるような関数 x は、やっぱり f の不動点です。さて、不動点結合子 Y とは、どんな関数 f についても不動点 x を求める事の出来る関数です。
- Y(f) = x, f(x) = x,
- つまり、f(Y(f)) = Y(f) = x
これは上に上げたインチキ成分の定義と同じです。という事で、こういうのを不動点結合子と呼ぶそうです。
