関数を末尾再帰を使用するように変換する - 正式な研究

Question

（自動的に）関数を末尾再帰的に変換する方法を記述した公式の論文を書いた人はいますか？私は限界（変換できる機能の種類）、変換の手続き、可能であれば正当性の証明など、大学レベルの正式な治療を探していますか？ハスケルの例はボーナスになります。

Answer 1

（自動的に）関数をテール再帰的に変換する方法はありますか？

したがって、この2つの部分がある：

• 所定の再帰関数は非常に、尾再帰形式に変換され、効率的な方法で末尾再帰を実装すること変換
• を作ることができることを認識するで変換は価値があります。

末尾再帰に再帰を変換

文法的に末尾再帰定義を認識するために比較的単純に表示されます。結局のところ、 'tail recursive'は、呼び出しが式の末尾に構文的に現れることを意味します。

など。 Schemeの人々は説明します

は単にジャンプとして適切な自己呼び出しをコンパイルするフル末尾再帰を達成 にsuficientではありません。代わりに、ソース言語のすべての 部分式の位置を構文的に2つのクラスに分割します：tail （または縮小）の位置とサブ問題の位置。単純な 式（predicateの結果の代替）の場合、predicateは サブ問題位置ですが、結果と代替の両方が の削減位置にあります。この構文的概念は、任意にネストされたサブ式である に容易に拡張することができる。

• Compiling Higher-Order Languages into Fully Tail-Recursive Portable C

尾に機能を変換あなたの質問のトリッキーな部分は、末尾再帰ものに候補再帰的な計算を識別し、変換するための最適化である

を呼び出します。

GHCでは、インライン化と単純化ルールの幅広い配列を使用して、再帰呼び出しを崩壊させるための基本的なテール再帰構造が残るまで1つの参照があります。

• Secrets of the GHC inliner

テールコール撤廃

あなたは末尾再帰の形であなたの機能を持っていたら、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月。

Answer 2

水星には自動的にテール再帰的なものを作るための2つの最適化が含まれています。 （Mercuryは強制的な純粋な論理プログラミング言語なので、関数ではなく述語について述べていますが、Haskellのものと同じ考えの多くはMercuryプログラムにも当てはまります。

「アキュムレータの導入」は、再帰呼び出しの前に連想操作を移動できるように、特別なアキュムレータパラメータを持つ述語の特殊バージョンを生成します。明らかに、この最適化は必ずしも独自のテール再帰述語をもたらすわけではないが、しばしば第2の最適化によって最適化できる形式になる。

"最後の呼び出しモジュロコンストラクタ"は、本質的に、値が最初に "穴"を含むように再生成されるコンストラクタアプリケーションによってのみ使用され、再帰呼び出しは通常の戻り値渡し規則を使用するのではなく、 "穴"のメモリアドレスに直接出力を返します。しかし、私はHaskellがこのような最適化を怠惰のために無料で行うと信じています。

これらの最適化はいずれも、論文Making Mercury programs tail recursiveに記載されています。