Yコンビネータにトライ

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

きしだんさんすごいっす。自分も学習のために、ラムダの復習も兼ねつつJavaScriptでトライしてみる。独学で適当にやってるので間違いも多数あると思いますが、ご容赦を。

ラムダ
ラムダ式は、関数の表現形式みたいなもので、おおよそfunction式に相当する。引数が複数あるのが違うところだけど、この話は後で解決する。（非形式的な）ラムダ式ってこんなもの。
λx.x*2
このラムダ式は、xを受け取ったら2倍して返す関数を表している。
最初は読むのに（特にλ記号が複数になった場合に）とても苦労したんだけど、引数を「λ」と「.」で挟み込む形で表現した関数だ、と考えるとずいぶん読みやすくなった。これをJavaScriptで表すと…
function(x) { return x * 2 }
こうなる。ラムダ計算の体系では、計算のすべてをラムダ式であらわす。ラムダ式は関数なので、計算のすべてを関数であらわすということだ。ということで、JavaScriptから余計なものをそぎ落としていきましょー。

カリー化
さっきも少し出てきたけど、もともとのラムダ計算体系ではすべての関数は1引数関数として扱う。一般にラムダ計算体系では…
f(x, y) = f(x)(y)
が成り立つ（理屈は省略）ので、多引数の関数はすべて1引数の関数に変換できる。こうすれば、多引数のことあんま考えなくてもいいから、世界がシンプルになる。たぶん。
で、カリー化とは、上記左辺の f(x, y) から f(x)(f) への変換のことを言う。Haskellとかで関数の部分適用の話が出てくるけど、Haskellの関数はすべてカリー化されている（1引数関数である）ので、部分適用といっても単に、順番に関数適用しているだけなんだと思う。

JavaScriptの関数は引数を複数取ることができるが、上記の法則によって、必ず1引数の関数に変換できる。関数や引数が特定された形であれば、特別な機構がなくてもカリー化はできる。
function func(x, y) { return x + y }
この関数を引数3でカリー化（＋部分適用）したければ…
curried_func = function(x) { return func(x, 3) }
こうすればいい。
# これをカリー化とか部分適用というかどうかは甚だ疑問だが、とりあえずイメージってことで…。
でも、これだと関数や引数が変わるたびにガリガリコードを書かなければいけないので、嬉しくない。どんな関数や引数でもカリー化できる機構があれば楽ちんだ。
JavaScriptには関数をカリー化する標準的な機構は用意されていないんだけど、カリー化する関数を作る事はできる。カリー化関数の実装にはいくつかバリエーションがあるんだけど、ここではわかりやすさを重視して nanto_vi さんのカリー化関数を使わせていただくことにする。
function curry(f) {
 if (f.length == 0) return f;
   function iterate(args) {
     if (args.length >= f.length)
       return f.apply(null, args);
     return function () {
       return iterate(args.concat(Array.prototype.slice.call(arguments)));
     };
   }
 return iterate([]);
}
これを使えば、どんな関数でもカリー化できる。元ネタの例を拝借して、2引数の以下のような関数をカリー化してみる。
function add(x, y) { return x + y }
curry関数を使って…
var curried_add = curry(func(x, y))
これで、1引数関数になった。
curried_add(1)(2)
> 3
OK。間にごちゃごちゃはさまるものの、関数は1引数だけ考えればよくなった。また1つ、世の中が単純になった。本当か？

ラムダで条件分岐
じゃ、次は1引数関数で条件分岐ができるようにしてみる。これができれば、if文なんていう特別な構文を用意しなくても if文相当のプログラムが書けるわけで、世界は単純なまま進行する（JavaScriptで言うなら、if文を忘れ去ることができる）わけだ。よーし、じゃあif関数みたいなものを作るぞ！こんな風に動けばいいよね。
myIf (b)(exp1)(exp2)
…しかしmyIfで全部やろうとすると…
var myIf = curry(function (b, exp1, exp2) {
 return b ? exp1 : exp2
}
結局は内部に if文相当のもの（ここでは3項演算子だけど）が出てきてしまう。余分なものをそぎ落とすのが基本方針なので、やはりきしださんと同じアプローチを取る。
関数はすべて1引数なので、if関数が条件として真偽値をとらなければならないなら、真偽値自体が実行する関数を選ばなくてはならない。とうわけで、真偽値を関数として定義する。ラムダ式で書くとこんな感じ。
true=λx.λy.x
false=λx.λy.y
trueは、xとyを順に適用すると、xを返す関数。falseは、xとyを順番に適用するとyを返す関数として定義している。JavaScriptで書くと、こんな風になる。
var myTrue = curry(function(x, y) { return x })
var myFalse = curry(function(x, y){ return y })
// trueやfalseは予約語だから使えない
さて、条件分岐を書いてみよう。せっかくだから右の扉を…じゃなくて if っぽい関数を書いてみよう。全然型安全じゃないのがアレな感じだけど、とりあえず気にしない。
var myIf = function(x) { return x }
myIf(myFalse)(0)(1)
> 1
条件分岐できた。一応 (my)True も試しておく。条件分岐後に関数が実行されるようにもしてみる。
myIf(myTrue)(curried_add(1, 2, 3))(10)
> 6
OK。なんかカッコだらけなんですけど…。言語はシンプルだけど、世の中はどんどん複雑になっていっている気も。

さて、今のままだと、JavaScript の bool値はまったく使えない。ifを忘れ去るんだし、別になくても問題ない（というかなくしたい）んだけど、一応 JavaScript の bool と myTrue/myFalse/myIf をブリッジするための関数も用意してみる。
var bool = function(b) { return b ? myTrue : myFalse }
myIf の JS boolean バージョン。
myIf(bool(true))(curried_add(1, 2, 3))(10)
> 6
OK。振り返ってみると、真偽値自体を
  • Trueの場合は1番目の式を評価する関数
  • Falseの場合は2番目の式を評価する関数
このように定義することで条件分岐を可能にする、というアイディアだったわけですね。たぶん。

ラムダでループ
やっと本題にきたよ！さて、世界をシンプルに保つために、今度は関数でループできるかやってみよう。関数だけでループするためには、再帰を使えば良いよね。
フィボナッチを考えてみよう。とりあえずはプレーンなJavaScriptで。
function fib(n) {
 if(n < 2) { return n }
 else { return fib(n - 1) + fib(n - 2) }
}
ここでは、fib関数の中で自分自身（fib）を呼び出す事で再帰を実現している。普通に関数で計算を表現するだけなら、別にこれで十分だと思う。myIfで書き直したいんだけど、自然数とか比較とか（+とかも）作ってないからとりあえずこのまま ^^;

ただし、ラムダ計算の世界では自分自身を含む関数を定義することができない。せっかくなので、自分自身への呼び出しを取り除いて、ラムダ計算の体系に沿うように考えてみよう。

自分自身を呼び出すように記述できないのなら、自分自身を表す関数を引数に取って、その関数を呼び出せばいいのでは？と一瞬思ったが、結局それ、自分自身を呼び出してるよな…。

じゃあ、自分自身みたいだけど自分自身じゃない関数（fake_fibとでもしよう）が引数としてわたってきて、その関数を呼び出すことで間接的に自分自身が呼び出されるようにするのはどうだろう？JavaScriptで書くと、こんな感じ。
function fib(fake_fib, n) {
 if (n < 2) { return n }
  else { return fake_fib(n - 1) + fake_fib(n - 2) }
}
fake_fib(n - 1)呼び出しが、さらにfib(fake_fib, n - 1)を呼んでくれれば再帰が実現できることになるのでは？fibを g に、fake_fib を f にして簡潔に書きなおすと…
function g(f, n) {
 if (n < 2) { return n }
 else { return f(n - 1) + f(n - 2) }
}
こんな感じ。で、f(n - 1) が g(f, n - 1) に（1引数の世界で言えば、f が g(f) に）展開されれば再帰が実現できるはず。というわけで、展開するとg(f)になるような f、つまり
f = g(f)
となるような f を見つける、という問題に帰結する。このような条件を満たす f は一般的に「不動点」と呼ばれており、以下のようなラムダ式で表すことができることが知られている。
Y = λg.(λx.g(xx))(λx.g(xx))
これがいわゆるYコンビネータってやつらしい。
# このラムダ式がさきほどの条件を満たすことは、きしださんのところに書いてあるとおり、試してみればわかる。これをJavaScriptで書いてみると、
function Y(f) {
 return function(x) {
   return f(x(x))
 }(function (x) {
   return f(x(x))
 });
}
# ナンダコレハ…。
こうなる。これを使う形で、あらためてフィボナッチをJavaScriptでちゃんと書くと、こんな感じになる。
var fib2 = curry(function(f, n){
 if(n < 2) {return n }
 else {return f(n - 1) + f(n - 2)}
})
実際に呼び出すには、Yを使ってこんな感じで呼べばいい。
Y(fib2)(10)
> InternalError: too much recursion
しかし、こちらも同じく再帰エラー。まねっこしてZコンビネータを作ってみよう。
function Z(f) {
 return function(x) {
   return function(m) {
     return f(x(x))(m)
   }
 }(function(x) {
   return function(m) {
     return f(x(x))(m)
   }
 })
}
…なんかもう慣れてきた。呼び出し。
Z(fib2)(10)
> 55
えええ！動いちゃったよ！そりゃ動くように作ったけどさ！

で、これで何ができるかっていうと…自分自身を参照しなくても、再帰が書ける。だから、無名関数でも再帰が書ける。他にどんな良いことがあるかというと、相変わらずよくわからない ^^; ラムダ計算の体系に沿って計算を組み立てておくことで、何か良いことがあるのだろうか。

チャーチ数とかもやってみようと思ったけど、力尽きた。続く…かもしれない。

コメント

コメントを投稿