function add(n,acc) { if(n===0) return acc; return add(n-1,acc+n); }
最初に、関数はパラメーターacc = 0で呼び出されます。 nがゼロに等しくない場合、メソッドは他のパラメーターを使用して自分自身を呼び出し、結果を返します。 コンパイラー（またはインタープリター、または仮想マシン）は、スタック上の現在の関数呼び出しが不要になったことを理解し、それを消去して次の呼び出しに置き換えます。 したがって、再帰によってスタックが大きくなることはありません。 厳密に言えば、現在の関数にアクセスするために末尾呼び出しは必要ありません。他の呼び出しも末尾にすることができます。 主な条件：関数を呼び出してその結果を返すことは、現在の関数の最後のアクションでなければなりません。 たとえば、このような実装では、呼び出しの後に追加が行われるため、末尾再帰メソッドはありません。
function add(n) { if(n===0) return 0; return n+add(n-1); }
いくつかの理由により、末尾再帰はJavaScriptでサポートされていません（このトピックについてはStackOverflowで議論されています）。 したがって、add（100000.0）などの呼び出しは例外で終了します。 Habréでは、setTimeoutを介してこの問題を解決する試みが行われましたが、非常に正直ではなく、あまり美しくありません。 Python言語のよりエレガントなソリューションが、 スプリングボードを使用して提案されました。 JavaScriptの同様のアプローチをここで説明します 。 しかし、私はそれが迅速に動作し、関数が上記の例のように直接書かれることを望んでいました。 何ができるか見てみましょう。
この記事のフレームワークでは、関数がtailメソッドによって自分自身のみを呼び出す場合（他の関数を呼び出すことはできますが、呼び出しは最適化されません）、限られた、しかし一般的なケースを考慮します。 したがって、再度呼び出すのではなく、引数値を新しい値に置き換えて、現在の関数の先頭に移動するだけです。 JavaScriptにはgoto演算子はありませんが、次のようにブロック内の関数をいつでもラップできます。
$tail$label:while(true) { < >; return; }
次に、
continue $tail$label
を使用して関数の先頭に移動します。 関数呼び出しをそのような遷移に置き換える方法は？ 思いついた簡単な方法は、関数を例外をスローする別の関数に置き換えることです。 その後、それをキャッチしてパラメーターを書き換えることができます。 次のようになります。
function add(n,acc) { function add() {throw arguments;} while(true) { try { if(n===0) return acc; return add(n-1,acc+n); } catch($tail$ex) { n = $tail$ex[0]; acc = $tail$ex[1]; } } }
ご覧のとおり、自分ではなく、例外をスローするネストされた関数を呼び出しています。 それを適切に取得し、引数を書き直して、ループの次の反復に進みます（ラベルが役に立たなかった場合でも）。
しかし、私は毎回これを書きたくありません。タスクは簡単に書くことでした。 単純な関数を1つに作り直す方法は？ 関数のソースコードを（toStringを使用して）逆コンパイルし、修正し、次のようにevalを使用してコンパイルし直します。
Function.prototype.tail = function() { var funcStr = Object.toString.apply(this); var paramsPos = funcStr.indexOf('('); var paramsEndPos = funcStr.indexOf(')'); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, ""); var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(","); var body = funcStr.substring(bodyPos+1, bodyEndPos); var paramPassString = ""; for(var i=0; i<args.length; i++) paramPassString += args[i]+"=$tail$ex["+i+"];"; var newBody = "function "+name+"() {throw arguments;} while(true) {try{"+body+ "return;}catch($tail$ex) {"+paramPassString+"}}"; return eval("var $tail$function = function "+name+"("+args.join(",")+") {\n"+ newBody+"};$tail$function"); }
まず、関数のソースコードで、名前、引数、および本文が検索されます。 次に、本体の前とその後に追加の行が生成され、その後、すべてが関数に収集されます。 このアプローチには次の制限があります。
- 関数には名前が必要です。
- 関数はそれ自体を排他的に末尾の方法で呼び出す必要があります。
- それ自体への呼び出しは、try-catchブロック内にあるべきではありません（原則として、これは前のブロックから続きます）。
したがって、add（100000,0）はクラッシュしますが、add.tail（）（100000,0）はすべてを完全にカウントします。
しかし、そのようなソリューションの価格はいくらですか？ 便宜上、関数プロトタイプに補助関数時間を追加します。
Function.prototype.time = function（n）{...}
Function.prototype.time = function(n) { var start = new Date(); var result; var error; for(var i=0; i<n; i++) { try { result = this(); } catch(ex) { error = ex; } } var time = new Date()-start; var funcStr = Object.toString.apply(this); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var body = funcStr.substring(bodyPos+1, bodyEndPos).replace(/^\s*/, "").replace(/\s*$/, ""); if(error) console.log("Code: "+body+"; error: "+error+"; time="+time/n); else console.log("Code: "+body+"; result: "+result+"; time="+time/n); }
関数は引数として開始回数を取り、時間を平均します。 これらのテストを追加します。
var addTail = add.tail(); (function() {return add(10000,0)}).time(500); (function() {return add(100000,0)}).time(500); (function() {return addTail(10000,0)}).time(500); (function() {return addTail(100000,0)}).time(500);
このすべてをGoogle Chrome 25で実行すると、期待外れの結果が表示されます。
Code: return add(10000,0); result: 50005000; time=0.102 Code: return add(100000,0); error: RangeError: Maximum call stack size exceeded; time=0.162 Code: return addTail(10000,0); result: 50005000; time=2.392 Code: return addTail(100000,0); result: 5000050000; time=24.826
繰り返しの回数による制限はなくなりましたが、パフォーマンスが24倍低下しても満足できません。 さらに何ができますか？
明らかに遅いもの（例外と引数）なしで行うには、変更している関数の本体に入り込む必要があります。 もちろん、ここでは、理想的にはJavaScriptパーサー（ jslint.jsに基づく）を作成する必要があります。 しかし、思考を説明するために、正規表現は使用されますが、特定の形式のコードが必要です。
Function.prototype.tail2 = function() { var funcStr = Object.toString.apply(this); var paramsPos = funcStr.indexOf('('); var paramsEndPos = funcStr.indexOf(')'); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, ""); var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(","); var body = funcStr.substring(bodyPos+1, bodyEndPos); body = body.replace(new RegExp("return\\s+"+name+"\\s*\\((.+?)\\);", "g"), function(match,argsStr) { var passArgs = argsStr.split(","); var result = ""; for(var i=0; i<args.length; i++) result+="var $tail$arg"+i+"="+passArgs[i]+";" for(var i=0; i<args.length; i++) result+=args[i]+"="+"$tail$arg"+i+";" return "{"+result+"continue $tail$label;}"; }); var newBody = "$tail$label:while(true) {"+body+"return;}"; return eval("var $tail$function = function "+name+"("+args.join(",")+") {"+newBody+"};$tail$function"); }
ここでは、
return < >(val1, val2, ..., valN)
という形式の文字列の各出現をブロックに変換し、中間変数を介して引数に新しい値を割り当て、continueを呼び出します。 すぐに言いますが、コードは非常に素朴で、追加の角かっこや、たとえば、return式に演算子があると簡単に壊れます。
テスト：
var addTail2 = add.tail2(); (function() {return addTail2(10000,0)}).time(500); (function() {return addTail2(100000,0)}).time(500);
結果は印象的です。
Code: return addTail2(10000,0); result: 50005000; time=0.022 Code: return addTail2(100000,0); result: 5000050000; time=0.222
オリジナルよりもさらに高速です！ もちろん、今は関数呼び出しを保存しています。
他に何をテストしますか？ 上記の記事からフィボナッチ数を見つけるための元の関数を使用します 。
function cpsFib(n, prev, cur, _return) { if (n < 2) { return _return(cur); } return cpsFib(--n, cur, cur + prev, _return); } function identity(x) {return x} var cpsFibTail = cpsFib.tail(); var cpsFibTail2 = cpsFib.tail2(); (function() {return cpsFib(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail2(1300, 0, 1, identity)}).time(5000);
結果：
Code: return cpsFib(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0222 Code: return cpsFibTail(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.3436 Code: return cpsFibTail2(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0036
この記事から実装を取り上げると、次のようになります。
Code: return cpsFib.tco(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.187
例外を除いてバージョンよりも高速ですが、それでも通常の再帰形式よりも8倍遅く、最適化された形式よりも52倍遅いです。
そのようなことが実際のプロジェクトで役立つかどうかはわかりませんが、楽しみのためです。 いずれにせよ、JavaScriptソースコードを再生成する可能性に注意する価値があります。 通常、ウイルスや難読化ツールで使用されますが、このツールは他の目的にも使用できる可能性があります。