@azu_re さんのツイートで知ったのですが、6to5 に末尾呼び出し最適化が追加されました。
ECMAScript 6 compatibility table によると ES6 transpiler では初めてテストを通った実装のようです。
6to5 ではどのような ECMA−262 5th のコードに変換して実現しているのか気になったので調査してみました。
末尾呼び出し最適化って何？
その前に「末尾呼び出し最適化って何？」って人のために簡単に説明しておきます。
通常、再帰するようなコードを書くとこんな感じになります。
function f(num) {
var acc = arguments[1] || 0:
return num <= 0 ? acc : f(num - 1, acc + num);
}
var result = f(5);
console.log(result);この場合だと 5+4+3+2+1 を計算するコードですね。f の呼び出しに注目すると、f(5) の中で f(4, 5) が呼ばれ、その中でさらに f(3, 9) が呼ばれ…という感じになっています。
この呼び出しをインデントで表すと以下のようになります。
result = f(5);
return f(4, 5);
return f(3, 9);
return f(2, 12);
return f(1, 14);
return f(0, 15);
return 15;このように、再帰するたびにコールスタックが増えていきます。
コールスタックが増えるたびに f のスコープの変数なども保持していなくてはならないため、メモリをどんどん消費していきます。
（なお、ブラウザによりますがコールスタックがあまりに増えすぎると例外を投げて止まります）
それはよくないということで、return するときに function 呼び出している場合は現在のスコープを破棄して、呼び出している function の戻り値をそのまま呼び出し元に返すようにします。
これを末尾呼び出し最適化といいます。
あまり正確ではありませんが、前述の呼び出しに末尾呼び出し最適化を適用すると以下のようになります。
呼び出し自体は変わっていないのですが、呼び出し元がずっと同じイメージです。
result = f(5);
return f(4, 5);
return f(3, 9);
return f(2, 12);
return f(1, 14);
return f(0, 15);
return 15;実際に変換してみる
元となるコードは下記の通り。
function f(num, acc=0) {
return num <= 0 ? acc : f(num - 1, acc + num);
}
var result = f(5);
console.log(result);これを 6to5 で変換したのがこちら。
_tailCall が一行になっていて読みにくいので Google Chrome の開発者ツールで整形しています。
"use strict";
var _tailCall = (function() {
function Tail(func, args, context) {
this.func = func;
this.args = args;
this.context = context;
}
var isRunning = false;
return function(func, args, context) {
var result = new Tail(func, args, context);
if (!isRunning) {
isRunning = true;
do {
result = result.func.apply(result.context, result.args);
} while (result instanceof Tail);
isRunning = false;
}
return result;
};
})();
function f(num) {
var acc = arguments[1] === undefined ? 0 : arguments[1];
if (num <= 0) {
return acc;
} else {
return _tailCall(f, [num - 1, acc + num]);
}
}
var result = f(5);
console.log(result);まず、return num <= 0 ? acc : f(num - 1, acc + num); の条件演算子が最適化され、retrun acc と return _tailCall(f, [num - 1, acc + num]); に分解されています。
ここからが末尾呼び出し最適化のキモで、_tailCall というメソッドが何を行っているのか見ていきます。
_tailCall は func, args, context の3つの引数をとります。func は元の function, args はその引数, context はおそらくレシーバを指しています。
これらは元となる function を function.prototype.apply で実行するのに不可欠だからです。
これらのコンテキストを Tail というオブジェクトにしています。
最初の呼び出しだけ do-while のループに入るようにして、次回以降はそのまま Tail オブジェクトを返すようにしています。
これは何をしているのでしょうか？
このコード例を元に条件文や変数を都度展開して追っていくと以下のようになります。
1. result = f(5);
// f(5, 0)
2. return _tailCall(f, [4, 5]);
3. result = new Tail(f, [4, 5], undefined)
4. result = result.func.apply(undefined, [4, 5])
// f(4, 5);
5. return _tailCall(f, [3, 9]);
6. result = new Tail(f, [3, 9], undefined);
7. return result; // Tail Object
8. result = result.func.apply(undefined, [3, 9]);
// f(3, 9);
9. return _tailCall(f, [2, 12]);
10. result = new Tail(f, [2, 12], undefined);
11. return result; // Tail Object
12. result = result.func.apply(undefined, [2, 12]);
// f(2, 12);
13. retrun _tailCall(f, [1, 14]);
14. result = new Tail(f, [1, 14], undefined);
15. return result; // Tail Object
16. result = result.func.apply(undefined, [1, 14]);
// f(1, 14);
17. retrun _tailCall(f, [0, 15]);
18. result = new Tail(f, [0, 15], undefined);
19. return result; // Tail Object
20. result = result.func.apply(undefined, [0, 15]);
// f(0, 15);
21. return 15; // not Tail Object
22. return 15;これを見るとわかるように、2回目以降の _tailCall 呼び出しはその場で function を呼び出すのではなく、Tail オブジェクトを返すようにすることでコールスタックが深くなっていくのを避けています。
追記（2015/02/10 13:00）
末尾呼び出し最適化の実装が不完全だったため v3.5.2 以降でこの実装は除外されました。
詳しくは別途記事を書いたのでそちらを見てください。
