おとうさん、ぼくにもYコンビネータがわかりましたよ！

やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。
名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。

まずλありき

関数の話をしたいのです。
そのとき、いちいち

hoge(x) = x * 2

としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。
そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、

λx.x*2

のように表記します。
というのがλ。
このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。

(λx.x*2)y

とあったら、xの部分をyでおきかえて

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

となります。λの引数部分を与えられた引数で置き換えることを簡約といいます。

(λx.xは暑いね)今日 →今日は暑いね

です。式が複雑になっても、冷静に置き換えれば大丈夫です。

これを動くコードで書くので、Javaで匿名クラス使いまくって書くのもいいんだけど、無意味にわけわからなくなるので、今回はGroovy使います。
Groovyだとこんな感じ

{x -> x * 2}

引数なんてひとつで十分だよね

関数には複数の引数をとるものがあります。
たとえばこんな感じ。

def func(x, y){x + y}

ここで、たとえばyを3に固定すると、引数ひとつの関数がつくれます。

def add3(x){func(x, 3)}

けど、この3の部分も指定できるようにしたいので、あとで指定してねという感じで、引数ひとつとる関数を返してしまいます。

def add(x){ {y -> func(x, y)}}

そうすると、add(5)としたときに引数をひとつとる関数を返してきます。なので(add(5))(3)とするとx+yが計算されるようになります。
クロージャで書き直すとこうです。

def add = {x -> {y -> func(x, y)}}

こうやって、複数の引数をとる関数を1引数の関数に変換することをカリー化といいます。カリー化のおかげで、関数のことを考えるときは1引数の関数だけを考えればいいということになります。
やったね！

λで条件分岐できるよね

カリー化のおかげで、λはひとつの引数をとる場合だけを考えればいいことになりました。
ここで、こんな関数を導入してみます。

true=λx.λy.x
false=λx.λy.y

そうすると、変数bがtrueかfalseをとるとして

b(0)(1)

とすると、bがtrueのとき0、falseのとき1を返します。
λで条件分岐ができた！

Groovyで書くとこう。

def tr = {x -> {y -> x}}
def fl = {x -> {y -> y}}

ついでに、booleanからλ版true/falseに変換するboolという関数を作っておきます。

def bool = {b -> b ? tr : fl}

そうすると、こんな感じで条件分岐が確認できます。

> bool(3 < 4)(2)(5)
2
> bool(3 < 1)(2)(5)
5

条件分岐しました！

補足(2011/11/16)

> tr(2)(5)

とすると2が

> fl(2)(5)

とすると5が返りますね。

そうすると

> var b=tr
> b(2)(5)
2
> var b=fl
> b(2)(5)
5

のようにbがtrなら2が、flなら5が返ります。

あとは、比較演算子をここでラムダで定義するのは面倒なので、Groobyのbooleanをtr/flに変換する関数boolを作っています。
比較演算子は、あとで出る引き算と同じ感じで定義することができます。

λでループは？

条件分岐ができたら、ループもやりたい！ここで出てくるのがYコンビネータです。
定義をそのまま書くと、こう。深く追わないのが吉。

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

で、ここに関数Mを考えてYを適用させるとこうなります。

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) = M(λx.M(xx))(λx.M(xx))

これは、上のYMの変換と同じです。このことから、こうなります。

M(YM)=YM

関数にその関数自身を適用させるときにYを適用させておくと、そのまま同じものが帰ってくるので、Yを不動点演算子といいます。
これを使うとλで再帰関数が表現できるようになります。再帰関数が表現できるということは、ループができるということです。条件分岐とループができるということは、あらゆる計算ができるということです。
λで計算ができることがわかりました！

YコンビネータをGroovyで書くとこうなります。

def Y = {f -> {x -> f(x(x))}({x -> f(x(x))})}

こいつを使ってフィボナッチをやってみましょう。

> println Y({f -> {n -> n < 2 ? n : f(n - 1) + f(n - 2)}})(7)
Exception in thread "main" java.lang.StackOverflowError

ぬぬ、スタックオーバーフロー。

これは、式がそのまま評価されてしまうことに問題があるようです。そこで遅延評価するための変換をいれてみます。
mをかましてみます。

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

そうすると、無事フィボナッチができます。

> println Z({f -> {n -> n < 2 ? n : f(n - 1) + f(n - 2)}})(7)
13

この変換を行ったものはZコンビネータというらしいです。ブログでみかける「Yコンビネータできたよ！」は、だいたいZコンビネータができています。

せっかくboolも作ったことなので、それを使ってみましょう。

> println YY({f -> {n -> bool(n < 2)(n)(f(n - 1) + f(n - 2))}})(7)
Exception in thread "main" java.lang.StackOverflowError

ぬぬ、またしてもオーバーフロー

これは、boolで真の場合も偽の場合の式もその場で評価されてしまって無限ループになってしまうためで、やっぱり遅延評価しないといけません。

> println YY({f -> {n -> bool(n < 2)({n})({f(n - 1) + f(n - 2)})()}})(7)
13

ということで、条件分岐とループが関数だけでできてしまいました。やりましたね！

数字もλであらわすよ

さて、制御構造がλであらわせたのですが、まだいろいろとλじゃないものが残っています。ということで、数字もλで表しましょう。

0=λf.λx.x
1=λf.λx.f(x)
2=λf.λx.f(f(x))

のように、関数fが値xに何回適用されたかで自然数を表します。チャーチの数字といいます。チャーチえらい！

これをGroovyで書いてみます。

def zero = {f -> {x -> x}}
def one = {f -> {x -> f(x)}}
def two = {f -> {x -> f(f(x))}}

これを整数に置き換えるには、0に+1が何回適用されたかという風に考えればいいので、こんな感じです。

> println zero({x -> x + 1})(0)
0
> println one({x -> x + 1})(0)
1
> println two({x -> x + 1})(0)
2

この、チャーチ数から整数への変換の関数を作っておきましょう。

def toInt = {n -> n({x -> x + 1})(0)}

で、すべての数字をいちいち定義するわけにもいかないので、1増やす演算をしてみます。

succ = λx.λf.λx.f(n f x)

とあらわせます。
Groovyで書くとこう。

def succ = {n -> {f -> {x -> f(n(f)(x))}}}

試してみます。

> println toInt(succ(two))
3

増えました！

フィボナッチしたいので、足し算したいですね。足し算はこうです。

add = λm.λn.λf.λx.nf(m f x)

Groovyで書けばこう。

def add = {m -> {n -> {f -> {x -> n(f(m(f)(x)))}}}}

試してみます

> println toInt(add(two)(two))
4

足せました！

さてλだけでフィボナッチ

フィボナッチやるには、比較や引き算もλでやる必要があります。
ということで、まず同値比較。ただ、同値比較はGroovy版λだけではだめで、一旦整数に変換しました。関数が同値かどうかをGroovyで判定できないので仕方ない。できるのかな？λ項の同値関係を判定するアルゴリズムが難しそう。
ということで、こんな関数を導入します。

def eq = {x -> {y -> toInt(x) == toInt(y) ? tr : fl}}

そうすると、こう使えます。

> println eq(one)(two)("わん")("つー")
つー
> println eq(succ(one))(two)("わん")("つー")
わん

さて、問題は引き算です。1引く関数を定義します。今回はZコンビネータ使ってループしました。

def pred = Z({g -> {n -> {m -> 
  eq(m)(succ(n))
    ({n})
    ({g(succ(n))(m)})
  ()}}})(zero)

使ってみます。

> println toInt(pred(add(two)(two)))
3

おー、引き算ができたようです。

ということで、フィボナッチの準備ができたので、やってみます。

def fib = Z({f -> {n ->
            (eq(n)(zero)
              ({zero})
              (eq(n)(one)
                  ({one})
                  ({plus(f(pred(n)))(f(pred(pred(n))))})
              )
            )()
          }})

できた！カッコだらけでLISPみたい！
ためしてみます。

> println toInt(fib( add(two)(add(two)(two)) ))
8
> println toInt(fib( succ(add(two)(add(two)(two))) ))
13

おー、これで基本的にλだけでフィボナッチができました！

ついでに対で

最後に、対を導入してみます。対さえ導入できれば、どんなデータ構造も実現できます。
対は、次のように定義できます。

(M, N) = λz. if z then M else N

そうすると、それぞれの項が、このようにして取れます。

first = λp.p true
second = λp.p false

ということで、Groovyでこんな定義をやってみます。

def pair = {m -> {n -> {c -> c(m)(n)}}}
def first = {p -> p(tr)}
def second = {p -> p(fl)}

ためしてみます。

> def a = pair(two)(succ(two))
lambda.YComb$_run_closure9_closure42_closure43@74c3aa
> println toInt(first(a))
2
> println toInt(second(a))
3

やりました！
これで、あとはがんばればλだけでクイックソートとかできそうです。
λすごい！世の中、全部関数です。

参考文献:
論理とλ計算の関係を、カリーハワードの対応でしめくくるとか、そういうのがまとめられた本。

論理と計算のしくみ