"コンピュテーションビルダーに機能を後付けする"の補足?
アドベントカレンダーとその補足記事で色々と賑わっていて素晴らしいですね。 と、前置きはここまでにしておいて。
コンピュテーション式の変形後を覗き見るを改良する - ぐるぐる~
さて、この記事に下記の記述があります。
さて、コンピュテーションビルダーに対する機能の追加ですが、方法としては以下のものがあるでしょう。
- コンピュテーションビルダーの書き換え
- 既存のコンピュテーションビルダーを継承して機能を追加
- 型拡張として機能を追加
- 拡張メソッドとして機能を追加
ここでは4つ紹介されていますが、実はもう一つ方法があります。
コンピュテーションビルダーをラップしたコンピュテーションビルダーを作る
async
や query
といった builder-expr はビルダーオブジェクトが変数束縛されているだけの、ごく普通の存在です。*1
なので、ビルダーの持つメソッドを呼び出すことが可能です。
これを利用してビルダーをラップすることで、後付っぽいことを行います。
試しに、 SimpleBuilder
をラップしてみましょう。
// 既存の SimpleBuilder type SimpleBuilder () = member __.Return(x) = x member __.Bind(x, f) = f x let simple = SimpleBuilder () module Print = type SimpleBuilder () = member this.Return(x) = (sprintf "$b0.Return(x)", simple.Return(x)) member this.Bind(x, f) = let trace, res = simple.Bind(x, f) sprintf "$b0.Bind(%A, fun x -> %s)" x trace, res member this.Delay(f) = f member this.Run(f) = let trace,res = f () printf "let $b0: SimpleBuilder = simple\n%s" trace res let simple = SimpleBuilder() // モジュールをオープンすればラッパーのほうに切り替わる open Print let res = simple { let! x = 10 return x }
出力は以下の通りです。
let $b0: SimpleBuilder = simple $b0.Bind(10, fun x -> $b0.Return(x))
使いどころ
使い道は現時点で3つくらい考えられます。
作ろうと思ったメソッドが既に存在する
同じシグネチャを持つメソッドを型拡張や拡張メソッドで後付することはできません。 この場合は、ソースコードを入手できない場合はラップする以外の選択肢がありません。
式木は重過ぎるけど、介入はしたい
コンピュテーション式にデバッグロガーを仕込みたい場合などの、各メソッド適用後の値に介入したい場合に使います。
適用前に介入したい場合は Source
という手もありますが、あれは特定の構文にしか現れないので、汎用性に乏しいです。
とはいえ、ラップするより型拡張のほうが楽なのは確かです。
ユーザに既存ビルダーの一部機能を使わせたくない
「このビルダー、この実装以外はいいのに!」という状況や、Source
メソッドに介入されてうまくコンパイルできない場合などに使えます。
おすすめ利用順序
機能の後付方法として、個人的なおすすめは
- 型拡張
- ラップ
- コンピュテーションビルダーの書き換え
にの順になります。
型拡張はやっぱり楽なのと、モジュールを分けておけば既存のものを壊さずに済むので、可能であればこれで済ませたいです。
その次はラップです。 多少面倒くさいとはいえ、自由度に機能を追加できます。
ビルダー自体を書き換えるのは、破壊的変更を生み出しかねないので慎重になるべきだと考えています。
継承はあまりお勧めしません。 コンピュテーションビルダーのメソッドがオーバーライドできる可能性は低いからです。
まとめ
たとえ標準の async
だろうと、介入方法はいくらでもあるよというのが言いたかっただけです(ただしドキュメントの仕様から外れるリスクもあります)。
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 }
を用意したりします。
コンピュテーション式の Tips
この記事は F# Advent Calendar 2014 - connpass の初日の記事です。
12月になってしまいましたね、進捗どうですか?私は駄目です。
タイトルは"コンピュテーション式の Tips"となっていますが、中身は Basis.Core や "Persimmon 内で使われているコンピュテーション式の実装方法を勝手に紹介するというだけです。
はじめに
この記事は 2014/12/01 JST 現在書きかけです。 よって、後々更新したときのために gist で diff を残しておきます。
モナド
コンピュテーション式で一番よく知られている(そして誤解するかもしれない)パターン。
do 構文のエミュレーションに必要な最低限のメソッドのみ実装する。
// example type OptionBuilder() = member __.Bind(x, f) = Option.bind f x member __.Return(x) = Some x member __.ReturnFrom(x: _ option) = x let option = OptionBuilder() let l = [10..99] option { let! a = List.tryFind (fun x -> x % 2 = 0) l let! b = List.tryFind (fun x -> x % a = 9) l return (a, b) }
フロー制御
- 目的: 使うキーワードによって後続の計算を分岐させたい
- 実装に使うもの: State, CPS, (try-with)
これは既に id:bleis-tift さんが詳しく解説しているので、紹介にとどめておきます。
more information: yield and return (poor English ver)
例外
- 目的: 最小限のBuilderで例外をハンドリングする
- 実装に使うもの: try-with, custom operator
拡張メソッド
- 目的: 既存のコンピュテーション式を拡張したい
- 実装に使うもの: 拡張メソッド
//examle 1 open Basis.Core 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
//example 2 open System.Threading.Tasks type AsyncBuilder with member __.Source(x: Task<_>) = Async.AwaitTask(x) member __.Source(xs) = Async.Parallel(xs) let task = async { return 1 } |> Async.StartAsTask async { let! x = task return printfn "%d" (x + 1) } |> Async.Start async { let! xs = [0..10] |> List.map (fun x -> async { return x }) return printfn "%A" xs } |> Async.Start
型によるDSL制御
- 目的: キーワードの呼び出し順序を固定したい
- 実装に使うもの: 判別共用体(DU), custom operator, Sourceメソッド
unit
- 目的: unitとそれ以外の型で挙動を変えたい
- 実装に使うもの: 判別共用体, Sourceメソッド
Quotation Evaluation
query ビルダーが公式サンプルである。
カスタムオペレーター
TODO: write
why reverse?
カスタムオペレーターに関するおまけ。
type SampleBuilder() = member __.Yield(()) = Seq.empty member __.Yield(x) = x member __.For (state, _) = state [<CustomOperation("case", AllowIntoPattern=true)>] member inline __.Case(source, case) = seq { yield! source; yield case } [<CustomOperation("run")>] member __.SideEffect(source: _ seq, [<ProjectionParameter>]f: _ * _ -> unit) = source |> Seq.iter f let sample = SampleBuilder() (* expected output: 1, 2 3, 4 but was: 2, 1 4, 3 *) sample { case (1, 2) case (3, 4) into (x, y) run (printfn "%d, %d" x y) }
なぜかタプルが逆順で出力されるのですよねー…仕様なのかバグなのか。
おわりに
TODO: write
余談
最初は FSharp.Karma や Higher や (未完成の) FreeF の解説を書こうかと思っていたけど、テンションがあがらなかったので断念。 それもこれも FreeF が未完成なのが悪い。 Please give me "higher kinded types"!
コンピュテーション式のカスタムオペレーターで遊ぶ
柿プロジェクトを触っているときに思いついたネタです。
ホモビルダー
日本語を使ってみたかったので作ったもの。 ネタが思いつかなかったのでこのネタに…。
https://gist.github.com/pocketberserker/b0f67590f0bcc615b330
一番最初のカスタムオペレーターの変換に unit を引数に取る Yield が呼び出されます。
t-wada さんのサバンナスタンドを表示したかったが…
ネタがないと言っていたら「サバンナ表示させればよいのでは?」と提案されたので。 しかし、等幅フォントだと残念な結果に…。
https://gist.github.com/pocketberserker/4b748d75835737bf4d82
- 指定の順序でない場合コンパイルエラーにしたいので、型を1ラインごとにわける
- オペレーター名をリフレクションで取得する
- バッククオートでくくらないと使えない識別子を使っていたりします
そんなに難しくないです。
ごちうさ
簡約 λカ娘 巻の七を見てやりたくなった。
https://gist.github.com/pocketberserker/ea1b9897ab9a602126fc
- 関数を無理やり合成する感じ
- 呼び出すオペレーターによって変換させたりさせなかったり結合順序を変えたりできる
おわりに
某ガンプラアニメ風に言えば「コンピュテーション式はどんな自由な発想で作ってもいいんだ」
あぁ^~こころがぴょんぴょんするんじゃ^~
FsAttoparsecとattoの内部構造が変わった話とか
私が FsAttoparsec を実装し始めた5月頃、実は本家 attoparsec は内部構造を新しいものに変更していたということに先月末気が付きました*1。 どういう変更かというのは
A major upgrade to attoparsec: more speed, more power | teideal glic deisbhéalach
これ読めばいいと思います。
というわけで、attoparsec の F# 移植である FsAttoparsec や Scala 移植で最近もメンテナンスされている atto も追随させたいと思って修正することにしました。
内部の状態に position を持たせる
とはいえ、F# や Scala は Haskell ではないし、パフォーマンス調査するのも面倒だなーということで内部構造のみ変更することにしました。 そのあたりの変更部分は
https://github.com/pocketberserker/FsAttoparsec/commit/5082a9aa6102b39ee31264aa734117b925be5c52
と
new internal design · 5082a9a · pocketberserker/FsAttoparsec · GitHub
で確認できます。 大雑把にいうと内部状態に position を持つようにしたのでいろいろ取れるようになったね、という。
ちなみにこの内部設計、attoparsec 的には第3世代らしい(前述の記事参照)。
atto のアレなところ?
attoparsec のセールスポイントの一つに"不完全な入力でも動作する"というものがあります。 が、atto の parse メソッドと parseOnly メソッドはその中で feed メソッドを呼び出してしまっているため、このポイントをつぶしているようにも見えるのでした。
(というかこれに気が付かずテストがこけて何事かと思った)
雑感
正直、 attoparsec みたいな実装は rankNtype があって濃度解析のような最適化が組み込まれていて Trampoline を差し込まなくてもスタックオーバーフローにならない言語でないと速度改善は厳しいのかなと。
いやまぁ、インターフェースのメソッドを inline 指定できるとか高速に動作する Trampoline があれば問題ないのですけど、それはちょっと難しそうだしなぁ…。
クラスベースでCPSな実装にした場合のパフォーマンス改善はなかなか難しい問題な気がしてます。
"F# でのテスト用 DSL について考える"で書いたコンピュテーション式
発端や流れに関しては
F# でのテスト用 DSL について考える — a wandering wolf
を読んでください。
本記事では私が実装してみたコンピュテーション式についてゆるく説明します。
先に読むべきもの
コンピュテーション式の実装にStateを用いる - pocketberserkerの爆走
第1版
do!
で失敗したら移行を実行しない- それ以外はとりあえず実行する
みたいな話があったので、ぱっと思いついた Source メソッドを悪用する方針で攻めることにしました。 Source メソッドをオーバーロードすることで、unit型かそれ以外の型かをBindメソッドなどに伝えます。
このタイミングはここで時間切れだったので、中途半端な状態で公開しました。
第2版
テスト結果は、失敗したときにその理由を1つだけ持つのではなく、複数の失敗を持てる、的な
@bleis 最近、それがJUnitで流行っている。soft assertって名前で。
2014-10-22 14:42:55 via TweetDeck to @bleis
こういう話と、bleis さんの実装した
を眺めながらいじったコードが以下になります。
https://gist.github.com/Gab-km/86dd730a8d8e407a699f に触発された何か
Bindメソッドの基本はbleisさんのものを借りつつ、Value に入力型を持たせることで失敗したアサーション以降のアサーションも実行できるようにしました。
Unchecked.defaultof
を使っているので危険では?という意見もあるかもしれませんが、 `let! _`` で捨てる前提なので、これでいいかな、と。
第3版
とはいえ、 let! _
はあまりきれいじゃない気がしますし、どうせなら yield!
のほうがよさそうだよね、ということでさらにいじりました。
https://gist.github.com/Gab-km/86dd730a8d8e407a699f に触発された何か
過去に紹介した、引数で状態を引き回す方法を使ってCombineを実装することにより、 yield!
を連続で呼び出すことが可能です。
Sourceメソッドで注意すべき点
Sourceメソッドはそこそこ変換に現れるので、型合わせるのが簡単ではないです(そこまで難しいわけでもないですが)。
最終版の場合だと、Source メソッドで結果、型情報、状態を生成して型をあわせつつ、YieldFromやReturnFromで状態のみ書き換えるとかしてしのいでいます。
おわりに
実用化?知らない子ですね。
#関数型なんたら という勉強会をやります(ニコ生もあるよ!)
2014年10月25日土曜日に関数プログラミング的な交流会(?)のような勉強会を開催します。
函数型なんたらの集い 2014 in Tokyo - connpass
なぜ1週間前のこのタイミングで告知記事を書いているかというと、二木ニコ生放送があることを伝えたいからです(ドワンゴスタッフの方々、ありがとうございます!)
函数型なんたらの集い 2014 in Tokyo - 2014/10/25 11:30開始 - ニコニコ生放送
当日見れそうにない方も、アカウントがあるならタイムシフト予約しておくと便利かもしれません。
ちなみに
この勉強会の発端は、だいたい毎年行われている"函数プログラミングの集い"が今年はないという話をきいてちょっと残念に思っていたところ、
「野良でやってもいいんじゃない」
という話をTLで観測したので、会場があればやりたいなーと思っていました。 そんなときに
この記事の最後のほうにドワンゴさんの会場の話が書かれていたことを思い出したので、ScalaMatsuriのときに相談した、という流れです。