ベンチャーキャピタルの Y コンビネーターはラムダ計算の Y コンビネーターから名付けられている。その Y コンビネーターについて JavaScript での説明をメモっとく。
階乗の再帰的な関数定義
JavaScript で階乗を再帰的に定義して、5の階乗を求めるとこうなる。
function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
factorial(5); // => 120
この場合 factorial という名前で関数を定義しているので再帰的に関数呼び出しができている。しかし Y コンビネーターを使うと無名関数での再帰的な関数呼び出しが実現できてしまう。まあ、JavaScript だと arguments.callee で下記のように実現できてしまうのだけど、arguments.callee を使わなくても実現できちゃうんだよってことを説明する。
(function(n) {
return n == 0 ? 1 : n * arguments.callee(n - 1);
})(5); // => 120
この投稿は知的好奇心を満たせるかもしれないけど、仕事ではあまり役に立たないかなと思う。
0の階乗を求める再帰できない無名関数
無名関数を定義しよう。前述の arguments.callee を fact に置き換えておく。fact は存在していないのだけど、0の階乗は計算できる。
(function(n) {
return n == 0 ? 1 : n * fact(n - 1);
})(0); // => 1
1の階乗は計算できない。
(function(n) {
return n == 0 ? 1 : n * fact(n - 1);
})(1); // => ReferenceError: fact is not defined
1の階乗を求める1回再帰できる無名関数
この先に進むには fact が必要だ。とりあえず仮引数に追加しよう。でも fact は undefined なので結局計算できない。JavaScript はアリティ（引数の数）が不一致でも実行できるけど足りない引数は undefined になる。
(function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1);
})(1); // => TypeError: fact is not a function
関数を渡してあげよう。fact は何か思い出してみると、本来は再帰なので自分自身になる。そうすると1の階乗を求められる。
(function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1);
})(1, function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1);
}); // => 1
コードを理解するために一部分を置き換えてみると、下記のような構造になってることがわかる。
var FACT = function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1);
};
FACT(1, FACT); // => 1
さて2の階乗はどうだろう？まあ予想通りの結果だね。
(function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1);
})(2, function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1);
}); // => TypeError: fact is not a function
階乗を求める再帰できる無名関数
2回目の再帰で fact が undefined になってしまうから失敗する。1回目の再帰で2つ目の引数を渡してないからね。
ということで呼び出す関数を渡してあげよう。これで2の階乗を求められる。
(function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1, fact);
})(2, function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1, fact);
}); // => 2
5の階乗も求められる。一旦は完成だ。
(function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1, fact);
})(5, function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1, fact);
}); // => 120
無名関数の引数を独立させる
階乗を求めたい数が無名関数の中にいるので独立させたい。
改めてコードの一部分を置き換えてみよう。
var FACT = function(n, fact) {
return n == 0 ? 1 : n * fact(n - 1, fact);
};
FACT(5, FACT); // => 120
これをこの形にしたい。いわゆるカリー化ってやつだ。
var FACT = ???;
FACT(FACT)(5); // => 120
FACT に FACT を渡して返ってきた関数に5を渡す。関数に関数を渡して返ってきた関数に数値を渡す感じ。
var FACT = function(fact) { // 関数を受け取る
return function(n) { // 数値を受け取る
return n == 0 ? 1 : n * fact(fact)(n - 1); // 再帰もカリー化
};
};
FACT(FACT)(5); // => 120
これを展開するとこうなる。
(function(fact) {
return function(n) {
return n == 0 ? 1 : n * fact(fact)(n - 1);
}
})(function(fact) {
return function(n) {
return n == 0 ? 1 : n * fact(fact)(n - 1);
}
})(5); // => 120
重複を取り除く
重複を取り除いて DRY にしよう。
var FACT = function(fact) {
return function(n) {
return n == 0 ? 1 : n * fact(fact)(n - 1);
};
};
(function(fact) {
return fact(fact);
})(FACT)(5); // => 120
展開する。ちょっと複雑になってきた。
(function(fact) {
return fact(fact);
})(function(fact) {
return function(n) {
return n == 0 ? 1 : n * fact(fact)(n - 1);
};
})(5); // => 120
fact(fact) を factorial にする
階乗の再帰部分の fact(fact) を factorial にしたい。
改めてコードの一部分を置き換えて整理してみる。
var FACT = function(fact) {
var SUBFACT = function(n) {
return n == 0 ? 1 : n * fact(fact)(n - 1);
};
return SUBFACT;
};
(function(fact) {
return fact(fact);
})(FACT)(5); // => 120
階乗の再帰部分の fact(fact) を factorial にしてみる。単純にやってしまうとエラーになる。fact(fact) で無限に評価してコールスタックを使い果たしてしまうからだ。
var FACT = function(fact) {
var SUBFACT = (function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
})(fact(fact));
return SUBFACT;
};
(function(fact) {
return fact(fact);
})(FACT)(5); // => RangeError: Maximum call stack size exceeded
fact(fact) を無限に評価しないように細工する。
var FACT = function(fact) {
var SUBFACT = (function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
})(function(x) {
return fact(fact)(x);
});
return SUBFACT;
};
(function(fact) {
return fact(fact);
})(FACT)(5); // => 120
展開する。このあたりまで読んだら、もう一度最初から読み直すといいかもしれない。何を目指してたのかがわからなくなってくるかもしれないから。
(function(fact) {
return fact(fact);
})(function(fact) {
return (function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
})(function(x) {
return fact(fact)(x);
});
})(5); // => 120
無名関数を再帰する仕組みと階乗を計算する仕組みを分離する
無名関数を再帰する仕組みは一般化できるはずなので、階乗を計算する仕組みと分離する。
コードを整理する。どこを FA に置き換えたかわかるだろうか。
var FA = function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
};
(function(fact) {
return fact(fact);
})(function(fact) {
return FA(function(x) {
return fact(fact)(x);
});
})(5); // => 120
FA を独立させる。このパターンに慣れてきていると嬉しい。
var FA = function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
};
(function(fa) {
return (function(fact) {
return fact(fact);
})(function(fact) {
return fa(function(x) {
return fact(fact)(x);
});
});
})(FA)(5); // => 120
展開する。ここが一番複雑だ。あと少し。
(function(fa) {
return (function(fact) {
return fact(fact);
})(function(fact) {
return fa(function(x) {
return fact(fact)(x);
});
});
})(function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
})(5); // => 120
適応順 Y コンビネーター
最初の無名関数部分が適応順 Y コンビーネーター（Z コンビネーター）だ。Wikipedia にも似たようなコードが掲載されているけど、手順を踏んでみないと中々理解できない関数だ。引数名などを整理すると下記のような感じだ。
var Y = function(f) {
return (function(g) {
return g(g);
})(function(g) {
return f(function(x) {
return g(g)(x);
});
});
};
Y コンビネーターを利用して階乗を再帰的に実行してみる。
Y(function(factorial) {
return function(n) {
return n == 0 ? 1 : n * factorial(n - 1);
};
})(5); // => 120
Y コンビネーターってこういうものなのだ。知的好奇心は満たせただろうか？
参考文献
Scheme 手習い