(自動的に)関数を末尾再帰的に変換する方法を記述した公式の論文を書いた人はいますか?私は限界(変換できる機能の種類)、変換の手続き、可能であれば正当性の証明など、大学レベルの正式な治療を探していますか?ハスケルの例はボーナスになります。関数を末尾再帰を使用するように変換する - 正式な研究
答えて
(自動的に)関数をテール再帰的に変換する方法はありますか?
したがって、この2つの部分がある:
- 所定の再帰関数は非常に、尾再帰形式に変換され、効率的な方法で末尾再帰を実装すること変換
- を作ることができることを認識するで変換は価値があります。
文法的に末尾再帰定義を認識するために比較的単純に表示されます。結局のところ、 'tail recursive'は、呼び出しが式の末尾に構文的に現れることを意味します。
など。 Schemeの人々は説明します
は単にジャンプとして適切な自己呼び出しをコンパイルするフル末尾再帰を達成 にsuficientではありません。代わりに、ソース言語のすべての 部分式の位置を構文的に2つのクラスに分割します:tail (または縮小)の位置とサブ問題の位置。単純な 式(
predicate
の結果の代替)の場合、predicate
は サブ問題位置ですが、結果と代替の両方が の削減位置にあります。この構文的概念は、任意にネストされたサブ式である に容易に拡張することができる。
尾に機能を変換あなたの質問のトリッキーな部分は、末尾再帰ものに候補再帰的な計算を識別し、変換するための最適化である
を呼び出します。
GHCでは、インライン化と単純化ルールの幅広い配列を使用して、再帰呼び出しを崩壊させるための基本的なテール再帰構造が残るまで1つの参照があります。
テールコール撤廃
あなたは末尾再帰の形であなたの機能を持っていたら、effiicently実装その持っているしたいと思います。ループを生成することができれば、それは良いスタートです。あなたのターゲットマシンがない場合には、tail call eliminationは「いくつかのトリックが必要になります。Odersky著とSchinzを引用するには、以下に引用、
の様々な技術が 一般的な(とだけではなく、再帰を排除するために長年にわたって提案されてきましたほとんどのコンパイラC.
をターゲット 用)末尾再帰は、...大きな機能で、プログラム全体を入れて、 機能をシミュレートするためには、直接ジャンプを使用して呼び出すか、この関数内のステートメントを切り替える。
...人気のテクニックは、トランポリンを使用することです。トランポリン内部関数を繰り返し呼び出す外部関数 です。内部関数 が別の関数を末尾に呼び出したいときは、それを直接呼び出すのではなく、単純に がその識別子を(例えばクロージャとして)トランポリンに返します。それによって が呼び出されます。したがって、無制限のスタックの増加は避けられますが、ほとんどの場合、トランポリンによって行われたすべての呼び出しが静的に未知の関数である を呼び出すため、一部のパフォーマンスは必然的に失われます( )。
別の技術は、彼の技術では ヘンリー・ベイカーの「MTAのチェイニー」で、プログラムは最初したがって、末尾再帰にすべてのコールを回し、次に をコンパイルすることができ、 スタイル(CPS)を通過継続に変換する必要がありいつものように。実行時に、スタックがオーバーフローしようとすると、 現在の継続が構築され、コールスタックの一番下にあるトランポリン 「待機中」に返されます(またはlongjmped)。
Tail call elimination on the Java Virtual Machine、ミシェルSchinzマーティン・オーダーズキー、2001
ヘンリー・G.・ベーカー・ジュニアCONSすべきではないCONSその引数、一部II:MTAのドラフト版にチェイニー 、1994年1月。
水星には自動的にテール再帰的なものを作るための2つの最適化が含まれています。 (Mercuryは強制的な純粋な論理プログラミング言語なので、関数ではなく述語について述べていますが、Haskellのものと同じ考えの多くはMercuryプログラムにも当てはまります。
「アキュムレータの導入」は、再帰呼び出しの前に連想操作を移動できるように、特別なアキュムレータパラメータを持つ述語の特殊バージョンを生成します。明らかに、この最適化は必ずしも独自のテール再帰述語をもたらすわけではないが、しばしば第2の最適化によって最適化できる形式になる。
"最後の呼び出しモジュロコンストラクタ"は、本質的に、値が最初に "穴"を含むように再生成されるコンストラクタアプリケーションによってのみ使用され、再帰呼び出しは通常の戻り値渡し規則を使用するのではなく、 "穴"のメモリアドレスに直接出力を返します。しかし、私はHaskellがこのような最適化を怠惰のために無料で行うと信じています。
これらの最適化はいずれも、論文Making Mercury programs tail recursiveに記載されています。
- 1. 再帰関数を末尾再帰に変換する
- 2. は、どのように関数がF#で末尾再帰は
- 3. 末尾再帰を正しく使うには?
- 4. Kotlin:相互再帰関数のための末尾再帰
- 5. curried形式の再帰関数は末尾再帰型にできますか?考える
- 6. 末尾再帰を使用するDoublyLinkedList - InsertItem
- 7. 再発は完全に末尾再帰関数
- 8. F#計算式と末尾再帰の再帰的バインド
- 9. Haskell再帰関数はリストの末尾に追加します
- 10. この例では、再帰を末尾再帰に変換する方法はありますか?
- 11. F#の末尾再帰
- 12. 末尾再帰POWアーラン
- 13. 末尾再帰レーベンシュタイン距離
- 14. の最適化非末尾再帰関数
- 15. エリクシール末尾呼び出し再帰関数
- 16. 畳み込み関数を末尾の再帰形式で記述することはできますか?
- 17. 再帰関数の変換
- 18. Raspbian - 多くの研究の末、PHPコード
- 19. Selenium(Edge)長い研究の末、
- 20. 2つのリストを末尾再帰的にマージするには?
- 21. フレーズクエリーを使って研究する
- 22. 再帰関数によって使用されるグローバル変数
- 23. Pythonこの関数を再帰関数に変換します
- 24. どのように再帰関数でカウントを保持する必要がありますか。末尾再帰や追加パラメータなし
- 25. C#の文字列再帰関数を使用するよう
- 26. 再帰的JS関数をObj-Cに変換する
- 27. 再帰的ツリーウォーキング関数を反復的に変換する
- 28. F#の末尾再帰呼び出し
- 29. switch文の末尾が再帰的か?
- 30. 再帰から尾の再帰への変換
私はグーグルをしましたが、具体的な参照は見つかりませんでした。誰かがリファレンスを提供することを期待していました。 – Ralph
CPS変換は、最も一般的なケースでは確かにその仕事を行うでしょう(そして結果的にいくつかの最適化は、結果として生じる裂け目のほとんどを取り除くかもしれません)。多数の論文がこのトピックに掲載されています。 –