問題タブ [tail-call-optimization]

does-the-jvm-prevent-tail-call-optimizationsから2 年後、プロトタイプの 実装があるようで、MLVMはこの機能をしばらくの間「proto 80%」と​​してリストしています。

テール コールをサポートすることに Sun/Oracle 側からの積極的な関心はありませんか、それとも、 JVMで言及されているように、テール コールは「[...]すべての機能の優先順位リストで 2 位になる運命にある [...]」だけなのでしょうか。言語サミット？

誰かが MLVM ビルドをテストして、それがどれだけうまく機能するか (もしあったとしても) の印象を共有できれば、私は本当に興味があります。

更新: Avianなどの一部の VMは、問題なく適切な末尾呼び出しをサポートすることに注意してください。

理論的には、大きな入力でもうまく機能するはずの深く再帰的な関数があります。問題は、これを書いている時点で、C# はテール コールの最適化がうまくいかないことを忘れていたことですStackOverflowException。メソッドの基本構造は 2 つの大きなメソッドで構成され、それぞれが他方を呼び出します。

IsSimpleとの両方ProcessExpansionのスタック深度は比較的固定されています。唯一の問題は、Simplify と Expand の間の再帰です。ここでスタックの深さを減らすにはどうすればよいでしょうか?

結果を計算するデリゲートを返すことを考えていましたが、それはやり過ぎのようです - もっと簡単な方法があるはずです。これは私の解決策の考えです（ここでひどく間違ったことをしているに違いないと考え続けているため、あまり洗練されていません）：

だから私の2つの質問は次のとおりです。

1. このソリューションでひどく間違っていると感じるのは何ですか?
2. より良いものを考えられますか？

C＃で末尾呼び出しの最適化が欠落しているために、言語が再帰的なアルゴリズムの実装に適していないという質問がいくつかあります。ただし、これは疑問を投げかけます。例外が発生した場合、またはリフレクションを使用して呼び出しスタックを検査して処理する場合に、末尾呼び出しの最適化を実行し、適切なスタックトレースを提供するにはどうすればよいですか。

重複の可能性：
JVMがまだ末尾呼び出しの最適化をサポートしていないのはなぜですか？

私はオンラインで非常に多くの異なる答えを見るので、私は専門家に尋ねると思いました。

私はStackOverflowExceptionこのJavaメソッドを取得します：

私は末尾呼び出しの再帰で遊んでいるので、JVMがスタックを正しく短絡しないとこれが起こると思いますか？

別の SO question への回答を作成しているときに、Mathematica の末尾再帰に関する奇妙な動作に遭遇しました。

Mathematicaのドキュメントには、末尾呼び出しの最適化が実行される可能性があることが示唆されています。しかし、私自身の実験では相反する結果が得られます。たとえば、次の 2 つの表現を対比してください。最初の例では、おそらくスタックの枯渇が原因で、7.0.1 カーネルがクラッシュします。

2 番目の実行は完了するまで実行され、意味のある結果を返すためにテール コールの最適化を利用しているように見えます。

どちらの式も末尾再帰関数を定義していますf。最初の関数の場合，Mathematica は明らかに複合文の存在を考慮して，テールコールの最適化の可能性を無効にします．$RecursionLimitまた、最初の式は によって、2 番目の式は --によって管理されていることに注意してください。これ$IterationLimitは、 Mathematica が 2 つの式を異なる方法で扱っていることを示しています。（注：上記のSOの回答には、テールコールの最適化をうまく活用するあまり工夫されていない機能があります）。

そこで質問です: Mathematica が再帰関数の末尾呼び出し最適化を実行する状況を知っている人はいますか? Mathematica のドキュメントまたはその他のWRI資料の決定的なステートメントへの参照が理想的です。憶測も大歓迎です。

特定の「因数分解可能な」プロパティを持つ数値を計算する次の Clojure コードがあります。（コードが正確に何をするかは二次的なものです）。

現在、私は TCO に夢中になっており、recurキーワードを使用して明示的に指示された場合にのみ、Clojure が末尾再帰を提供できることに気付きました。だから私はそれを行うためにコードを書き直しました（唯一の違いはrecurでfactor-9を置き換えます）：

私の知る限り、TCO には 2 つのメリットがあります。最初のものは、非末尾再帰呼び出しほどスタックを使用しないため、より大きな再帰でスタックを吹き飛ばさないことです。2つ目は、ループに変換できるため、結果として高速になると思います。

さて、私は非常に大まかなベンチマークを作成しましたが、2 つの実装の間に違いは見られませんでした。私の 2 番目の仮定は間違っていますか、それとも JVM (自動 TCO を持たない) で実行し、recurそれを達成するためのトリックを使用することに関係がありますか?

ありがとうございました。

私は可能な限り C で関数型のプログラムを書こうとしています。GCC/Clang のような優れたコンパイラが末尾呼び出しの最適化を黙って行うことは知っていますが、それは保証されていません。コンパイラで末尾呼び出しの最適化を強制するオプションはありますか? （もちろん、それ自体の最後に呼び出された場合のみ）

メソッドがfinalでない限り、Scalaコンパイラが末尾呼び出しの最適化を適用しないのはなぜですか？

たとえば、これは次のとおりです。

結果は

エラー：@tailrec注釈付きメソッドを最適化できませんでした：プライベートでもファイナルでもないため、オーバーライドできます

このような場合にコンパイラがTCOを適用した場合、正確には何がうまくいかないでしょうか。

Xbox での開発用に、F# 仕様からの 最終的なワークフローの修正バージョンを使用しています。Xbox の .net フレームワークはテール コールをサポートしていないようです。このため、コンパイル時に末尾呼び出しの最適化を無効にする必要があります。

最初は、この制限が計算式でのあらゆる形式のループの使用を防止するように思われるかもしれませんが、私は当初、「ステッピング」によってその問題を回避できると考えていました。 f を呼び出すラムダを含む 最終的に値を返します。

実験の結果、while ループ (計算式で使用してもスタック オーバーフローは発生しません) については正しかったが、再帰関数についてはそうではありませんでした。

明確にするために、これは機能します：

これにより、スタック オーバーフローが発生します。

2 番目のケースでは、スタック トレースは "bind@17-1" への長い一連の呼び出しを示しています。そのコードを以下に示します。スタック トレースに表示される行番号は 17 行目です。

どこが間違っていますか？「ステップ可能な再帰」がスタックオーバーフローに対して無害であるという私の推論は間違っていますか? バインドの実装に何か問題がありますか?

ああ、私の頭！再帰を伴う継続渡しは頭痛の種です...

編集:「スタックオーバーフローに関して無害なステップ可能な再帰」という名前が付けられました。いわゆるトランポリンです。