問題タブ [tail-call-optimization]

基本的に、boolを返す仮想update（）関数によって指示されたとおりにトラバースおよび削除される、リンクリストとして格納されたクラスに使用される基本クラスを作成しています。

これが最も効率的なケースであるかどうか疑問に思っています（特に単一のリンクリストである可能性があるという事実が好きです）：

リンクリストはNULLで終了することに注意してください。

次のトラバース関数が呼び出された後、ローカル変数への割り当て操作が慎重に行われないことで、末尾呼び出しを使用してこの関数を確実に使用できるようになると思います。誰かが私が間違ったことを見つけたり、少し複雑でないアプローチを提案したりできますか：p

最後の CLR がテール コールの最適化を行うことを(偶然に)発見しました。コードでテストしましたが、率直に言って、期待どおりに動作しません。関数の最後のものが関数呼び出しである場合、末尾呼び出しの最適化が発生する可能性があると思いました。

フォーム テール コール op を防ぐために、このコードを「中断」しようとしています。

それでも Foo は最適化されています。どうして？

重複の可能性：
.net / C＃が末尾再帰を排除しないのはなぜですか？

次のC＃コードを使用します。

C＃コンパイラ（とにかく私のもの）は、Counterメソッドを次のCILにコンパイルします。

上記のコードの問題は、スタックオーバーフローが発生することです（私のハードウェアでは約i = 262000）。この問題を回避するために、一部の言語は、末尾呼び出しの除去または末尾呼び出しの最適化（TCO）と呼ばれるものを実行します。基本的に、再帰呼び出しをループに変えます。

私の理解では、.NET 4 JITの64ビット実装はTCOを実行し、上記のCILのようなコードのオーバーフローを回避します。ただし、32ビットJITはそうではありません。モノもそうではないようです。JIT（時間とリソースのプレッシャーにさらされている）がTCOを実行するのに対し、C＃コンパイラーは実行しないのは興味深いことです。私の質問は、C＃コンパイラ自体がTCOに対応していないのはなぜですか？

JITにTCOを実行するように指示するCIL命令があります。たとえば、C＃コンパイラは代わりに次のCILを生成できます。

オリジナルとは異なり、このコードはオーバーフローせず、32ビットJIT（.NETとMonoの両方）でも完全に実行されます。魔法はtail.CIL命令にあります。F＃などのコンパイラは、この命令を含むCILを自動的に生成します。

だから私の質問は、C＃コンパイラがこれを行わないという技術的な理由はありますか？

歴史的には、それだけの価値がなかったのかもしれません。のようなコードCounter()は、慣用的なC＃や.NETフレームワークでは一般的ではありませんでした。C＃のTCOは、不要または時期尚早の最適化と簡単に見なすことができます。

LINQなどの導入により、C＃とC＃の両方の開発者がより機能的な方向に進んでいるようです。したがって、再帰を使用することがそれほど危険なことではなかったとしたら、それは素晴らしいことです。しかし、私の質問は実際にはもっと技術的なものです。

このようなTCOをC＃にとって悪い考え（または危険な考え）にする何かが欠けています。それとも、正しく理解するのが特に難しいものはありますか？それが私が理解したいと思っていることです。何か洞察はありますか？

編集：素晴らしい情報をありがとう。この機能の欠如を批判したり、要求したりしていないことを明確にしたかっただけです。私は優先順位付けに関する合理性にはあまり興味がありません。私の好奇心は、これを困難、危険、または望ましくないものにする障害を認識または理解できない可能性があることです。

おそらく、別のコンテキストが会話に集中するのに役立ちます...

CLRに独自のC＃のような言語を実装しようとしていたとしましょう。なぜ私は（機会費用以外に）「尾」の自動で透明な放出を含めないのでしょうか。必要に応じて指示？C＃に非常によく似た言語でこの機能をサポートする際に、どのような課題に直面したり、どのような制約を導入したりしますか。

返信ありがとうございます（そして事前に）。

Eric Lippertのブログ エントリを読んで、次のスニペットに出会いました。

...永久にループするか (末尾呼び出しを最適化できるアーキテクチャを使用している場合)、スタックが不足してプロセスがクラッシュします。

コンパイラが末尾再帰を最適化できることは承知していますが、末尾呼び出しを最適化できるアーキテクチャとはどういう意味ですか?

ocamldebug のコール スタックは実際のコール スタックであるため、テール コールを行った関数は表示されません。これは紛らわしいです。末尾呼び出しを含むバックトレースを取得するにはどうすればよいですか?

パターンマッチングを使用して、リストのlat要素を決定するコード：

コードをコンパイルしたいのですが、コンパイラーから「怒鳴られ」ます。

@tailrecアノテーションを削除すると、コードがコンパイルされます。テールレックの最適化を行うためにコードを変更するにはどうすればよいですか？

3 つの階乗アルゴリズムをコーディングしました。

1. スタックオーバーフローで失敗すると思います。問題ない。
2. 末尾再帰呼び出しを試し、前のアルゴリズムを再帰から反復に変換します。うまくいきませんが、理由がわかりません。
3. メソッドを使用trampoline()すると、期待どおりに正常に動作します。

私は小さな Lisp インタープリター (Google コードの sapid Lisp) を Python と sapid Lisp 自体に実装しました。おそらく、その主な特徴は、例外による末尾および相互再帰の最適化を実装することです。実装の詳細はこちらhttps://sites.google.com/site/sapidlisp/recursion-optimization .

標準的な手法よりも優れている点は、末尾再帰の最適化を行うために再帰インタープリターに適用する変更が限られていることです。デメリットはタイミングかもしれません。

Python デコレーター ( http://code.activestate.com/recipes/474088/ )で使用されている同様の手法を見つけました。このテクニックをそのコンテキストに入れるために、私は Lisp やその他のインタープリター言語でこのようなテクニックを説明している参考文献を探しています。何か情報はありますか？

Scalaで並列コレクションを試していて、結果が注文されたかどうかを確認したかったのです。そのために、私はREPLに小さな関数を記述して、作成していた非常に大きなリストでそのチェックを実行しました。

stackOverflowで失敗します（ここでの質問にどれほど適切か！）。私はそれがテール最適化されることを期待していました。どうしたの？

私はscalaTCOを調べており、次のコードを記述しています

@tailrecテストに合格し、私の関数は自己再帰的な末尾呼び出しであると信じています。それでも、Javaバイトコードを調べてみると

自己再帰関数のTCOに約束されたgotoが表示されません。これがバイトコードです。