FsAttoparsecについて

F#

この記事は F# Advent Calendar 2014の16日目の記事兼ML Advent Calendar 2014の16日目の記事になります。

今日はF# のネタリストの中から、FsAttoparsecについてです。

attoparsec とは

attoparsec は Haskell のパーサコンビネータライブラリの一つです。 CPSとインライン展開を用いることで高速化を図っていることが特徴です。 あと実装がそこそこ小さいです。

速度を重視する代わりに犠牲となっているものは、エラー出力です。 まぁ、仕方ないですよね。

なお、attoparsec の現在の実装はこの記事 曰く第3世代だそうです。

FsAttoparsec とは

F# 移植版(+ちょっとした機能追加) attoparsec です。 本家とは違い、今のところ高速とは名乗っていません(実際遅い)。

実装理由

F# のパーサコンビネータライブラリ事情 - pocketberserkerの爆走

この記事にも書いたのですが、FParsec は速いけど文字列のみ、ParsecClone はバイナリに主眼をおいているけどシグネチャがよみづらいし実装間違えると例外が投げられるのがつらいという現実がありました。

というわけなので、上記2つ以外にも候補があってもいいよねと思い、ちょうど現実逃避もしたかったし CPS クンカクンカしたかったので実装しました。

特徴や欠点

  • pure F# implementation
  • 小さな実装
  • トークンパーサ
  • パフォーマンスへの影響
  • 開発者が日本人

pure F# implementation

F# オンリーで FParsec に追いつきたいという意地。

小さな実装

全実装行数がFParsecの1ファイル分だったりするという…FParsecが巨大なだけですが。

トークンパーサ

本家 attoparsec には存在しないのですが、FsAttoparsec には Parsec の TokenParser も実装されています。

パフォーマンスへの影響

F# で GHC 拡張の RankNTypes をエミュレーションするにはメソッドベースで CPS にしなければならず、メソッドを実装するためにはクラスベースにしなければなりません。 このためインターフェースを利用せざるを得なくなり、仮想テーブルの影響でパフォーマンスに影響が出るのが一つ目の問題です。

メソッドはビルド環境設定によっては最適化されないので、スタックオーバーフローを起こします それを回避するために trampoline を使っているのですが…当然のごとくパフォーマンスに影響します。

開発者が日本人

母国語で実装についてきけるのは楽なのではないでしょーか!

むしろ英語で訊かれても答えられない可能性…。

利用実績

F#erが多く在籍している名古屋の会社のどこかで使われているらしいです。

サンプル

テストコード内にLTSVパーサの例が、ベンチマークプロジェクト内にJsonパーサの例があります。

あとは Haskell のコードを参考にするとか、ですかね。

実際どのパーサコンビネータライブラリがいいの?

ここで、とある方の意見を見てみましょう。

これは、文字列解析に関して言えば正しいと思います。 利用実績も多いでしょうし、速度も申し分ないので。

他のデータ構造に関してはどうですかね… ParsecClone も FsAttoparsec も一長一短あるので何とも言えません。

参考資料など

attoparsec の知識がそれなりにそのまま使えます。

このあたりは参考になるかもしれません。

移植にどのくらいかかるのか

FsAttoparsecの移植はコードリーディングからバグ修正まで含めて2週間くらいかかりました。

知っておくべき知識は(速度を求めないなら)

  • CPS (call/cc や shift/reset はわからなくてもよい)
  • Monoid
  • rankNtypes
  • 入力データ構造の各種関数
  • ちょっとしたHaskellコードリーディング力

と、多くもなく難しいわけでもないので、わりとどうにかなるのではないでしょうか。 速度を求めなければ。

OCaml は確かモジュールを使えば rankNtype はなんとかできたはずですし、わりと問題なく実装できそうな気がしますね。

まとめ

attoparsec の別言語への移植は CPS と パーサコンビネータ実装の練習にちょうど良いと思うのでした。

"コンピュテーションビルダーに機能を後付けする"の補足?

アドベントカレンダーとその補足記事で色々と賑わっていて素晴らしいですね。 と、前置きはここまでにしておいて。

コンピュテーション式の変形後を覗き見るを改良する - ぐるぐる~

さて、この記事に下記の記述があります。

さて、コンピュテーションビルダーに対する機能の追加ですが、方法としては以下のものがあるでしょう。

  1. コンピュテーションビルダーの書き換え
  2. 既存のコンピュテーションビルダーを継承して機能を追加
  3. 型拡張として機能を追加
  4. 拡張メソッドとして機能を追加

ここでは4つ紹介されていますが、実はもう一つ方法があります。

コンピュテーションビルダーをラップしたコンピュテーションビルダーを作る

asyncquery といった 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 メソッドに介入されてうまくコンパイルできない場合などに使えます。

おすすめ利用順序

機能の後付方法として、個人的なおすすめは

  1. 型拡張
  2. ラップ
  3. コンピュテーションビルダーの書き換え

にの順になります。

型拡張はやっぱり楽なのと、モジュールを分けておけば既存のものを壊さずに済むので、可能であればこれで済ませたいです。

その次はラップです。 多少面倒くさいとはいえ、自由度に機能を追加できます。

ビルダー自体を書き換えるのは、破壊的変更を生み出しかねないので慎重になるべきだと考えています。

継承はあまりお勧めしません。 コンピュテーションビルダーのメソッドがオーバーライドできる可能性は低いからです。

まとめ

たとえ標準の async だろうと、介入方法はいくらでもあるよというのが言いたかっただけです(ただしドキュメントの仕様から外れるリスクもあります)。

*1:seq だけは例外で、あれはシグネチャを見るとわかるとおり関数です

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 }

を用意したりします。

コンピュテーション式の Tips

F#

この記事は F# Advent Calendar 2014 - connpass の初日の記事です。

12月になってしまいましたね、進捗どうですか?私は駄目です。

タイトルは"コンピュテーション式の Tips"となっていますが、中身は Basis.Core"Persimmon 内で使われているコンピュテーション式の実装方法を勝手に紹介するというだけです。

はじめに

この記事は 2014/12/01 JST 現在書きかけです。 よって、後々更新したときのために gist で diff を残しておきます。

FsAdvent.2014.md

モナド

  • 目的: Haskellのdo構文をエミュレート
  • 実装に使うもの: monad laws, Return, Bind, ReturnFrom (, Zero)

コンピュテーション式で一番よく知られている(そして誤解するかもしれない)パターン。

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

参考: https://github.com/persimmon-projects/Persimmon/blob/87a83d55602268f43a6d31e04ac47dafa2bd8de4/Persimmon/ComputationExpressions.fs#L74

拡張メソッド

  • 目的: 既存のコンピュテーション式を拡張したい
  • 実装に使うもの: 拡張メソッド
//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メソッド

例: https://github.com/persimmon-projects/Persimmon/blob/87a83d55602268f43a6d31e04ac47dafa2bd8de4/Persimmon/ComputationExpressions.fs#L19

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.KarmaHigher や (未完成の) FreeF の解説を書こうかと思っていたけど、テンションがあがらなかったので断念。 それもこれも FreeF が未完成なのが悪い。 Please give me "higher kinded types"!

コンピュテーション式のカスタムオペレーターで遊ぶ

F#

柿プロジェクトを触っているときに思いついたネタです。

ホモビルダー

日本語を使ってみたかったので作ったもの。 ネタが思いつかなかったのでこのネタに…。

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# や ScalaHaskell ではないし、パフォーマンス調査するのも面倒だなーということで内部構造のみ変更することにしました。 そのあたりの変更部分は

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な実装にした場合のパフォーマンス改善はなかなか難しい問題な気がしてます。

*1:初期実装はscala-attoparsecを参考にしていたので本家のコードを読んでなかった

"F# でのテスト用 DSL について考える"で書いたコンピュテーション式

発端や流れに関しては

F# でのテスト用 DSL について考える — a wandering wolf

を読んでください。

本記事では私が実装してみたコンピュテーション式についてゆるく説明します。

先に読むべきもの

詳説コンピュテーション式 - ぐるぐる~

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

第1版

https://gist.github.com/pocketberserker/40006f8da7e195924713/092438c92ed1de1cb65809876fdddcd15c2ad401

  • do! で失敗したら移行を実行しない
  • それ以外はとりあえず実行する

みたいな話があったので、ぱっと思いついた Source メソッドを悪用する方針で攻めることにしました。 Source メソッドオーバーロードすることで、unit型かそれ以外の型かをBindメソッドなどに伝えます。

このタイミングはここで時間切れだったので、中途半端な状態で公開しました。

第2版

こういう話と、bleis さんの実装した

TestBuilder.fs

を眺めながらいじったコードが以下になります。

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で状態のみ書き換えるとかしてしのいでいます。

おわりに

実用化?知らない子ですね。