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