問題タブ [tail-call-optimization]

私は再帰と TCO を調べてきました。TCO はコードを冗長にし、パフォーマンスにも影響を与える可能性があるようです。たとえば、7 桁の電話番号を取り、可能なすべての単語の順列を返すコードを実装しました。

短いので、あまり時間を割く必要はありません。ただし、TCO を取得するために末尾呼び出しの再帰でそれを実行しようとすると。かなりの時間を費やす必要があり、コードが非常に冗長になります。スペースを節約するためにコード全体をポーズするつもりはありません。これは git repo link へのリンクです。多くの皆さんが、私よりも優れた簡潔な末尾再帰コードを作成できることは確かです。一般に、TCO はより冗長であると私は今でも信じています (たとえば、階乗およびフィボナッチの末尾呼び出し再帰には、アキュムレータという追加のパラメーターがあります)。しかし、TCO はスタック オーバーフローを防ぐために必要です。TCO と再帰にどのようにアプローチするかを知りたいです。このスレッドでの TCO を使用した Akermann の Scheme 実装は、私の問題点の典型です。

次のブログ記事は、F# でfoldBack継続渡しスタイルを使用して末尾再帰を行う方法を示しています。

Scala では、これは次のことを意味します。

これを行うことで末尾再帰にすることができます：

残念ながら、長いリストではまだスタック オーバーフローが発生します。loop は末尾再帰的で最適化されていますが、スタックの蓄積は継続呼び出しに移動しただけだと思います。

これが F# の問題ではないのはなぜですか? Scalaでこれを回避する方法はありますか?

編集：スタックの深さを示すいくつかのコード：

これは以下を出力します:

Ruby の再帰関数でのスタック オーバーフロー エラーの回避策はありますか?

たとえば、次のブロックがあるとします。

を呼び出すとcountUpTo(1, 10000)、エラーが発生します: stack level too deep (SystemStackError)。

8187 で壊れているようです。Ruby にスタックのサイズを無視するように伝える関数、または最大スタック サイズを増やす方法はありますか?

スタックレスが含まれているPyPy1.7のデフォルトのビルドでは、再帰の深さの制限なしで（まっすぐに）実行する機能は提供されません。

なんで？

スタックレスサポート継続スタイルの関数呼び出しと末尾再帰を備えたPyPyのPreviusビルド。

コルーチンを含むソリューションについては質問していませんが、統合スタッケルの問題を探しています。

列挙子を破棄する必要があるため、末尾呼び出しが最適化されていない私の試みは次のとおりです。

そして、ここに使用例があります：

列挙子の使用を避けることができれば（つまりSeq.head AND Seq.tail）、それを機能させることはできますが、それがなければSeq.tail途方に暮れます。私はこれを一般的なシーケンスで機能させることを本当に望んでいます。

そして参考までに、このコードは現在の状態では機能しないことを知っています。これは、列挙子を複数回破棄することになるためです。

背景：学校のプロジェクト用に.NETコンパイラ（C＃に非常によく似ています）をプログラミングしています。現在追加しようとしている機能の1つは、メソッド内の末尾呼び出しの再帰です。

詳細：CILでは、「this」は単なる別の引数であるかのようにインスタンスメソッドに渡されます。したがって、静的メソッドの最初の引数にアクセスするとldarg.0が発行されますが、インスタンスメソッドの最初の引数にアクセスするとldarg.1が発行され、インスタンスメソッドの「this」にアクセスするとldarg.0が発行されます。 。（インスタンスメソッドは、私が想像していたよりも拡張メソッドにさらに似ています。）

質問：starg.0を使用して、副作用なしに「これ」を設定できますか？

これが問題となる理由：メソッドがインスタンスメソッドであるかどうかは、少しブラックボックスであるMethodBuilderで設定されます。「this」は他の引数とまったく同じように見えますが、一部のJITコンパイラは「this」を個別に追跡し、この値に応じて動作を変更することを知っています。インスタンスメソッドで「this」を設定したときに副作用がある場合、どうすればそれらを回避できますか？

Mono (2.11) での Tail Call Optimization (TCO) 実装の現在の状態は? callee-pops-arguments 規則を使用するには、すべてのコードベースを変更する必要があることをどこかで読んでください。この変更の状況は? この件に関して、ARM/Linux への移植は最新ですか?

ありがとう！

.netにはTailCallオペコードがあるので、これを使用して、F＃関数が本当に末尾再帰であるかどうかを判断できますか？

それが本当なら、誰かがテール機能と非テール機能を識別するVSアドインを作成しましたか？

次のプログラムはスタックを吹き飛ばします:

で失敗する

スタック スペースのオーバーフロー: 現在のサイズは 8388608 バイトです。それを増やすには、「+RTS -Ksize -RTS」を使用します。

ただし、私が理解している限り、可能な再帰呼び出し__find_first_occurrenceは によって評価される最後のもの__find_first_occurrenceであるため、末尾呼び出しの最適化を実行できるはずです。