くまのプーさん：ああ、あなたのしっぽはどうなったの？
Eeyore：彼に何が起こるのでしょうか？
くまのプーさん：彼は違います。
Eeyore：あなたは間違っていなかったのですか？
くまのプーさん：尻尾はそこにあるか、まったくない！ 間違いはありません。
Eeyore：それから何がありますか？
くまのプーさん：何もありません！
私たちのプロジェクトでは、サーバーコンポーネントの1つで、次のリファクタリング後にメモリが流れ始めました。 .NET、F＃、マネージャコード、ガベージコレクション、すべてのもののように見えますが、メモリはどこかでリークしました。 眠れない夜と甘やかされた神経を犠牲にして、漏れの原因が発見されました。 この問題の原因は、F＃チュートリアルからほぼ1対1でコピーされたコードであることが判明しました。
それは予期せぬ場所での不在で判明したように、それはすべて、テール再帰についてでした。
末尾再帰
再帰は、おそらく関数型プログラミングの兵器庫で最も重要なツールの1つです。 そして、再帰呼び出しはスタックを使用するため、ご存じのように無制限ではないため、再帰の使用は制限されており、再帰の深さは有限であるように思われます。
ただし、すべてがそれほど悲観的ではありません。ほとんどすべての関数型言語コンパイラには、末尾再帰最適化などの便利な機能があり、スタックを使用せずに再帰を使用できます。これにより、再帰ネストの制限がなくなります。
末尾再帰は、再帰呼び出しを反復で置き換えることができる場合の特殊な再帰です。 一方では、テールスタイルのロジックを記述することはプログラマの良心のままです。他方では、コンパイラはテール再帰を「検出」し、再帰を反復にスピンする必要があります。
通常、初心者は「機能的」にすぐに目と腕を詰め込み、あらゆる場所で末尾再帰を使用します。 しかし、実際には鉄の「尾」であると思われる関数が、そうではない特殊なケースがいくつかあります。 これらの特別な場合は、非常に不快な結果につながり、多くの時間と神経を殺す可能性があります。
最初のそのようなケースを見て、「トラブル」を回避できるルールを定式化しましょう。
最初に、1からNまでのすべての数を合計する単純な関数を見てみましょう。
let rec sum i = if i <= 0L then 0L else i + sum (i - 1L) > sum 10L;; val it : int64 = 55L
1点を除き、すべて順調です。 少なくとも100,000の金額を計算しようとすると、額にStackOverflowExceptionが発生します。 つまり 計算のための十分なスタックがありませんでした。
> sum 100000L;; Process is terminated due to StackOverflowException.
この問題の答えは、バッテリーを再帰関数の引数として使用することです。
let sumTailRec i = let rec loop acc i = if i <= 0L then acc else loop (acc + i) (i - 1L) loop 0L i
スタックを必要としないように関数を書き換えました。合計に戻る代わりに、引数としてバッテリーを転送します。
計算の順序（引数5）は、次のように説明できます。 末尾再帰なし：
sum: 5 + (4 + (3 + (2 + (1 + (0))))) – , , . .
末尾再帰あり：
sumTailRec: (((0 + 5) + 4) + 3) + 2) + 1) – , , , .
新しい関数は、すでに任意の大きな数を消化できます（int64で十分な場合）。
> sumTailRec 10000000L;; val it : int64 = 50000005000000L
次に、数値を合計するのではなく、現在の数値の特定の関数の結果を合計する、もう少し一般化された関数を作成してみましょう。
let sumFTailRec fi = let rec loop acc i = if i <= 0L then acc else loop (acc + fi) (i - 1L) loop 0L i
新しいバージョンでは、もう1つのパラメーターがあります。関数です。その計算結果を合計する必要があります。 数値自体を要約するオプションは次のとおりです。
> sumFTailRec (fun i -> i) 10000000L val it : int64 = 50000005000000L
そしてここに、正方形を要約します：
> sumFTailRec (fun i -> i*i) 10000000L val it : int64 = 1291990006563070912L
これまでのところ良い。 しかし、わずかなニュアンスがあり、送信される関数は例外をスローする可能性があります。 以下に例を示します。
> let someProblemFun i = i/((i+1L) % 1000L) > sumFTailRec someProblemFun 10000000L System.DivideByZeroException: Attempted to divide by zero. Stopped due to error
問題
値i = 999の場合、ゼロによる除算があります。 例外を除いて、計算をクラッシュさせるのではなく、単に問題要素を無視したいとします。 例外処理が必要になります。 論理的で期待される解決策は、次のことを示唆しています。
let sumFTailRecWithTry fi = let rec loop acc i = if i <= 0L then acc else try loop (acc + fi) (i - 1L) with exc -> printfn "exn raised:%s" exc.Message loop acc (i - 1L) loop 0L i
だから試してください：
> sumFTailRecWithTry someProblemFun 10000L exn raised:Attempted to divide by zero. ... exn raised:Attempted to divide by zero. val it : int64 = 351405L
結果が得られ、例外がキャッチされ、すべてがうまくいくようです。 次に、より深刻な番号を入力してみてください。
> sumFTailRecWithTry someProblemFun 10000000L exn raised:Attempted to divide by zero. ... exn raised:Attempted to divide by zero. Process is terminated due to StackOverflowException.
おっと...問題は何ですか？ 一見、末尾再帰を使用した関数がありますが、なぜスタックが突然終了したのですか？
ご想像のとおり、問題はtry ... with構文にあります。 実際のところ、tryブロックで再帰呼び出しが行われると、テールはテール再帰から再帰し、通常の再帰になります。 なんで？ ループに対する後続の再帰呼び出しのいずれかで、理論的には例外がスローされる可能性があるためです。 処理する必要がある場合は、例外がスローされたときに戻る必要がある場所をスタック上に記憶する必要があります。
解決策
これらの不快な状況はどれですか？ 非常に簡単です。 再帰呼び出しをtry ... with blockでラップする必要はありません。 "external"関数fを呼び出すときにのみ例外が発生するため、この呼び出しをラップするだけです。
let sumFReallyTailRecWithTry fi = let rec loop acc i = if i <= 0L then acc else let fRes = try fi with exc -> //printfn "exn raised:%s" exc.Message 0L loop (acc + fRes) (i - 1L) loop 0L i
私達は試みます：
> sumFReallyTailRecWithTry someProblemFun 10000000L val it : int64 = 374200932236L
出来上がり！ 今回はスタックで十分でしたが、彼は何もしなかったのです。
したがって、ルール：try ... withブロックにテールコールを入れないでください。
2番目のシリーズでは、非同期{...}およびMailboxProcessorの末尾再帰に関する衝撃的な啓示があります。