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-23

FsAttoparsecとattoの内部構造が変わった話とか

F# Scala Haskell

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

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