YコンビネータとZコンビネータ（Ruby）

qiita.comこの記事がおもしろかったので色いろぐぐっていたら、すばらしくわかりやすいサイトがあった。

d.hatena.ne.jpわかりやすいので、いっぱいブクマがついております。以下これを参考にして、メモしておきます。

まずラムダ式であるが、

f(x) = x * 2

と書く代わりに、f というような識別子は余分だとして

λx.x * 2

というように書く。そして、これをカッコで括って後に例えば y をくっつけると、

(λx.x * 2)y → y * 2

のように変換されるものとする。これは見てのとおり一変数しか使えない関数式であるが、これらの組み合わせの工夫で多変数関数も表現できるのである（カリー化）。これがラムダ計算である。

具体的には Ruby でこんな感じ。

f = ->(x, y) {x + y}
f[5, 3]       #=>8

add3 = ->(x) {x + 3}
add3[5]       #=>8

add = ->(x) { ->(y) {x + y} }
add[5][3]     #=>8

Proc#curry を使うと

add = ->(x, y) {x + y}.curry
add[5][3]     #=>8

ラムダ計算で「繰り返し」を実装できる。そのひとつが「Yコンビネータ」である。これは天下り的に

Y = λf.(λx.f(xx))(λx.f(xx))

と与えられる。さて、これに関数 M を作用させてみよう。定義どおりに地道に計算すると、

YM = (λf.(λx.f(xx))(λx.f(xx)))M
   = (λx.M(xx))(λx.M(xx))
   = M((λx.M(xx)(λx.M(xx)))
   = M(YM)

となる。つまり YM = M(YM) となって再帰するのだ。これを繰り返すと

YM = M(YM) = M(M(YM)) = M(M(M(YM))) = ...

となって無限に続く。なので、これを単純に Ruby で実装すると、Ruby の lambda は値渡しなので、関数定義が無限にネストして「スタックオーバーフロー」となってしまう（ここを参照）。

Yコンビネータのようなものを「不動点コンビネータ」というが、不動点コンビネータには「Zコンビネータ」というのもある。これも天下り式に

Z = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))

と与えておこう。これも同様に関数 M を作用させ、地道に計算してみる。

ZM = (λf.(λx.f(λy.xxy))(λx.f(λy.xxy)))M
   = (λx.M(λy.xxy))(λx.M(λy.xxy))
   = M(λy.(λx.M(λy.xxy))(λx.M(λy.xxy))y)
   = M(λy.ZMy)

となる。ここで ZM = A とおくと

A = M(λy.Ay)

であり、関数 A に値 a を代入すれば

Aa = M((λy.Ay)a) = M(Aa)

となってこれも再帰する。しかしこれならば関数定義そのものはネストしておらず、すなわち一種の「遅延評価」をしていることになって、値渡しの Ruby でも実装が可能である。Ruby での実装は、先ほどのサイトのものをありがたく使わせてもらおう。

Z = ->(f) {
  ->(x){
    f.(
      ->(y) {x.(x).(y)}
    )
  }.(
    ->(x){
      f.(
        ->(y) {x.(x).(y)}
      )
    }
  )
}

Z[
  ->(x) {
    ->(n) { (n == 0) ? 1 : n * x[n - 1] }
  }
][5]
#=>120

Zコンビネータと無名関数だけで、一切の識別子なしに 5 の階乗を求めている。

なお、「きしだのはてな」の記事のように、YコンビネータとZコンビネータを並べて書いてみると、

Y = ->(f) { ->(x) {f[x[x]]} [->(x) {f[x[x]]}] }
Z = ->(f) { ->(x) {->(m) { f[x[x]][m] }} [->(x) {->(m) { f[x[x]][m]} }] }

となって、ZコンビネータがYコンビネータに遅延評価（mの部分）を咬ませただけのものだということがはっきりすると思う。（なお、この「きしだのはてな」のZコンビネータは、上の定義どおりではない。）

※追記
LambdaDriver を使って書くとこうなる。

require 'lambda_driver'
Y = ->(f) {->(x) {f < x < x} < ->(x) {f < x < x}}
Z = ->(f) {->(x) {f < ->(y) {x < x < y}} < ->(x) {f < ->(y) {x < x < y}}}
Z < ->(x) {->(n) { (n == 0) ? 1 : n * (x < n - 1) }} < 5
#=>120

「きしだのはてな」の方のはこう。

Z = ->(f) {->(x) {->(m) {(f < (x < x)) < m}} < ->(x) {->(m) {(f < (x < x)) < m}}}

フィボナッチ数列の実装。

Z < ->(f) {->(n) { (n < 2) ? n : f[n - 1] + f[n - 2]}} < 7
#=>13

※参考
不動点コンビネータ - Wikipedia