継続を使ってOptionコンピュテーション式を実装する
前提
下記記事を読んでいることが前提となります。
コンピュテーション式の実装にStateを用いる - pocketberserkerの爆走
注意事項
- 継続に関する解説はしません
- この記事のコードが理解できなくてもコンピュテーション式は使うことができます
継続、しませんか
そもそもこの話は、コンピュテーション式のキーワードによって計算を継続するかどうか切り替えたい、というのが元々のお話でした。そして継続というと、この界隈にいれば一度は単語を聞いたことがあるだろう、継続モナドが真っ先に思いつくのが自然ですよね。
というわけで、件の OptionBuilder を、継続の概念を用いて実装してみましょう。
定義
先に実装を掲載しておきます。なお、 TryWith, TryFinally, While, For は既存と変更はないため、省略します。
type Cps<'T, 'R> = | Cps of (('T -> 'R) -> 'R) type OptionBuilder internal () = member this.Zero() = Cps (fun k -> k None) member this.Return(x) = Cps (fun _ -> Some x) member this.ReturnFrom(x: _ option) = Cps (fun _ -> x) member this.Bind(x: _ option, f: _ -> Cps<_ option, _>) = match x with | Some x -> f x | None -> this.Zero() member this.Using(x: #IDisposable, f: #IDisposable -> Cps<_ option, _>) = try f x finally match box x with null -> () | notNull -> x.Dispose() member this.Combine(x, rest) = Cps (fun k -> match x with | Cps f -> f (fun value -> match rest () with | Cps g -> g k)) member this.Delay(f) = f member this.Run(f) = match f () with | Cps x -> x id
Cps 型
わかりやすく（？）するために導入しています。
Zero
引数として受け取った関数に計算結果を適用するラムダ式を返します。
Return, ReturnFrom
引数の関数は使わずそのまま値を返します。こうすることで、後続の計算をすべて破棄しています。
Bind
渡された option が Some であれば Cps に束縛します。None の場合は Zero メソッドに依存します。今回は継続する形にしました。
Using
型が異なること以外は Bind と大した差はありません。
Combine
x, rest, 渡された引数の順に計算を行うラムダ式を Cps でくるんで返します。
return などでは、引数として渡される関数は破棄しているので、後続の処理がひたすら破棄されるのがわかると思います。
Run
最終的に Option コンピュテーション式は Option を返したいので、 型を取り外して返します。
このコンピュテーション式は今まで通りの式をかけるのか？
少なくとも Basis.Core.OptionBuilder 用のテストは、テスト側は一切修正せずとも全件パスしたので、その範囲においては動作すると思われます。
継続渡しスタイルで
ここまでくると型いらないだろう、ということで。
type OptionBuilder internal () = member this.Zero() = fun k -> k None member this.Return(x) = fun _ -> Some x member this.ReturnFrom(x: _ option) = fun _ -> x member this.Bind(x, f) = x |> Option.map f |> getOrElse this.Zero member this.Using(x: #IDisposable, f) = try f x finally match box x with null -> () | notNull -> x.Dispose() member this.Combine(f, rest) = fun k -> f (fun _ -> rest () k) member this.Delay(f) = f member this.Run(f) = f () id
見た目はシンプルですが、シグネチャがすごいことになっています。が、定義する側としてはこちらのほうが楽ですね。
終わりに
というわけで、継続渡しスタイルはこういうところで使えるよ、という例でした。
Listコンピュテーション式にyield breakもどきを作れないかあがいてみた
コンピュテーション式におけるreturnとyieldにも書かれている通り、カスタムオペレーターで yield break を実装することはできません。では、型の力をつかってどうにかできないか、とあがいてみました。
Builder の定義
前述の記事で掲載されている ListBuilder の定義を少し変更します。なお、下記コードでは変更のない部分を省略しています。
module Control = type YieldControl<'a> = Break | Return of 'a open System open Control // オープンする順序で Break の優先順位を決める open Basis.Core.ComputationExpr type ListBuilder internal () = ... member this.YieldFrom(x) = match x with | YieldControl.Break -> (this.Zero() |> fst, Break) | YieldControl.Return x -> this.Return(x) ...
すると、
open Control list { for x in [1; 2; 3; 4; 0; 5; 6] do if x = 0 then yield! Return -1 yield x return 10 } // equal [1; 2; 3; 4; -1] list { for x in [1; 2; 3; 4; 0; 5; 6] do if x = 0 then yield! Break yield x return 10 } // equal [1; 2; 3; 4]
と、ちょっと残念な形で yield break (ついでに yield return)もどきを記述できます。
Yield メソッドを使えない理由
既存の Yield は 'a -> 'a list * FlowControl です。仮に YieldControl<_> -> 'a list * FlowControl を定義したとしても、呼び出し側でどちらを呼べばいいかの型注釈をつける必要がでてきます。
YieldFrom は list を受け取るメソッドしか存在しないため、どのメソッドを呼び出せばよいか判別できます。なので型注釈も必要ありません。
結論
定義が複雑になるくらいなら、素直に return! [] を使ったほうがよさそうですね。
コンピュテーション式のSourceメソッドを試す
前提
以下のエントリを読んでいることが推奨されます。
注意
src(e)は、ビルダーがSourceメソッドを持っており、 かつ最も内側のForEachがユーザによるもの(変換により生成されたコードではなく、ユーザが書いたコードであるということ)である場合のみ、b.Source(e)に変換されます。2番目の条件は仕様書からのものですが、どうも実際の実装はちょっと違っているようです。コードを軽く眺めただけですが、ForEachとForEachThenJoinOrGroupJoinOrZipClauseのForEach部分とLetOrUseBangの場合に、ユーザコードかどうかの判定をしているようで、そのほかの部分ではビルダーにSourceメソッドがあればそれを呼び出しているようです。 そのため、
return! eはビルダーにSourceメソッドが存在すればb.ReturnFrom(b.Source(e))に、存在しなければb.ReturnFrom(e)に変換されます。
このことから、将来のF# のバージョンによっては、仕様書通りの挙動になって今回のサンプルコードが動かなくなる可能性が十分に有り得ます。
Source メソッドで何ができそうかを考える
src が出現する変換規則は以下の通りです。
T(let! p = e in ce, V, C, q) = T(ce, V Å var(p), lv.C(b.Bind(src(e),fun p -> v), q)
T(yield! e, V, C, q) = C(b.YieldFrom(src(e)))
T(return! e, V, C, q) = C(b.ReturnFrom(src(e)))
T(use! p = e in ce, V, C, q) = C(b.Bind(src(e), fun p -> b.Using(p, fun p -> {| ce |}0))
T(for p1 in e1 do joinOp p2 in e2 onWord (e3 eop e4) ce, V, C, q) =
Assert(q); T(for pat(V) in b.Join(src(e1), src(e2), lp1.e3, lp2.e4,
lp1. lp2.(p1,p2)) do ce, V , C, q)
T(for p1 in e1 do groupJoinOp p2 in e2 onWord (e3 eop e4) into p3 ce, V, C, q) =
Assert(q); T(for pat(V) in b.GroupJoin(src(e1),
src(e2), lp1.e3, lp2.e4, lp1. lp3.(p1,p3)) do ce, V , C, q)
T(for x in e do ce, V, C, q) = T(ce, V Å {x}, lv.C(b.For(src(e), fun x -> v)), q)
T(do! e;, V, C, q) = T(let! () = src(e) in b.Return(), V, C, q)
ぱっと思いつくのは、
- 互換のある型が渡された場合に変換を行う
- (Stateを用いた実装にしている場合)特定の型のみ、後続の計算を継続する/破棄する
です。後者は特にやる理由がないので、ここでは前者について見て行きましょう。
例：Souce メソッドを利用して型を変更する
コンピュテーション式に Source メソッドを実装して、互換のある型から値を取り出してみましょう。
例として、Basis.Core の OptionBuilder に Result 型を渡せるようにします。
open Basis.Core module Hoge = type Option.OptionBuilder with member this.Source(x) = Result.toOption x member this.Source(x: _ option) = x let res = option { return! Success 10 } // Some 10
この例の場合、 Result 型の場合は Option に変換され、それ以外の型はそのまま ReturnFrom 渡されます。Result 用の関数は定義したけど Opation のコンピュテーション式内でも同じものが使いたくなった、という場合に利用できそうです。
まとめ
- 溢れ出る QueryBuilder 用メソッド臭…
- 拡張メソッドとオーバーロードのご利用は計画的に。無理のない型ライフを。
- 型変換が多量に発生することが予測できる時に利用することをおすすめします
コンピュテーション式の Quote メソッドで変換結果を見る
前提
以下のエントリを読んでいることが前提となります。
また、F# のコードクォートに関する知識を持っていると、理解しやすいと思います。
今回のお話
QuoteメソッドはExprを取るRunとセットで拡張すればいいって話をお昼に @pocketberserker に教えてもらった。なるほどねー。
— ふ''れいす (@bleis) 2014, 1月 30これに関することをメモ書きしておきたかった。
Quote メソッド
Run, Delay, Quote メソッドが定義されていると、コンピュテーション式は以下のように変換されます。
let b = builder-expr in b.Run (<@ b.Delay(fun () -> {| cexpr |}C) >@)
Quote メソッドはコードクォートに変換されることがわかります。
この Quote を使って何か面白いことができないか…と考えるのですが、既存のコンピュテーション式の多くは既にコードクォートを受け取らない Run を実装しています。単に Quote だけを拡張メソッドとして定義するだけでは、コンピュテーション式を利用した既存コードがコンパイルエラーになってしまいます。
まずはこの問題を解決しましょう。
拡張メソッドで呼び出すメソッドを制御する
コンピュテーション式はクラスなので、拡張メソッドやオーバーロードが利用できます。この2つを使うことで、コードクォートを引数にとらない Run が既に実装されていても、コンパイルエラーを回避できます。
例として、コンピュテーション式の実装にStateを用いる で定義した OptionBuilder を使います。定義を再掲します。
module Program 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()
では、拡張してみましょう。
module Ext = type OptionBuilder with member this.Quote() = () // コードクォートを受け取ってそのまま返す member this.Run(f: Quotations.Expr<unit -> 'a option>) = f // Expr let test<'a> = option { return 0 return 1 }
test を printfn "%A" に渡すと、以下の値が表示されると思います。
Call (Some (Value (Program+OptionBuilder)), Delay,
[Lambda (unitVar,
Call (Some (Value (Program+OptionBuilder)), Combine,
[Call (Some (Value (Program+OptionBuilder)), Return,
[Value (0)]),
Call (Some (Value (Program+OptionBuilder)), Delay,
[Lambda (unitVar,
Call (Some (Value (Program+OptionBuilder)),
Return, [Value (1)]))])]))])
この結果を大雑把に説明すると、
- ラムダ式を引数に Delay が呼び出される
- ラムダ式の引数は
unitで、ラムダ式内では Combine が呼ばれる - Combine の第1引数は Return に 0 を渡した結果、第2引数は 式を Delay でくるんだものが入る
のような感じです。コンピュテーション式の変換結果がそれとなくわかりますね。定義したコンピュテーション式が意図した通りに展開されているかを簡易的に眺めたいときに便利かもしれません。
ちなみに、この方法は拡張メソッドとオーバーロードを利用するだけなので、標準ライブラリのコンピュテーション式も制御できます。
type AsyncBuilder with member this.Quote() = () member this.Run(f: Quotations.Expr<_>) = f // 型はExpr<unit> let asyncTest = async { return! Async.Sleep 1000 }
Quote メソッドの実装に関して
Quote メソッドが存在する場合は、 Delay を引用符で囲んだ形で出力されます。このことを考えると、最小の実装は以下の通りです。
type OptionBuilder with member this.Quote() = ()
引数を渡すパターンだと
type OptionBuilder with member this.Quote(q: Quotations.Expr<_>) = q
となることが多いでしょう。
コードクォートを使ってコンピュテーション式を制御する
Quotations.Expr を引数として受け取り、Expr の評価結果を返すような eval 関数を実装し、 Run の引数の Expr を eval に適用すると、通常のコンピュテーション式の計算結果と同様の結果を得られます。
この eval の中で、特定のメソッドが Call されていたら以降の計算を破棄する、という実装を行えば、この記事で取り上げたような State を併用せずとも、フローを変更できるでしょう *1 。Quotations.Patterns, Quotations.DerivedPatterns, Quotations.ExprShape で定義されている各種アクティブパターンを使えば、式木を解析することができます。
式木を実際に評価する方法については、残念ながら私にはリフレクションを使うことしか思いつきませんでした。でもそうなると、パフォーマンス劣化を招く恐れがあるので、この方法を使うかどうかはケースバイケースですね。
最後に
eval をどう実装するかについては、Quotations の話になってくるので省略します。興味のある方は色々と試してみてください。
*1:つまりこの方法が、Return 以降の処理を破棄する解決案3ということになります
コンピュテーション式の実装に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 を適用して返します。保存されていない場合は、第１引数の値次第で処理を分岐します。
option が変数だと、内部に保存している値を共有してしまい、状況によっては unbox を適用した際に InvalidCastException が発生します *3 。これを避けるために、 option を関数として定義し Builder インスタンスを毎回生成しています。
解決案2: 引数で状態を引き回す
return や return! を呼び出したかどうかを表す値を、引数で渡したり返すことで、状態を引き回します。
ここでは状態をあらわす型として 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 e が b.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 が妥当でしょう。
p は e に何かしら行ったもの、と考えると 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引数の関数を評価するか決めます。これにより、 return や return! が評価されて以降の処理は適用されないようにできます。
Using, For, While, TryWith, TryFinally
前述した記事を読めば、これらのメソッドは簡単に定義できると思うので、ここでは省略します。
解決案1, 2の比較
解決案1の特徴は以下の通りです。
対して、解決案2の特徴は、
- 内部に状態をもたないので、関数呼び出しにする必要がない
- シグネチャは直感的でない（ドキュメントかサンプルの提供必須）
- （解決案1と比べて）パフォーマンスが低下する可能性がある
- （副作用として）コンピュテーション式をラップした時に、状態を変更できてしまう
どちらを採用するかは、何のために提供するか次第かなと思います。
まとめ
- まずはどう変換されるか知る
- 各メソッドの型を考える
- 状態遷移を利用することで、呼び出されたメソッドに合わせて処理を行う、行わないを切り替えられる
それでは引き続き、素敵なコンピュテーション式ライフをお楽しみください！
*1:他のライブラリでの実装として ExtCoreのMaybeBuilder があります。FSharpPlus の MonadPlusBuilder は本気でモナモナしていて説明が面倒なので、今回は割愛。
*2:Returnメソッド適用以降の式が継続されるのは F# のバグでは、という噂もありますが…真実は現状闇の中
*3:（あるコンピュテーション式が別のコンピュテーション式を呼び出すなど）ネストを多用したコンピュテーション式を評価する関数に非同期にアクセスすると、この問題が高確率で再現します
FSharp.Core.Printf モジュールについてのメモ
メモ。そのうち記事に昇格するかも。
間違っているかもしれないので、質問疑問指摘その他お待ちしております!
printf, printfn
System.Console.Out に書き込む。n がつく場合は書き込み後に改行。
fprintf, fprintfn
引数で渡された System.IO.TextWriter に書き込む。たとえば StreamWriter とか？
eprintf, eprintfn
System.Console.Error に書き込む。
sprintf
文字列返すやつ
bprintf
渡された StringBuilder に書き込む。
failwithf
最後に failwith に渡して例外を投げる。
kが頭文字につく関数とつかない関数
kbprintf と bprintf ってどういう違いがあるのという話。
PrintfEnv.Finalize 実行時に渡された関数を適用する。
k が付かない場合は、だいたいの関数が k*printf に ignore 関数を渡している。
StringFormat
書式を作る的な何か。
let fmt = Printf.StringFormat<string -> int -> string>("こんにちは、%sさん!今年は%d年です。") sprintf fmt "hoge" 2013 // => "こんにちは、hogeさん!今年は2014年です。"
設定ファイルから読み込んでsprintfに渡すとかできるようになります。
ちなみに、指定した型が間違っていたら実行時に例外を投げます。
BuilderFormat
StringBuilder に渡すための書式なので、返す型は unit。
let builder = StringBuilder() let fmt = BuilderFormat<string -> unit>("hogeさん、%s!") bprintf builder fmt "こんにちは" builder.ToString() // => "hogeさん、こんにちは!" |> ...
TextWriterFormat
TextWriter に渡すための書式なので、返す型は unit。
let fmt = TextWriterFormat<int list -> unit>("とりあえず中身を見る: %A") printfn fmt [1;2;3]
%A を含む文字列をFormatに渡したい
前述で書いている通り、渡したいものの型を書いておけばだいたい動くと思われます。
残り
あとでかく
