Y/Zコンビネーターについて理解するまで

最近「アンダースタンディング コンピュテーション」という本を読んでいる。

アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで
Tom Stuart
オライリージャパン
売り上げランキング: 155,740


  

前半が形式言語とオートマトンの話で、決定性有限オートマトン→非決定性有限オートマトン→決定性プッシュダウンオートマトン→非決定性プッシュダウンオートマトン→決定性チューリングマシン→非決定性チューリングマシン、というように簡単なものから最強のものまで一巡りする。

後半はラムダ計算とプログラミング?。RubyのProcだけでプログラムを書いてやろうという試みから始まる。(当然「int」とかも使わない。)型なしラムダ計算風のものをRubyで実装しようということである。
この章にものすごい詰まるポイントが出てきた。それが表題のYコンビネーター。
ちなみにこの本ではラムダ計算もRubyでやってるんだけど、絶対Javascriptのほうがわかりやすいと思う…。Rubyでは構文解析→AST構築用のライブラリがあるというのが強みだけど、ラムダ式をProcで書くのは読みづらい。

このYコンビネーターを理解するのに3日くらいかかったけど、その三日間の中で一番役に立った記事が以下の記事。

ここで改めてYコンビネーターの説明するのも面倒なのでぜひこの記事を読んで勉強してほしい。。。
でもこの記事だけだとわかりにくい点も多々あると思うので二点ほど補足説明。(本当はこの記事で出てくるのはYコンビネーターじゃなくてZコンビネーターというところも補足しておきたい…※)

まず「Yコンビネーターとは何か」というと、ラムダ計算で再帰を実現するために必要なものだそうだ。
普通再帰というと、

    function bikkuri(n) {  //アホみたいな名前だけど階乗
      if (n <= 0) {
        return 1;
     } else {
          return n * bikkuri(n-1);
      }
     } 

といったように関数内で自分の名前を呼ぶことで自分を再帰呼び出しする。でも関数に名前をつけることができないとしたら?(ラムダ計算なので)当然自分に名前がないので、自分を呼ぶことができない。

function (n) { 
  if (n <= 0) { 
    return 1;
  } else {
      return n * ???(n-1);
  }
 }

これを解決するのがYコンビネーター。Yコンビネーターの基本的な考えとしては、さきほどのbikkuriのように再帰する関数の引数にその関数自身を渡すというもの。

 function (f, n) {  //fはこの関数と同じ関数
  if (n <= 0) {
    return 1;
  } else {
      return n * f(n-1);
  }
 }

これがわかるだけで、Yコンビネーターが何をやっているかとてもイメージしやすくなった。
Yコンビネーターは(λg. (λx. g(x x)) (λx. g(x x)))と表わされるけど、ここでなんでxxなんてのがでてくるのかの理由が以上でわかると思う。(xという表記がわかりにくさを生む原因なんだけど、このxは値じゃなくて関数が入るところ)
gという関数は、関数xを与えると内部でその関数xを呼ぶ関数x'を返す関数である。そしてその関数xが中で関数x自身を呼ぶために関数xに関数xを渡しておく、というのがg(x x)のだいたいの意味。(これも表記がわかりづらい。g(x(x))と書いてくれればいいのに。)

そして、もう一点。
ラムダ式を書いているといったいこれはなんなのかわからなくなってしまうことがある。こういう場合、きちんと各部分がなんなのか線を引きながら読むとわかりやすくなる。
(λx.(x+2)) 1 が

(function (n) {
  return n + 2;
})(1);

となるのはすぐわかると思うけど、(λf.(λx.f(λy.xxy))(λf.(λx.f(λy.xxy)))Mという式を与えられると一体何がなんなのか見失いやすい。これは

(function (f) {
  return ( (λx.f(λy.xxy))(λx.f(λy.xxy))に相当する関数)
})(M);

という意味。

この二点を頭に入れたうえではじめに紹介した記事を読めばきっと理解できるはず。

※RubyやJavascript、というか世の中のほとんどのプログラム言語では評価戦略の都合上Yコンビネーターを使うと無限に再帰呼び出しが発生してスタックオーバーフローを起こすそうだ。このためYコンビネーターをちょっと変えたZコンビネーターを使う。
正直ここについては完全に理解していないので間違っているかもしれないが、さっきの階乗計算の例で考えると、

    function bikkuri(n) {
      if (n <= 0) {
        return 1;
     } else {
          return n * bikkuri(n-1);
      }
     } 

これはnが与えられ条件が評価されたうえでif節かelse節のどちらかだけを評価する。なので適切な引数が与えられれば再帰呼び出しのゴールにいずれたどり着くので無限ループにならない。(bikkuri("a");とかやってみれば…)
しかしYコンビネーターを使った再帰的な関数呼び出しは各再帰的関数呼び出しステップで具体的な引数が与えられるまえに再帰的な関数を返すようになっている。なので無限ループを起こす。
そこで各再帰的関数呼び出しステップでちゃんと引数を与えて条件の評価を可能にすることで、if節かelse節どちらかだけを評価すればいいように改良したのがZコンビネーター、ということだと思っている。
プログラミング系の記事で「Yコンビネーター」という言葉が出てきたら基本的にZコンビネーターをさしているんだけど、言葉選びは気をつけたほうがいいと思いますね。