FsAttoparsecについて

この記事は 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 と パーサコンビネータ実装の練習にちょうど良いと思うのでした。