問題タブ [tail-call-optimization]

私は ocaml を学び始めており、この言語の再帰の力を本当に高く評価しています。ただ、一つ気になるのはスタックオーバーフローです。

ocaml が関数呼び出しにスタックを使用すると、最終的にスタックをオーバーフローしませんか? たとえば、次の関数があるとします。

最終的にスタックオーバーフローを引き起こす必要があります。C++ で (再帰を使用して) 同等のことを行うと、オーバーフローすることがわかっています。

私の質問は、関数型言語がスタックをオーバーフローするのを防ぐためのセーフガードが組み込まれているのでしょうか? そうでない場合、上記の合計アルゴリズムは for ループを使用した手続き型スタイルで記述されており、(整数オーバーフローを無視して) 任意の数を処理できるため、このようにあまり有用ではありませんか?

友人がClojureでこのコードスニペットをくれました

そして、同様のScala実装に対してどのようにうまくいくのかと私に尋ねました。

私が書いたScalaコードは次のようになります。

つまり、Clojureのコードは私のマシンで約1.8秒で実行され、5 MB未満のヒープを使用し、Scalaのコードは約12秒で実行され、512 MBのヒープでは不十分です（ 1GBまでヒープ）。

では、なぜこの特定のケースでClojureがこれほど高速でスリムなのか、疑問に思っています。速度とメモリ使用量の点で同様の動作をするScala実装がありますか？

宗教的な発言は控えてください。私の興味は、主にこの場合のclojureの速度を上げる理由と、scalaでのalgoの実装が速いかどうかを調べることにあります。ありがとう。

My answer for a recent question about GOTOs and tail recursion was phrased in terms of a call stack. I'm worried that it wasn't sufficiently general, so I ask you: how is the notion of a tail call (or equivalent) useful in architectures without a call stack?

In continuation passing, all called functions replace the calling function, and are thus tail calls, so "tail call" doesn't seem to be a useful distinction. In messaging and event based architectures, there doesn't seem to be an equivalent, though please correct me if I'm wrong. The latter two architectures are interesting cases as they are associated with OOP, rather than FP. What about other architectures? Were the old Lisp machines based on call-stacks?

Edit: According to "What the heck is: Continuation Passing Style (CPS)" (and Alex below), the equivalent of a tail call under continuation passing is not "called function replaces calling function" but "calling function passes the continuation it was given, rather than creating a new continuation". This type of tail call is useful, unlike what I asserted.

Also, I'm not interested in systems that use call stacks at a lower level, for the higher level doesn't require a call stack. This restriction doesn't apply to Alex's answer because he's writing about the fact that other invocation architectures (is this the right term?) often have a call stack equivalent, not that they have a call stack somewhere under the hood. In the case of continuation passing, the structure is like an arborescence, but with edges in the opposite direction. Call stack equivalents are highly relevant to my interests.

この質問に続いて：how-do-i-check-if-gcc-is-performing-tail-recursion-optimization、-fPICでgccを使用すると、この最適化が破壊されるように見えることに気づきました。共有ライブラリを作成していますが、-fPICオプションは必要ないようです。

さて、私の質問は、なぜ-fPICがgcc最適化を変更するのですか？何らかの理由で-fPICを保持する必要がありますか？

誰かがこの (plt) スキーム コードを Clojure に書き直すことはできますか?

プロシージャ f、g、および h を一緒に折りたたまず、クラッシュすることなくコードを無期限に実行できるようにする方法は?

この大失敗の質問の討論に参加した後、私はコミュニティ全体の前で質問を提起したいと思います.

末尾呼び出しの最適化は、.Net ベースのコードにどのようなシナリオで適用されますか?

信頼できる最新の情報源または再現可能な実験で回答をサポートしてください。

その質問への回答によると 、末尾再帰の最適化を行う C++ コンパイラはありますか? コンパイラは末尾再帰の最適化を行う必要があるようです。

しかし、提案されたオプションを試してみましたが、テンプレート関数の場合、コンパイラはこの最適化を実行できないようです。どうにかして修正できますか？

IL命令を見たいのです.tailが、私が書いてきた末尾呼び出しを使用した単純な再帰関数は、明らかにループに最適化されています。Reflectorでループがどのように見えるか完全にはわからないので、私は実際にこれを推測しています。しかし、私は間違いなく.tailオペコードを見ていません。プロジェクトのプロパティで[末尾呼び出しの生成]をオンにしました。また、Reflectorでデバッグビルドとリリースビルドの両方を試しました。

私が使用したコードは、ChrisSmithによるProgrammingF＃、190ページからのものです。

誰かが実際に生成するいくつかの簡単なF＃コードを提案できます.tailか？

@tailrecコンパイラが末尾再帰関数を最適化するようにするための注釈があると思います。宣言の前に置くだけですか？Scala がスクリプト モードで使用されている場合 (たとえば:load <file>、REPL で使用している場合) にも機能しますか?

Cは末尾呼び出しの除去を実行しないとよく言われます。規格では保証されていませんが、とにかくまともな実装で実際に実行されているのではないでしょうか。成熟した、適切に実装されたコンパイラのみを対象とし、あいまいなプラットフォーム用に作成されたプリミティブコンパイラへの絶対的な最大移植性を気にしないと仮定すると、Cで末尾呼び出しの削除に依存するのは合理的ですか？

また、末尾呼び出しの最適化を標準から除外する理由は何でしたか？