問題タブ [tail-recursion]

GHC はデフォルトで次の関数の末尾呼び出しの最適化を実行しますか? 唯一の奇妙な点は、再帰的に IO アクションを定義していることですが、これを TCO できない理由がわかりません。

私は次の関数を書きました：

F# コンパイラがループに変換したかどうかを知るにはどうすればよいですか? Reflector を使用せずに調べる方法はありますか (Reflector の経験がなく、C# も知りません)。

編集:また、内部関数を使用せずに末尾再帰関数を作成することは可能ですか?それともループが存在する必要がありますか?

また、F# std lib には、特定の関数を何度も実行する関数があり、そのたびに最後の出力が入力として与えられますか? 文字列があるとしましょう。文字列に対して関数を実行し、結果の文字列に対して再度実行します...

関数型言語は、多くの問題を解決するために再帰を使用することにつながるため、それらの多くは末尾呼び出し最適化（TCO）を実行します。TCOは、その関数の最後のステップとして、別の関数（またはそれ自体。この場合、この機能はTCOのサブセットである末尾再帰除去とも呼ばれます）から関数を呼び出し、新しいスタックフレームを必要としません。これにより、オーバーヘッドとメモリ使用量が減少します。

Rubyは明らかに関数型言語（ラムダ、マップなどの関数など）から多くの概念を「借用」しており、興味をそそられます。Rubyは末尾呼び出しの最適化を実行しますか？

末尾呼び出しの最適化を実装する言語での再帰の深さに対する理論的/実際的な制限は何ですか？（繰り返し関数が適切に末尾呼び出しされていると想定してください）。

私の推測では、再帰的な手順であるにもかかわらず、再帰的なプロセスがないため、理論上の制限はNONEです。実際の制限は、使用可能なメインメモリによって許可される制限です。私がどこか間違っている場合は、明確にするか修正してください。

どうやら、Python にテール コールの最適化が必要かどうかについて大騒ぎになっているようです。これは、誰かが Guido に SICP のコピーを送ったときに頭に浮かびました。私はグイドと同じ船に乗っています。テールコール最適化の概念を理解しています。Python が本当にそれを必要とする理由が思いつきません。

これを理解しやすくするために、TCO を使用して大幅に簡素化できるコードのスニペットを教えてもらえますか?

f# の morris seq 用に書いたこの「学習コード」がありますが、回避方法がわからないスタック オーバーフローに悩まされています。"morris" は、無限の "see and say" シーケンス (つまり、{{1}、{1,1}、{2,1}、{1,2,1,1}、{1,1,1) を返します。 ,2,2,1}, {3,1,2,2,1,1},...})。

Seq.nth を使用して n 番目の反復を選択できますが、スタック オーバーフローに達する前にしか取得できません。私が持っている再帰の 1 つのビットは末尾再帰であり、本質的にリンクされた一連の列挙子を構築します。問題はそこじゃない。4000番目のシーケンスで「enum」が呼び出されたときです。F# 1.9.6.16 では、以前のバージョンは 14000 を超えていたことに注意してください)。これは、リンクされたシーケンスが解決される方法によるものです。シーケンスは遅延しているため、「再帰」も遅延しています。つまり、seq n は seq n-1 を呼び出し、seq n-2 を呼び出し、以下同様に最初の項目を取得します (最初の # が最悪のケースです)。

が問題を悪化させていることを理解しており[|0|] |> Seq.append str |> Seq.windowed 2、それを排除すれば、生成できる # を 3 倍にすることができます。実際には、コードは十分に機能します。morris の 3125 回目の反復は、長さが 10^359 文字を超えます。

私が実際に解決しようとしている問題は、遅延評価を保持し、選択できる反復のスタック サイズに基づいて制限をなくす方法です。メモリ サイズに基づいて制限を行うための適切な F# イディオムを探しています。

2010年10月更新

F# をもう少しよく学び、Haskell を少し学び、この問題を 1 年以上考え、調査した結果、ようやく自分の質問に答えることができました。しかし、難しい問題はいつもそうですが、問題は間違った質問から始まります。問題はシーケンスのシーケンスではありません。実際には、再帰的に定義されたシーケンスが原因です。私の関数型プログラミングのスキルは少し良くなったので、以下のバージョンで何が起こっているのかを簡単に確認できます。

これは基本的に、シーケンスを生成するための Seq 処理関数呼び出しの非常に長いチェーンを作成します。F# に付属している Seq モジュールは、スタックを使用しないとチェーンをたどることができないものです。追加および再帰的に定義されたシーケンスに使用する最適化がありますが、その最適化は、再帰が追加を実装している場合にのみ機能します。

だからこれはうまくいく

そして、これはスタックオーバーフローを取得します。

F# ライブラリが問題であることを証明するために、継続を使用して追加、ペアワイズ、スキャン、および収集を実装する独自の Seq モジュールを作成しました。これで、問題なく 50,000 seq の生成と出力を開始できます (処理が終了したため、終了することはありません)。 10^5697 桁の長さ)。

いくつかの追加メモ:

• 継続は私が探していたイディオムでしたが、この場合は、私のコードではなく、F# ライブラリに入る必要がありました。F# の継続については、Tomas Petricek の Real-World Functional Programmingの本から学びました。
• 私が受け入れた怠惰なリストの回答は、別のイディオムを保持していました。遅延評価。書き直したライブラリでは、遅延型を利用してスタックオーバーフローを回避する必要もありました。
• 怠惰なリストバージョンは運によって機能します（おそらく設計によるものですが、それは私の現在の判断能力を超えています）-構築および反復中に使用されるアクティブパターンマッチングにより、必要な再帰が深くなりすぎる前にリストが値を計算するため、怠惰ですが、スタックオーバーフローを避けるために継続が必要なほど怠惰ではありません。たとえば、2 番目のシーケンスが 1 番目のシーケンスの数字を必要とするときには、すでに計算されています。つまり、LL バージョンは厳密にはシーケンス生成の JIT 遅延ではなく、リスト管理のみです。

私は次のように再帰的にシーケンスを定義するのが好きです。

このような再帰シーケンスを実際に使用する必要があるかどうかはわかりません。は末尾再帰のようにyield! 見えますが、別のIEnumerable内から呼び出されているため、100％確実ではありません。私の見解では、コードは呼び出しごとにIEnumerableのインスタンスを閉じずに作成します。これにより、実際にはこの関数もメモリをリークします。

この関数はメモリをリークしますか？さらに言えば、それは「末尾再帰」でさえありますか？

[編集して追加]：答えを求めてNProfをいじくり回していますが、SOでの再帰シーケンスの実装に関する技術的な説明を得ることが役立つと思います。

私は最近Erlangについて読んでいて、反復ループを使用するのが難しいため、末尾再帰がどのように頻繁に使用されているかを読んでいます。

このように再帰を頻繁に使用すると、速度が低下しませんか？すべての関数呼び出しとそれらがスタックに与える影響はどうでしょうか？または、末尾再帰はこれのほとんどを無効にしますか？

私は言語にかなり慣れていないので、末尾呼び出しが最適化されているかどうか疑問に思っていました。他の言語では、マシンコードまたは中間表現を調べて自分で理解することができましたが、PL/SQL でそれを行う方法がわかりません。

前もって感謝します。