5

一部の VM、特に JVM は、TCO をサポートしないと言われています。その結果、Clojure のような言語は、ユーザーがloop recur代わりに使用する必要があります。

ただし、ループを使用するようにセルフテール呼び出しを書き直すことはできます。たとえば、末尾呼び出しの階乗は次のとおりです。

def factorial(x, accum):
    if x == 1:
        return accum
    else:
        return factorial(x - 1, accum * x)

同等のループを次に示します。

def factorial(x, accum):
    while True:
        if x == 1:
            return accum
        else:
            x = x - 1
            accum = accum * x

これは、コンパイラーによって行うことができます (私はこれを行うマクロを作成しました)。相互再帰の場合、呼び出している関数を単純にインライン化できます。

では、VM をまったく必要とせずに TCO を実装できることを考えると、なぜ言語 (Clojure、Armed Bear Common Lisp など) でこれを行わないのでしょうか? 私は何を逃したのですか？

4

3 に答える 3

11

インライン化は、多くの理由から、一般的なテール コールの削除の問題に対する解決策ではありません。以下のリストは網羅的なものではありません。ただし、それはソートされています-不便で始まり、完全なショーストッパーで終わります.

  1. 末尾の位置で呼び出される関数は大きな関数である可能性があり、その場合、インライン化はパフォーマンスの観点からお勧めできません。

  2. ginへの末尾呼び出しが複数あるとしfます。gインライン化の通常の定義では、各呼び出しサイトでインライン化する必要があり、f巨大になる可能性があります。goto代わりに、先頭にジャンプしてから戻ることを選択した場合g、どこにジャンプするかを覚えておく必要があり、突然、独自のコール スタック フラグメントを維持することになります (これは、「実際の" コール スタック)。

  3. 相互に再帰的な関数fandの場合、 inとingをインライン化する必要があります。インライン化の通常の定義では明らかにこれは不可能です。そのため、効果的にカスタムの関数内呼び出し規則が残っています (上記の 2. へのベースのアプローチのように)。fggfgoto

  4. Real TCE は、高次のコンテキストを含め、末尾の位置で任意の呼び出しを処理します。

    (defn say-foo-then-call [f]
  (println "Foo!")
  (f))

    これは、特定のシナリオで大きな効果を発揮するために使用できますが、明らかにインライン化ではエミュレートできません。

于 2014-04-19T21:33:09.527 に答える
1

  1. コール スタックが表示されないため、驚くべきことであり、デバッグが難しくなる可能性があります。

  2. VM が TCO をサポートする場合に処理される一般的なケースではなく、非常に特殊なケースでのみ機能します。

  3. プログラマーは、言語がそうする動機を与えない限り、コードを末尾再帰的に記述しないことがよくあります。たとえば、再帰階乗は通常、再帰ステップを として記述しますがn * fact(n-1)、これは末尾再帰ではありません。

于 2014-04-19T21:03:50.930 に答える