JavaScript で Y コンビネーターを理解する


ベンチャーキャピタルの Y コンビネーターはラムダ計算の Y コンビネーターから名付けられている。その Y コンビネーターについて JavaScript での説明をメモっとく。

# 階乗の再帰的な関数定義

JavaScript で階乗を再帰的に定義して、5の階乗を求めるとこうなる。

```js
function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}
factorial(5); // => 120
```

この場合 `factorial` という名前で関数を定義しているので再帰的に関数呼び出しができている。しかし Y コンビネーターを使うと無名関数での再帰的な関数呼び出しが実現できてしまう。まあ、JavaScript だと `arguments.callee` で下記のように実現できてしまうのだけど、`arguments.callee` を使わなくても実現できちゃうんだよってことを説明する。

```js
(function(n) {
    return n == 0 ? 1 : n * arguments.callee(n - 1);
})(5); // => 120
```

この投稿は知的好奇心を満たせるかもしれないけど、仕事ではあまり役に立たないかなと思う。

# 0の階乗を求める再帰できない無名関数

無名関数を定義しよう。前述の `arguments.callee` を `fact` に置き換えておく。`fact` は存在していないのだけど、0の階乗は計算できる。

```js
(function(n) {
    return n == 0 ? 1 : n * fact(n - 1);
})(0); // => 1
```

1の階乗は計算できない。

```js
(function(n) {
    return n == 0 ? 1 : n * fact(n - 1);
})(1); // => ReferenceError: fact is not defined
```

# 1の階乗を求める1回再帰できる無名関数

この先に進むには `fact` が必要だ。とりあえず仮引数に追加しよう。でも `fact` は `undefined` なので結局計算できない。JavaScript はアリティ（引数の数）が不一致でも実行できるけど足りない引数は `undefined` になる。

```js
(function(n, fact) {
    return n == 0 ? 1 : n * fact(n - 1);
})(1); // => TypeError: fact is not a function
```

関数を渡してあげよう。`fact` は何か思い出してみると、本来は再帰なので自分自身になる。そうすると1の階乗を求められる。

```js
(function(n, fact) {
    return n == 0 ? 1 : n * fact(n - 1);
})(1, function(n, fact) {
    return n == 0 ? 1 : n * fact(n - 1);
}); // => 1
```

コードを理解するために一部分を置き換えてみると、下記のような構造になってることがわかる。

```js
var FACT = function(n, fact) {
    return n == 0 ? 1 : n * fact(n - 1);
};

FACT(1, FACT); // => 1
```

さて2の階乗はどうだろう？まあ予想通りの結果だね。

```js
(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の階乗を求められる。

```js
(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の階乗も求められる。一旦は完成だ。

```js
(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
```

# 無名関数の引数を独立させる

階乗を求めたい数が無名関数の中にいるので独立させたい。

改めてコードの一部分を置き換えてみよう。

```js
var FACT = function(n, fact) {
    return n == 0 ? 1 : n * fact(n - 1, fact);
};

FACT(5, FACT); // => 120
```

これをこの形にしたい。いわゆるカリー化ってやつだ。

```js
var FACT = ???;
FACT(FACT)(5); // => 120
```

`FACT` に `FACT` を渡して返ってきた関数に5を渡す。関数に関数を渡して返ってきた関数に数値を渡す感じ。

```js
var FACT = function(fact) {                        // 関数を受け取る
    return function(n) {                           // 数値を受け取る
        return n == 0 ? 1 : n * fact(fact)(n - 1); // 再帰もカリー化
    };
};

FACT(FACT)(5); // => 120
```

これを展開するとこうなる。

```js
(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 にしよう。

```js
var FACT = function(fact) {
    return function(n) {
        return n == 0 ? 1 : n * fact(fact)(n - 1);
    };
};

(function(fact) {
    return fact(fact);
})(FACT)(5); // => 120
```

展開する。ちょっと複雑になってきた。

```js
(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` にしたい。

改めてコードの一部分を置き換えて整理してみる。

```js
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)` で無限に評価してコールスタックを使い果たしてしまうからだ。

```js
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)` を無限に評価しないように細工する。

```js
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
```

展開する。このあたりまで読んだら、もう一度最初から読み直すといいかもしれない。何を目指してたのかがわからなくなってくるかもしれないから。

```js
(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` に置き換えたかわかるだろうか。

```js
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` を独立させる。このパターンに慣れてきていると嬉しい。

```js
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
```

展開する。ここが一番複雑だ。あと少し。

```js
(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 にも似たようなコードが掲載されているけど、手順を踏んでみないと中々理解できない関数だ。引数名などを整理すると下記のような感じだ。

```js
var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(g) {
        return f(function(x) {
            return g(g)(x);
        });
    });
};
```

Y コンビネーターを利用して階乗を再帰的に実行してみる。

```js
Y(function(factorial) {
    return function(n) {
        return n == 0 ? 1 : n * factorial(n - 1);
    };
})(5); // => 120
```

-----

Y コンビネーターってこういうものなのだ。知的好奇心は満たせただろうか？

# 参考文献

Scheme 手習い