問題タブ [tail-call-optimization]

Scheme の末尾呼び出しの最適化について読んだことがあります。しかし、テールコールの概念を理解しているかどうかはわかりません。次のようなコードがある場合:

これを最適化して、スタックメモリを消費しないようにすることはできますか? または、末尾呼び出しの最適化を次のような関数にのみ適用できます。

特にSunを購入した後は、末尾呼び出しの最適化が一般的な最適化手法として追加されることはないようですが、VMで実行されている言語に、コンパイラがtailcall命令を出力するかどうかを自分で決定させることは技術的に可能ではありません。バイトコード？

例：Java、Groovyは命令を使用しないことを決定できますが、ScalaやClojureなどのより機能的な言語は命令を発行でき、HotSpot VMはtailcall？でマークされたもののみを最適化します。

次のコードを検討してください。

生成されたasmファイルによると、すべてが正常であり、末尾呼び出しが最適化されています。

交換してみてください

と

奇妙なことに、末尾呼び出しの最適化はなくなりました。私が覚えている限り、VS2008にはそのような奇妙なコンパイラの動作はありませんでした。これらのことが起こる理由と、末尾呼び出しの最適化が確実に行われるようにする方法について何か考えはありますか？

; 関数コンパイルフラグ：/ Ogtp

/O2と/Oxの両方の最適化フラグを試しました。重要な他のコンパイラオプションはありますか？

編集：VS2012はなんとか最適化を行うことができます

非常に高い初期 currentReflection 値でこの関数を呼び出すと、関数が末尾再帰ではないことを示すスタック オーバーフロー例外が発生します (正しいですか?)。私の理解では、再帰呼び出しが関数の最終計算である限り、現在のスタック フレームを再利用するには、末尾再帰関数としてコンパイラで最適化する必要があります。なぜこれがここに当てはまらないのか知っている人はいますか？

I've recently learned Haskell, and am trying to carry the pure functional style over to my other code when possible. An important aspect of this is treating all variables as immutable, i.e. constants. In order to do so, many computations that would be implemented using loops in an imperative style have to be performed using recursion, which typically incurs a memory penalty due to the allocation a new stack frame for each function call. In the special case of a tail call (where the return value of a called function is immediately returned to the callee's caller), however, this penalty can be bypassed by a process called tail call optimization (in one method, this can be done by essentially replacing a call with a jmp after setting up the stack properly). Does MATLAB perform TCO by default, or is there a way to tell it to?

Python が末尾呼び出しの最適化をサポートしていないことは知っています。それは、以下で定義した階乗のような反復プロセスを伴う再帰的な手順が O(n) メモリを消費することを意味するのでしょうか、それとも遅延操作がないという事実は、スペースが O(1) になることを意味するのでしょうか?

以下は、おもちゃのプログラミング言語用にプログラムで生成されたスニペットです。実際のコードは異なりますが、以下は実行時の動作を示しています。

私の質問は、GCCがこれを末尾呼び出しの除去と見なすかどうかです。

編集：私の目次の見方は少し欠陥があることがわかりました。そのため、別のケースでは、単一のリターンがテールに配置された別の関数が最適化の対象と見なされますか？私が尋ねる理由は、cコンパイラにはたくさんのスキームがあり、AFAIKスキームはTOCを義務付けているので、これを強制する方法がなければならないということです。

私はC/C ++の不潔な組み合わせで小さなSchemeインタープリターを作成しましたが、適切な末尾呼び出しをまだ実装していません。

私はMTAアルゴリズムの古典的なチェイニーを知っていますが、これを実装する他の素晴らしい方法はありますか？スキームスタックをヒープに置くことができることは知っていますが、標準では無制限の数のアクティブな末尾呼び出しをサポートする必要があるため、それでも適切な除去にはなりません。

私もlongjmpsをいじりましたが、これまでのところ、相互再帰的でない末尾呼び出しに対してのみうまく機能すると思います。

主要なCベースのスキームはどのように適切な末尾再帰を実装しますか？

開示：これは、私が維持しているF＃ランダムテストフレームワークであるFsCheckで発生しました。私には解決策がありますが、私はそれが好きではありません。さらに、私は問題を理解していません-それは単に回避されただけです。

（大きな単語を使用する場合はモナディック）シーケンスのかなり標準的な実装は次のとおりです。

genは、選択した計算ビルダーで置き換えることができます。残念ながら、その実装はスタックスペースを消費するため、リストが十分に長い場合、最終的にスタックがオーバーフローします。問題は、なぜですか。原則として、foldBackは末尾再帰ではないことは知っていますが、F＃チームの巧妙なバニーは、foldBackの実装でそれを回避しました。計算ビルダーの実装に問題はありますか？

実装を以下に変更すると、すべて問題ありません。

完全を期すために、Genタイプと計算ビルダーはFsCheckソースにあります。

この関数を書いていたとき、末尾呼び出しの最適化が得られないことはわかっていました。私はまだこれを処理する良い方法を思いついておらず、他の誰かが提案を提供してくれることを望んでいました.

私は木を持っています：

そして、そこにあるノードの数を数えたい:

これは、子ノードのカウントが追加されているため、最適化されていません。ツリーに 100 万個のノードがある場合、このようなものを作成する方法はありますか?

ありがとう、デレク

これは、CPS を使用した count の実装です。それでもスタックを吹き飛ばしました。

たぶん、スタックを吹き飛ばさずに数えられるように、ツリーを十分な数に分割する方法を思いつくことができるでしょうか?

誰かがツリーを生成するコードについて尋ねました。以下です。