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

F# のパーサコンビネータに関するメモ書きです。 情報が揃ったら、Qiitaに投下するかもしれません。

種類

ここでは3つのライブラリを対象にします。

  • FParsec
  • ParsecClone
  • FsAttoparsec

他にも「これかけよ!」などあればご連絡ください。

FParsec

FParsec は Haskell でポピュラーな Parsec の F# 適応です。

古の時代から存在しているライブラリです(ぉぃ

入力は文字列のみ

https://bitbucket.org/fparsec/main/src/c234349e7b738e09a1b9eb53f5f1ef77d584f09b/FParsec/Primitives.fsi?at=default#cl-20

を見ていただけると分かる通り、FParsec では CharStream を受け取って計算結果を返す関数を Parser として扱います。 CharStream は文字列操作を扱う FParsec 独自の型です。

File や Stream を入力として受け取り、解析を行う関数も用意されています。 しかし、これらの関数には System.Text.Encoding を渡す必要があります。

速い

文字列に特化させただけあってか、かなり高速です。おそらく、

  • CharStream 内ではポインタなどを駆使している
  • コンビネータの内部実装は for や mutable を駆使した泥臭い実装(外部からは immutable に見える)

などが高速化につながっているのではないか、と考えられます。

ドキュメントが整備されている

ドキュメントが充実しています。

日本語チュートリアルが存在する

@ さんの手によって、チュートリアルが日本語に翻訳されています。

http://blog.livedoor.jp/gab_km/archives/1437534.html

また、F# 黎明期から存在するので、FParsec を利用した日本語記事も多数確認できます。

ライブラリ自体のコードを読むには C# の知識も必要

CharStream を始めとして、多くの型が C# で実装されています。これらの実装は FParsecCS.dll に含まれています。

また、 CharStream の実装にはポインタが使われています。つまり、C# のポインタの知識がなければコードが読めません。

ParsecClone

ParsecClone は FParsec の subset clone です。

入力は IStreamP を実装した型

標準で提供されている入力は stringbyte [] (バイナリ)ですが bit (ParsecClone 独自の型)ですが、 IStreamP インターフェースを実装すれば、入力として指定できます。

バイナリ解析は速い

バイナリ解析の入力として使用される BinStream は、内部でキャッシュを持っていたりします。

では StringStream はというと…キャッシュを持っていないので、遅いです。つまり、入力データ型の実装によって速度はまちまちです。

エラー情報が少ない

Parser の適用結果が Option と IStreamP のタプルなので、失敗した場合の情報が少ないです。

また、いくつかの関数では特定の条件で例外を投げる実装になっているため、問題特定が難しい場合があります。

シグネチャが読みづらい

ParsecClone の関数の多くは型が明示されていません。 かといって fsi が定義されているわけでもないので、Visual Studio でカーソルを合わせてみても Parser 型と表示されません。

Parser を合成すると型エラーが読めず苦労する、なんてこともあります。

サンプルコードが面白い

サンプルコードとして、CSVパーサとMP4ヘッダーバイナリパーサが用意されています。

FsAttoparsec

Haskell の Attoparsec を、 F# へと移植したライブラリです。

筆者が(主に現実逃避中に)実装したものです。

入力はいくつかの関数と Monoid を実装した型

length, head, tail, splitAt, span, skipWhile, take, cons 操作を持つ型に対して Monoid を定義すれば、入力として扱うことができます。

遅い

atto の名に反して、遅いです。

  • 1万件の要素を持つJsonデータの解析で、 FParsec と比較して 約10倍差
  • バイナリ解析で、ParsecClone と比較して約10倍差(要再計測)

おそらく、入力データの操作で遅くなっています。改善策を検討中です。

エラー情報が少ない

エラー情報が全くないわけではありませんが、原因特定はちょっと大変かもしれません。 ここは Attoparsec 所以なので、仕方ないかなと諦めています。

Trampoline

継続渡しスタイルを用いて実装しているのですが、x64 環境での Release ビルドでしかメソッド呼び出しの最適化が(おそらく)行われない関係で、他の環境ではスタックオーバーフローを引き起こします。 これを回避するため、Trampoline を使っています。

サンプルコード

現時点でLTSVパーサ、Jsonパーサが存在します。

Pure FSharp

F# のみで実装しています。 また、ほぼ Attoparsec (もしくは scala-attoparsec およびその fork である atto )と同様の実装になっているため、HaskellScala 使いの方にもやさしいです。

まとめ

選択肢が増えることは、良いことだなって。