10

関数を (自動的に) 末尾再帰に変換する方法を説明する正式な論文を書いた人はいますか? 制限事項（変換できる関数の種類）、変換手順、可能であれば正当性の証明など、大学レベルの形式的な扱いを探しています。Haskell の例はおまけです。

4

2 に答える 2

7

関数を（自動的に）末尾再帰に変換する方法は？

したがって、これには2つの部分があります。

  • 与えられた再帰関数を末尾再帰形式に変換できることを認識し、その変換を行う
  • 効率的な方法で末尾呼び出しを実装するので、変換はしばらくの間価値があります。

再帰を末尾再帰に変換する

末尾再帰の定義を構文的に認識するのは比較的簡単に見えます。結局のところ、「末尾再帰」は、呼び出しが構文的に式の末尾に表示されることを意味します。

たとえば、Schemeの人々は次のように説明しています。

ジャンプは完全な末尾再帰を実現するのに十分ではないため、適切な末尾呼び出しをコンパイルするだけでは不十分です。代わりに、ソース言語のすべてのサブ式の位置を構文的に2つのクラスに分割します。テール（またはリダクション）位置とサブ問題位置です。単純な式（後件の場合predicate）では、predicateはサブ問題の位置ですが、後件と代替の両方が削減位置にあります。この構文上の概念は、任意にネストされた部分式に簡単に拡張できます。

関数を末尾呼び出しに変換する

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

1つの参照はGHCにあります。これは、基になる末尾再帰構造が残るまで、インライン化とさまざまな単純化ルールを使用して再帰呼び出しを折りたたむものです。

末尾呼び出しの削除

関数を末尾再帰形式にしたら、それを効率的に実装したいと思います。ループを生成できるのであれば、それは良いスタートです。ターゲットマシンがそうでない場合、末尾呼び出しの除去にはいくつかのトリックが必要になります。以下に引用するOderskyとSchinzを引用するには、

主にCを対象とするコンパイラーに対して、一般的な（再帰的だけでなく）末尾呼び出しを排除するために、長年にわたってさまざまな手法が提案されてきました。

...プログラム全体を大きな関数に入れ、この関数内で直接ジャンプまたはswitchステートメントを使用して関数呼び出しをシミュレートします。

...人気のあるテクニックはトランポリンを使用することです。トランポリンは、内部関数を繰り返し呼び出す外部関数です。内部関数が別の関数を末尾呼び出しするたびに、それを直接呼び出すのではなく、単にそのIDをトランポリンに返します（たとえば、クロージャーとして）。トランポリンはそれ自体を呼び出します。したがって、無制限のスタックの増加は回避されますが、トランポリンによって行われるすべての呼び出しが静的に未知の関数への呼び出しであることが主な理由で、パフォーマンスの一部が必然的に失われます。

もう1つの手法は、HenryBakerの「Cheneyonthe MTA」です。彼の手法では、プログラムを最初に継続渡しスタイル（CPS）に変換する必要があるため、すべての呼び出しを末尾呼び出しに変換してから、通常どおりにコンパイルできます。実行時に、スタックがオーバーフローしそうになると、現在の継続が構築され、コールスタックの最下部にあるトランポリン「待機中」に戻されます（またはlongjmpedされます）。

于 2012-05-22T11:57:18.573 に答える
6

Mercury には、末尾再帰を自動的に行うための最適化がいくつか含まれています。( Mercuryは強制純粋論理プログラミング言語であるため、関数ではなく述語について話しますが、Haskell プログラムと同じ考え方の多くが Mercury プログラムに適用されます。関数型ではなく論理型であることよりもはるかに大きな違いは、それが怠惰ではなく厳格）

「アキュムレータの紹介」では、再帰呼び出しの前に連想操作を移動できるようにするために、追加のアキュムレータ パラメータを使用して特殊なバージョンの述語を生成します。どうやら、この最適化は必ずしもそれ自体で末尾再帰述語をもたらすわけではありませんが、多くの場合、2 番目の最適化によって最適化できる形式になります。

「コンストラクターをモジュロとする最終呼び出し」は、基本的に、コンストラクター アプリケーションのみが続く再帰呼び出しを、最初に「ホール」を含む値が構築され、次に再帰呼び出しがその出力を「ホール」のメモリ アドレスに直接返すように書き換えることを可能にします。 " 通常の戻り値を渡す規則を使用するのではなく、. ただし、Haskell は単に怠惰なため、この最適化を無料で取得できると思います。

これらの最適化は両方とも、論文Making Mercury programs tail recursiveで説明されています。

于 2012-05-22T13:11:23.343 に答える