コンピュテーション式の実装にStateを用いる

この記事は、以下の素敵記事にかなり依存しているので、先に下記記事を読んでください。

詳説コンピュテーション式

本記事は上記記事内の whileを実用するためのCombine において、

ちなみに、simple を関数にしなくても済む方法があります。 それを実装した例がBasis.CoreのOptionBuilderなどで見れます。

と記述されている話の部分的な解説です。

問題: Return, ReturnFrom とCombine の組み合わせは、単純な実装では処理が継続される

ここでは、Option用のコンピュテーション式を例にします。

よく見かける実装としては、FSharpx の MaybeBuilderのような定義です *1 。 ここでは、一部抜粋して以下の様な定義とします。

type OptionBuilder() =
  member this.Return(x) = Some x
  member this.ReturnFrom(m) = m
  member this.Bind(m, f) = Option.bind f m
  member this.Zero() = None
  member this.Combine(m, f) = Option.bind f m
  member this.Delay(f) = f
  member this.Run(f) = f ()

let option = OptionBuilder()

では、次の式を評価してみましょう。

option {
  return 0
  return 2
}

評価結果は Some 2 になります。 「おいおい、 return とか言いつつ、次の式が評価されているじゃないか!」と仰るかもしれませんが、Builder の定義で処理を継続しない実装にしていないので仕方がありません *2

どうにかして return 適用以降のコンピュテーション式を破棄したいですよね!

解決案1: Builder が状態を持つ

解決案の一つは、「内部で return が呼ばれたことを記憶しておけば良いよねー」という方法です。

type OptionBuilder internal () =
  let mutable specialRet: obj option = None
  member this.Zero() = None
  member this.Return(x) = Some x
  member this.ReturnFrom(x: _ option) = specialRet <- Some (box x); x
  member this.Bind(x, f) = Option.bind f x
  member this.Combine(x: _ option, rest: unit -> _ option) =
    match specialRet with
    | Some x -> unbox x
    | None -> if x.IsSome then x else rest ()
  member this.Delay(f) = f
  member this.Run(f) = specialRet <- None; f ()

let option () = OptionBuilder()

では、前節とほぼ同様の式を評価してみましょう。

option () {
  return 0
  return 2
}

Some 0 が返ってくるよ、やったね!

解説

return!return の式が評価された場合に、 Builder 内の変数に評価結果を保存しておきます。 その際、他のコンピュテーション式の結果が別の型であっても問題ないように、 box 関数を適用しておきます。

Combine メソッドでは内部変数の状態を確認し、何かしら保存されているなら unbox を適用して返します。保存されていない場合は、第1引数の値次第で処理を分岐します。

option が変数だと、内部に保存している値を共有してしまい、状況によっては unbox を適用した際に InvalidCastException が発生します *3 。これを避けるために、 option を関数として定義し Builder インスタンスを毎回生成しています。

解決案2: 引数で状態を引き回す

returnreturn! を呼び出したかどうかを表す値を、引数で渡したり返すことで、状態を引き回します。 ここでは状態をあらわす型として FlowControl を定義します。 FlowControl は処理を継続しないことを表す Break、継続することを表す Continue からなる判別共用体とします。

// 状態を表す型
type FlowControl = Break | Continue

type OptionBuilder () =
    member this.Zero() = (None, Continue)
    member this.Return(x) = (Some x, Break)
    member this.ReturnFrom(x: _ option) = (x, Break)
    member this.Bind(x, f: _ -> _ option * FlowControl) = (Option.bind (f >> fst) x, Continue)
    member this.Combine((x: _ option, cont), rest: unit -> _ option * FlowControl) =
      match cont with
      | Break -> (x, Break)
      | Continue -> if x.IsSome then (x, Break) else rest ()
    member this.Delay(f: unit -> _ option * FlowControl) = f
    member this.Run(f) = f () |> fst

let option = OptionBuilder()

では、試しに使ってみましょう。

option {
  return 0
  return 2
}

Some 0 が返ってくるよ、やったね!

解説

ここからは、 コンピュテーション式の変換規則 とのにらめっこです。1メソッドずつ見て行きましょう。 なお、今回はカスタムオペレーターについては無視することにします。なので、カスタムオペレーターに関する定義も無視します(が、簡易表記を作るのが面倒なため、定義は仕様からそのまま引っ張ってきます)。

Return, ReturnFrom

Return と ReturnFrom の実装戦略は同じなので、一緒に見ることにします。

T(return e, V, C, q) = C(b.Return(e))
T(return! e, V, C, q) = C(b.ReturnFrom(src(e)))

return eb.Return(e) となることから、"引数の型 = e の型"が望ましいことがわかります。というわけで、引数の型は 'a option です。 Return や ReturnFrom が1度呼び出されてから以降は処理を継続したくないので、引数で渡された値を Some で包んだ値(または引数で渡された値)と Break のペアを返すべきだと判断できます。

Zero

Zero メソッド実装の参考として e の変換を見てみましょう。

T(e, C) = C(e; b.Zero())

この変換を考慮すると、Return と同じ型を返すのが良いと考えられます。今回は処理を継続しても良いと思うので Continue を返すことにしましたが、継続したいかどうかは好みの問題かもしれません。

Bind

まずは let! の変換規則を見てみましょう。

T(let! p = e in ce, V, C, q) =  T(ce, V ⊕ var(p), λv.C(b.Bind(src(e),fun p -> v), q)

e 何らかの評価結果になります。Option の場合は 'a option が妥当でしょう。 pe に何かしら行ったもの、と考えると e に依存した型になりそうです。今回は Option が対象なので、 Option.bind に適用させたい関数と考えると Option から取り出した値の型になります。 ce や Bind が返す値はコンピュテーション式の評価結果になるので、Return と同じ型にすべきだと判断できます。

これらを統合すると、 Bind メソッドの型は 'a option * (`a -> 'b option * FlowControl) -> 'b * FlowContol になります。型が決まったので実装に目を向けることができます。

let!ce という計算を継続しなければならないので、Continue を返すべきことは明白です。 Bind メソッドなので Option,bind を使いたいところですが、第2引数の型が (`a -> 'b * FlowControl) なので、そのままでは適用できません。しかしよく考えると、この関数で返ってくる状態を表す値は、 Bind の操作に何らかの影響を与えるべきではありません(Bind はそのまま評価されるべき)。影響を与えないなら捨てても問題ないので、第2引数の関数と fst (tuple から第1要素を取り出す)を合成して Option.bind に適用すれば良い、という結論が得られます。

Delay, Run

Delay は引数で受け取った関数をそのまま返したいです。ここで、関数が返したい型は計算結果と状態のペアなので、引数の型は 'a option * FlowControl となります。

このままでは一番外側が関数にくるまれたままだったり、その関数の戻り値型が 'a option * FlowControl となっていて不都合が生じるので、Run を実装します。ここで、変換規則を見てみましょう。

let b = builder-expr in b.Run (<@ b.Delay(fun () -> {| cexpr |}C) >@)

Quote を実装しない方針なので、コード引用符は無視できます。Delay では渡された関数をそのまま返したので、 unit -> 'a option * FlowControl が Run に渡されます。また、コンピュテーション式での計算結果として状態を返す必要はないので、結果として、関数を評価して返ってくる tuple の第1要素のみを Run の戻り値とすれば、求めるコンピュテーション式の形になります。

Combine

Combine が必要とされる変換規則の1つとして、

T(ce1; ce2, V, C, q) = C(b.Combine({| ce1 |}0, b.Delay(fun () ->  {| ce2 |}0)))

が、あります。この情報があれば構築できそうですね。やってみましょう。

第1引数は ce1 の型になります。Return などの型から考えると 'a option * FlowControl ですね。第2引数には Delay の評価結果が渡されることから、Delay と同じ型であれば良いことがわかります。

次に Combine の実装ですが、ce1 が 処理継続の状態を持つか否かで ce1 の評価結果を返すか、 第2引数の関数を評価するか決めます。これにより、 returnreturn! が評価されて以降の処理は適用されないようにできます。

Using, For, While, TryWith, TryFinally

前述した記事を読めば、これらのメソッドは簡単に定義できると思うので、ここでは省略します。

解決案1, 2の比較

解決案1の特徴は以下の通りです。

  • Builder 内部に状態を持つため、使うたびに関数呼び出しして Builder のインスタンスを生成する必要がある
  • シグネチャはわかりやすい
  • 思わぬバグに遭遇する確率が解決案2よりも高め

対して、解決案2の特徴は、

  • 内部に状態をもたないので、関数呼び出しにする必要がない
  • シグネチャは直感的でない(ドキュメントかサンプルの提供必須)
  • (解決案1と比べて)パフォーマンスが低下する可能性がある
  • (副作用として)コンピュテーション式をラップした時に、状態を変更できてしまう

どちらを採用するかは、何のために提供するか次第かなと思います。

まとめ

  • まずはどう変換されるか知る
  • 各メソッドの型を考える
  • 状態遷移を利用することで、呼び出されたメソッドに合わせて処理を行う、行わないを切り替えられる

それでは引き続き、素敵なコンピュテーション式ライフをお楽しみください!

*1:他のライブラリでの実装として ExtCoreのMaybeBuilder があります。FSharpPlus の MonadPlusBuilder は本気でモナモナしていて説明が面倒なので、今回は割愛。

*2:Returnメソッド適用以降の式が継続されるのは F# のバグでは、という噂もありますが…真実は現状闇の中

*3:(あるコンピュテーション式が別のコンピュテーション式を呼び出すなど)ネストを多用したコンピュテーション式を評価する関数に非同期にアクセスすると、この問題が高確率で再現します