問題タブ [tail-call-optimization]

(Common) Lispで別の関数を呼び出す代わりに別の関数にジャンプすることは可能ですか? つまり、現在の関数が壊れて別の関数が呼び出され、何千もの関数をジャンプバックせずに、末尾でなくても末尾呼び出しの最適化が行われているかどうかを自分で決めるかのように。"(return-from fn x)" が必要かどうかはわかりません。

例：

「ジャンプ」は、スタック オーバーフローが発生しないように、この関数の位置を保存せずに、元の funcall があった場所に戻る代わりに、次の関数を呼び出すようなものでなければなりません。'rest' は、x が nil の場合にのみ実行する必要があります。

私は関数型プログラミングのバックグラウンドを持っており、反復的な問題ではなく、問題に対する再帰的な解決策について最初に考えています。私は Rebol (具体的には R3) を少し使用し始めており、アキュムレータを使用した末尾再帰関数を使用して素因数カタのソリューションを作成しました。しかし、十分に大きな入力があると、スタックを吹き飛ばします。私は、「tail-func.r」と呼ばれる Rebol2 用のスクリプトを持っています。これは、AFAIK が R3 に移植されていないバージョンの末尾呼び出し最適化を実装しています。多くの場合、Rebol 3 は R2 とは異なる方法で実装されていることは知っていますが、追加のコードなしで Rebol 3 で TCO を取得する方法はありますか? そうでない場合、古いスクリプトを移植せずに入手する簡単な方法はありますか?

私のコードを追加するために編集：

この講演では、最初の 8 分間で Runar が、Scala にはテール コールの削除に問題があると説明しています。そうでない場合、なぜですか？

私は自分の質問に答えてもらうために、ウェブ上で掘り下げてみました。Project DaVinciに関連するドキュメントをいくつか見つけました。これは、JVM にクロージャーを含めることに関連する JSR 292 にタグ付けされています。このプロジェクトは実現しましたか? Java 8 の一部ですか?

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

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

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

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

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

私はこれまでのところ JavaScript が好きで、Node.js をエンジンとして使用することに決めました。その理由の 1つは、Node.js が TCO を提供すると主張している . ただし、Node.js でこの (明らかに末尾呼び出し) コードを実行しようとすると、スタック オーバーフローが発生します。

今、私はいくつかの掘り出し物をしました、そして私はこれを見つけました. ここでは、次のように書くべきだと言っているようです。

ただし、これにより構文エラーが発生します。私はそれのさまざまな順列を試しましたが、すべての場合において、Node.js は何かに不満を持っているようです。

本質的に、私は次のことを知りたいです：

1. Node.js は TCO を実行しますか?
2. yieldこの魔法のようなものが Node.js でどのように機能するのでしょうか?

tl;dr;

C# では、それ自体しか呼び出さず、有効な再帰終了条件を持つ遅延反復子関数がスタック オーバーフローを引き起こさないという保証はありますか?

詳細な質問:

原則として、TCO (Tail Call Optimization) 命令が C# コンパイラ (または JIT) によって生成されるという保証は得られないことを私は知っています。

この TCO の認識を考えると、コルーチンとしての性質のために遅延イテレータ関数 ( yield returnetc を使用) があるのではないかと考えています。再入可能性があるため、コルーチンの私の直感は、新しいフレームを作成する代わりに、関数から飛び出して親のフレームから次の関数にジャンプする機能が自然に見えるため、各末尾呼び出しがデフォルトで最適化されるということです。

これは C# での動作ですか、それとも C# イテレータ関数の再帰呼び出しは、親フレームに飛び出して新しいパラメータで再入力するのではなく、現在のフレームから新しいフレームを作成しますか?

例：

私の直感は、上記の例に基づいていますsubPermutations。それは単に山積みの計算であり、それを反復するように呼び出されたように見えます。現在のフレームから、ヒープされた計算を新しいフレームに拡張します-再帰呼び出しが試行される前にそこにあったものに余分なスタックスペースはかかりません...

この直感はまったく根拠のないものかもしれません...

GCC は次の関数で Tail 呼び出しの最適化を実行しますか?

Erlangで最適化された末尾呼び出しではない関数でスタックオーバーフローを取得することは可能ですか? たとえば、このような関数があるとします

十分な大きさのリストが渡された場合、最終的にスタック スペースが不足してクラッシュするように思われます。私はこれを次のようにテストしてみました：

しかし、それは決してクラッシュしません！100,000,000 個の整数のリストで試してみましたが、完了するまでに時間がかかりましたが、クラッシュすることはありませんでした! 質問:

1. これを正しくテストしていますか？
2. もしそうなら、スタックオーバーフローを生成できないのはなぜですか?
3. Erlang は、スタックオーバーフローの発生を防止する何かを行っていますか?