Y コンビネータって何？

このエントリの

親友へ。ブログを書こう。 - IT戦記
y がブログを始めたみたいなので、読んでみた。

で、最新のエントリを読んでみたら、

Y コンビネータというものについて書いてあったので、
Y Combinatorが凄すぎる！ - yuji1982の日記
Y コンビネータって何ってところから、自分でもいろいろ考えてみた。
結局なんなのかさっぱり分からなかったんですが、自分が考えたことをまとめておく

まず、フィボナッチ数を求める fib を定義する

var fib = function(n){
  return (n <= 2) ? 1 : (arguments.callee(n-1) + arguments.callee(n-2));
};
fib(10);

おお！ JS すげー！名前は n しか使ってねーよ！
めでたし、めでたし。。。。じゃなくて！

JS が素晴らし過ぎて話が終わってしまったので arguments.callee を禁止にして書いてみる

var fib = function f(n){
  return (n <= 2) ? 1 : (f(n-1) + f(n-2));
};
fib(10);

n, f だけ名前を使った！でも、グローバル汚染してない＞＜！ JS すげー！
めでたし、めでたし。。。。じゃなくて！

JS が素晴らし過ぎて話が終わってしまったので、名前付き関数定義を禁止にして書いてみる

var fib = function(n){
  return (n <= 2) ? 1 : (fib(n-1) + fib(n-2));
};
fib(10);

で、ここでの問題点を考える。

さきほどの fib ではグローバルなスコープに定義されているので、以下のように何げなく関数名を変更した場合動かないくなってしまいます。

var _fib = fib; // _fib という名前に fib 関数を代入
fib = null;        // 元の fib を消す

_fib(10); // 失敗する

どうやってこれを解決すればいいだろうか

以下のようにすればいい。

var fib = (function() {
  var fib = function(n){
    return (n <= 2) ? 1 : (fib(n-1) + fib(n-2));
  };
  return fib;
})();
fib(10)

これが Y コンビネータの原点なのかもしれないとか思った。なんとなく。でも関係ないなたぶん

で、本題に入る

λ計算というものの話になる。λ計算とは JS の世界でいうと = を使わない、関数自体に名前を付けない、関数は引数 1 個か 0 個しか持たない、関数は一つの return 文だけを持つ JavaScript の式ということなのかな？と思っています。違う？
これが何に役立つかわ分かりません。ただ、すべての計算はこれで表現できるらしいです。そのことが何なのかは僕には分かりません。

という訳で

これを

var fib = (function() {
  var fib = function(n){
    return (n <= 2) ? 1 : (fib(n-1) + fib(n-2));
  };
  return fib;
})();
fib(10)

そういう風に変換していってみる

まずグローバルの fib を無くす

var fib = (function() {
  var fib = function(n){
    return (n <= 2) ? 1 : (fib(n-1) + fib(n-2));
  };
  return fib;
})();
fib(10)

ここで、関数の呼び名を決めておきましょう

(function() {
  // ↓これを外の関数
  var fib = function(n){
    // ↓これを中の関数
    return (n <= 2) ? 1 : (fib(n-1) + fib(n-2));
  };
  return fib;
})()(10);

と呼ぶ事にします。

ローカルの fib を無くしたい

このコードは動かないです。

(function(f) {   // ← ここに中の関数を入れられればローカルの fib を無くせる
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})()(10);

さらに、外の関数を別の関数で受け取ってみる

このコードは動かないです。

(function(f) {   // ← ここに外の関数を入れた
  return f(/* ここに中の関数を入れられれば */)
})(function(f) { // ← ここに中の関数が入ってくるはず
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらに、考える

(function(f) {
  return f(/* ここに中の関数を入れられれば、この関数は中の関数を返すはず */)
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらにこうする

(function(f) {           // この関数は f に「中の関数」を入れれば、「中の関数」を返す
  return function g(m) { // ↑が成り立つと ↓ の f も「中の関数」を返す 
    return f(g)(m);
  };
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらに、考える

(function(f) {           
  return function g(m) { // さらに前に考えたことが成り立つと 
    return f(g)(m);      // g は「中の関数」にそのまま引数を渡すので、 g は「中の関数」と同じことをする関数を返す。
  };
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらに、考える

(function(f) {            // はじめの一回は必ずここに「外の関数」が入ってくる
  return function g(m) {
    return f(g)(m);
  };
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

ということは、帰納的に考えていくと

以下の式を評価すると、正しく 10 のフィボナッチ数を返すということになる。

(function(f) {
  return function g(m) {
    return f(g)(m);
  };
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

すげー！

次に、関数 g の名前を消すことを考える

まず、以下のようにしてみる

(function(f) {
  var g = function(m) {
    return f(g)(m);
  };
  return g;
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらに、考える

(function(f) {
  var g = function() {     // 
    return function(m) {   // さっきの g を無名にして g を返す関数を作った
      return f(g())(m);
    };
  }
  return g();
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらに、考える

(function(f) {
  var g = function(g) {
    return function(m) {
      return f(g(g))(m);   // ここの g を引数で受け取るようにした
    };
  }
  return g(g);             // ここで g に g を渡す
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

さらに、考える

(function(f) {
  return (function(g) {     // g に g を渡す部分を二つの同じリテラルにした
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
})(function(f) {
  return function(n){
    return (n <= 2) ? 1 : (f(n-1) + f(n-2));
  };
})(10);

実は、これでλ計算になっている。

そして、

以下の部分を Y コンビネータと言うらしい

function(f) {
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
}

そして、

Y コンビネータはすべての再帰的な式を λ 計算に変換する事ができる

たとえば

以下のように

(function(Y){ // ← Y コンビネータ

  // 10 のようにすると 10 の階乗が求まる
  return Y(function(fact) {  
    return function(n) {                       // ← 無名関数
      return (n == 1) ? 1 : (n * fact(n - 1)); // ← なのに再帰っぽく
    };
  })(10)

// 以下 Y コンビネータ本体
})(function(f) {
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
})

というわけで Y コンビネータを取り巻く現象は理解した

しかし、「式がすべて λ 計算に変換できる」という考え方が具体的にどのように役にたつかが分からない＞＜

まとめ

Y コンビネータいみふ＞＜！