問題タブ [tail-call-optimization]

次のコードを実行すると:

次の出力が得られます。

1134903170 再帰バージョンは 5803 ミリ秒かかりました。1134903170 反復バージョンは 0 ミリ秒かかりました。

ここで何か間違ったことをしたような気がします。末尾呼び出し (再帰的なフィボナッチ法の最後の行) がコンパイラによって最適化され、反復バージョンに速度が近づくと考えました。なぜこれが非常に遅く実行されているのか、誰にも考えがありますか? それは単に不十分に書かれた機能ですか？

NB私はOracle JDK 1.7を使用しています

問題のあるコードをこの関数 (ASP.NET のメンバーシップ クラスを使用) に分離しました。

System.OutOfMemoryExceptionの正確な5626繰り返しの後に取得していますh1。しかし、私のシステムのメモリ消費量は20 percent. (私は非常に強力な 16 GB のマシンを持っています。)

上記の関数がスタックをオーバーフローするのはなぜですか? tail 再帰的に書かれていませんか？

よろしくお願いします。

return昨夜、関数からの /redo オプションについて学びました。別の関数を返すことができます。この関数は呼び出し側で呼び出され、同じ位置からエバリュエーターを再度呼び出します。

fooは 1 つの引数しかとらない関数ですが、2 つの引数を取る関数のように動作します。そうでなければ、呼び出し元が関数を返すことを知っている必要があり、その呼び出し元はそのdoエバリュエーターを手動で使用する必要があります。

したがって、なしreturn/redoでは、次のようになります。

foo1 つのパラメーターを消費し、値によって関数を返しました (呼び出されなかったため、インタープリターは先に進みました)。次に、式は 10 に評価されました。return/redo存在しない場合は、次のように記述する必要があります。

これにより、呼び出し元は、実行する関数を返すことを選択したかどうかを知る (または気にする) 必要がなくなります。また、テール コールの最適化や、リターン機能自体のラッパーの作成などを実行できるため、優れています。return以下は、メッセージを出力しますが、関数を終了して結果を提供するバリアントです。

しかし、 で動作するのは関数だけではありませんdo。これが「コールサイトでの DO の必要性をなくす」ための一般的なパターンである場合、なぜこれは何も出力しないのでしょうか?

通常のリターンと同じように、ブロックを値で返しただけです。「テスト」を出力すべきではありませんか？doそれは...ええと、それで何をするかです：

SWI Prologの開発バージョン（Win x64）を使用して、決定論的レクサー（githubでホストされている）のDCG述語を作成しました（したがって、すべての外部述語には選択ポイントがありません）。

現在、多くのことを使用(;)して->、SWI-Prologがread_token(parser(Grammar, Tables), NewState, Token)Tail-Call-Optimizationを使用して再帰を最適化できるのか、または述語を手動でいくつかの句に分割する必要があるのか​​疑問に思いました。インタープリターが何をするのかを知る方法がわかりません。特に、デバッガーの実行時にTCOが無効になっていることを知っています。

続きで遊んでいるだけです。目標は、別の関数をパラメーターとして受け取り、実行量を受け取る関数を作成し、指定された量の時間パラメーターを適用する関数を返すことです。

実装はかなり明白に見えます

しかし、問題はありません。このコードは StackOverflow エラーで失敗します。ここにテールコールの最適化がないのはなぜですか?

Scala プラグインを使用して Eclipse で実行していますが、スレッド「メイン」で例外が返されます java.lang.StackOverflowError at scala.runtime.BoxesRunTime.boxToInteger(Unknown Source) at Task_Mult$$anonfun$1.apply(Task_Mult.scala: 25) at Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)

ps

ほぼ直訳であるF#のコードは問題なく動作しています

末尾再帰以外に末尾呼び出しの最適化はありますか? 私は再帰を含まないものを見つけたり考えたりしようとしましたが、成功しませんでした。出来ますか？例はありますか？

再帰と末尾呼び出しの最適化を使用して、一定の空間と線形時間で循環リンクリストを逆方向に出力できるように思えます。ただし、再帰呼び出しを行った後に現在の要素を印刷しようとすると、問題が発生します。逆アセンブリを調べると、関数が呼び出され、ジャンプされていないことがわかります。逆方向ではなく順方向に出力するように変更すると、関数呼び出しが適切に削除されます。

この関連する質問を見たことがありますが、再帰と TCO を使用して解決することに特に関心があります。

私が使用しているコード:

とコンパイル

更新:循環リストのわずかな変更を加えたジョニの回答を使用して解決しました

私は Scheme インタプリタを書こうとしていますが、TCO の実装が難しいと感じています。TCO が機能するために関数にどのようなプロパティが必要かはわかりません。

1) 定義の最後に自己再帰呼び出しがある関数:

2) 定義の最後にない自己再帰呼び出しを持つ関数:

3) 再帰呼び出しを変数に格納してから返す関数:

4) 相互再帰関数:

5) 関数定義の最後で別の無関係な関数を単純に呼び出す:

6) 私が考えることができる最もトリッキーなケースは閉鎖です。スコープ内の変数への参照を保持するとどうなりますか?

7) 引数として自己再帰呼び出しを使用して、関数定義の最後で別の関数を呼び出す:

私が理解しているように、TCO 実装 (Scheme と Common Lisp の両方) は TCO に適した関数を書き換えるため、TCO に適した関数を静的に検出できなければなりません。

私が知りたいのは：

• これらの関数のうち、TCO によって書き直されるのはどれですか? また、なぜそれらだけを書き直すのでしょうか?
• TCO の書き換えが発生する状況 (例: 7) ではありますが、関数は引き続きメモリを線形に消費しますか?

いくつかのライブラリは、テンプレートから制御フロー構造を生成します。たとえば、「安全なswitch」パターンやビジター パターンのテーブル ディスパッチなどです。

そのような構造のスタックメモリ使用量を測定したり、テールコール最適化との相互作用や一般的な実現可能性について何かを公開したりした人はいますか?

テンプレートからループを生成するなど、実行時の再帰戦略を検討しています。末尾呼び出しの最適化に依存できない場合、必然的にスタックがオーバーフローします。