Y combinator
最近は残業と休日出勤ばかりでうんざりの KrdLab です．
今回はちょっと毛色の違う話題を．内容はいつの間にか自分用のまとめになってしまいましたが．．．
Y combinator とは？
不動点コンビネータの一種．
不動点とは，ある関数 F を定義したとき，F(p) = p となる p のことを指す．ここで p を関数にまで拡張して考えてみる．すなわち関数 F は高階関数となる．この関数 F の不動点 p を返すような関数 g を考えると，p = g(F) の様に表すことができる．このとき関数 g を不動点コンビネータと呼ぶ．
特にラムダ計算では，
g := λf. (λx. f(x x)) (λx. f(x x))
と表される Y combinator がよく知られている．
なお，combinator については Combinatory logic - Wikipedia, the free encyclopedia にて以下のように説明されている．
A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments. [引用]
combinator は，自身の定義に自由識別子 (自由変数と呼ばれる場合もある) が含まれていないため，実行時の環境に因らず，引数 (束縛された識別子) のみから自身の出力が決まる．
性質
不動点の関係を表しているのだから，g(F) = YF = p，かつ F(p) = p より，F(YF) = YF となるはず．実際に適用を進めると，確かにその性質が認められる．
YF = (λf. (λx. f(x x)) (λx. f(x x)))F = (λx. F(x x)) (λx. F(x x)) = F((λx. F(x x)) (λx. F(x x))) = F(YF)
さらに適用を続けると，以下のように再帰構造が現れる．
= F(F(YF)) = F(F(F...
つまり不動点 YF は，「関数を引数にとって関数を返す」関数 F による再帰を表しているとも解釈できる．
何ができるのか？
ラムダ式で再帰を表現することができる (つまり繰り返しを表現できる)．このような再帰を無名再帰と呼ぶ．
ここでは階乗計算を例に説明する．プログラムでフツーに書けば以下のようになる．
fact 0 = 1 fact (n + 1) = (n + 1) * fact n
これをラムダ式のみで表すために Y を用いる．前述の性質から，「F の繰り返し適用 (再帰) の結果得られる関数」を表す YF に n を渡したものが，fact n と等しくなるような F を定義すればよい．
イメージとしては fact(n) := YFn = F(YF)n より，F は関数と数値を引数にとればよいことがわかる．
コードで書くと以下のような感じになる (大文字始まりなのは気にしないでください)．
F = \f n -> case n of 0 -> 1 (m + 1) -> n * f m
上記 F に Y を適用することで引数 f は YF となり，再帰構造が生まれる．
よって，目的の fact は以下のようになる (大文字始まりなのは気にしないでください)．
fact = Y F -- ↓ Y (\f n -> case n of 0 -> 1 (m + 1) -> n * f m)
実際に引数を与えると以下のように関数適用が進み，階乗計算が実現される (ラムダ式は長いので便宜上 F と表記しています)．
(Y F) 3 -> F (Y F) 3
-> 3 * (Y F) 2
-> 3 * (F (Y F) 2)
-> 3 * (2 * (Y F) 1)
-> 3 * (2 * (F (Y F) 1))
-> 3 * (2 * (1 * (Y F) 0))
-> 3 * (2 * (1 * (F (Y F) 0)))
-> 3 * (2 * (1 * (1)))
-> 6以上により，Y combinator を用いることで無名再帰を実現できたことがわかる．
