Async小話(末尾再帰関数)
過去にTomas Petricekさんの非同期に関する記事を翻訳しました。
Async in C# and F#: Asynchronous gotchas in C# (Japanese translation)
この記事の最後には以下の記述が存在します。
また、F# の async も問題を持っています(最も一般的な落とし穴は、末尾再帰関数はリークを避けるために do! の代わりに return! を使うべきだということです)。
まずは試してみよう
簡単なサンプルコードで試してみましょう。
open System let rec loop x = async { do! if x < 1 then async { return () } else loop x } loop Int32.MaxValue |> Async.Start
このコードはおそらく OutOfMemoryException
で落ちます。
open System let rec loop x = async { return! if x < 1 then async { return () } else loop x } loop Int32.MaxValue |> Async.Start
こちらはメモリ溢れすくこともなく動作し続けると思います。 fsi で実行している場合は fsi.exe の CPU 使用率を見ればなんとなく雰囲気はつかめるかと。
資料を調べる
残念ながら、The final version of the F# 3.0 language specification(pdf) にはそれらしい記述は見当たりません。
しかし、 The F# Asynchronous Programming Model(pdf) の3ページに以下の記述があります。
aexpr := | do! expr execute async | let! pat = expr in aexpr execute & bind async | let pat = expr in aexpr execute & bind expression | return! expr tailcall to async | return expr return result of async expression | aexpr; aexpr sequential composition | if expr then aexpr else aexpr conditional on expression | match expr with pat -> aexpr match expression | while expr do aexpr asynchronous loop on synchronous guard | for pat in expr do aexpr asynchronous loop on synchronous list | use val = expr in aexpr execute & bind & dispose expression | use! val = expr in aexpr execute & bind & dispose async | try aexpr with pat -> aexpr asynchronous exception handling | try aexpr finally expr asynchronous compensation | expr execute expression for side effects
return!
の説明に末尾呼び出しする説明が書かれています。
つまりどういうこと?
ここからは推測になります。
今回関係ありそうなコンピュテーション式の変換規則は以下の通りです(詳細は Specification を読んでください)。
T(return! e, V, C, q) = C(b.ReturnFrom(src(e))) T(let! p = e in ce, V, C, q) = T(ce, V + var(p), λv.C(b.Bind(src(e),fun p -> v), q) T(do! e;, V, C, q) = T(let! () = src(e) in b.Return(), V, C, q)
直和記号はプラスで代用しています。
do!
系統は let!
の規則に変換され、let!
では Bind
メソッドを呼び出す形になっています。
おそらくこのあたりがスタック溢れにつながっているのではないかと。
つまり、これは別に Async
だけでなく他のコンピュテーション式にも同じことが言えるのでは…?
他のコンピュテーション式でも発生するかどうか
というわけで、いつもあなたの隣に這いよる Option でも試してみましょう。
type OptionBuilder() = member __.Bind(x, f) = Option.bind f x member __.Return(x) = Some x member __.ReturnFrom(x) =x let option = OptionBuilder() let rec doLoopOption x = option { do! if x < 1 then option { return () } else doLoopOption (x - 1) } let rec returnLoopOption x = option { return! if x < 1 then option { return () } else returnLoopOption (x - 1) }
結果は Async
と同様の状況になりました。
まとめ?
ビルダーの実装をかなり工夫しないと(しても?)メモリを食いつくす問題は回避できない可能性があるので、末尾再帰関数でコンピュテーション式を使う場合はおとなしく return!
を使いましょう。
余談
空の Async を作りたい場合ってどうしていますか?(あまりないかもしれないですが)
私は
let zero: Async<unit> = async.Zero() let returnA x = async { return x }
を用意したりします。