22

主な質問: 私は、テール コール最適化 (TCO) の最も重要なアプリケーションを、再帰呼び出しをループに変換するものと考えています (再帰呼び出しが特定の形式を持つ場合)。より正確には、これを機械語に翻訳すると、通常はある種の一連のジャンプに翻訳されます。ネイティブ コード (SBCL など) にコンパイルする一部の Common Lisp および Scheme コンパイラは、末尾再帰コードを識別し、この変換を実行できます。Clojure や ABCL などの JVM ベースの Lisp では、これを行うのに問題があります。これを防止または困難にするマシンとしての JVM についてはどうですか? 理解できません。JVM には明らかにループに関する問題はありません。TCO を実行する方法を理解する必要があるのはコンパイラであり、コンパイル先のマシンではありません。

関連する質問: Clojureは一見再帰的なコードをループに変換できます: プログラマーが関数の末尾の呼び出しをキーワード に置き換えると、TCO を実行しているかのように動作しますrecur。しかし、たとえば SBCL や CCL のように、コンパイラにテール コールを識別させることが可能である場合、Clojure コンパイラは、テール コールを処理する方法で処理する必要があることを認識できないのはなぜrecurでしょうか?

(申し訳ありませんが、これは間違いなく FAQ であり、上記の発言は私の無知を示​​していると確信していますが、以前の質問を見つけることができませんでした。)

4

3 に答える 3

9

実際の TCO は、自己呼び出しだけでなく末尾位置の任意の呼び出しに対しても機能するため、次のようなコードはスタック オーバーフローを引き起こしません。

(letfn [(e? [x] (or (zero? x) (o? (dec x))))
        (o? [x] (e? (dec x)))]
  (e? 10))

JVM で実行されているプログラムはコール スタックを操作できないため、これには明らかに JVM サポートが必要です。(独自の呼び出し規則を確立し、関数呼び出しに関連するオーバーヘッドを課すつもりがない限り、Clojure は通常の JVM メソッド呼び出しを使用することを目指しています。)

末尾位置での自己呼び出しの排除に関しては、関数本体全体が単一の JVM メソッドにコンパイルされる限り、解決できる単純な問題です。ただし、これは限定的な約束です。その上、recurその明示性のためにかなり好まれています。

于 2013-10-19T04:29:23.797 に答える