読者です 読者をやめる 読者になる 読者になる

Async小話(末尾再帰関数)

F#

過去に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 }

を用意したりします。