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

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 を実装した型

標準で提供されている入力は string と byte [] (バイナリ)ですが 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 )と同様の実装になっているため、Haskell や Scala 使いの方にもやさしいです。

まとめ

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

F# Asyncに関しての落書き その1

調べてる最中の落書きなので、指摘ある場合はどんどんお願いします。

コードを読むための前提知識(たぶん)

  • .NETの非同期
  • 継続
  • Trampoline

ソースコード

今読んでるやつ

https://github.com/fsharp/fsharp/blob/6ac6318858da25fe4f1d4728901c5824e9f3bf3a/src/fsharp/FSharp.Core/control.fs

FakeUnitValue

https://github.com/fsharp/fsharp/blob/6ac6318858da25fe4f1d4728901c5824e9f3bf3a/src/fsharp/FSharp.Core/control.fs#L383

ここはコメントの通り、と。

Trampoline

内部でのAsync専用Trampolineの実装に.NETの限界を垣間見る

do!とか

Async in C# and F#: Asynchronous gotchas in C# (Japanese translation) に"末尾再帰関数では do! より return! を使うべき"とか書いてあった気がする。do! の変換を見てみよう。

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

上記でも解説されている通り、do!には二つの変換パターンが存在する。

T(do! e in ce, C) = T(let! () = e      in ce,         C)
T(do! e;,      C) = T(let! () = src(e) in b.Return(), C)

末尾再帰関数として使う場合に使うのは後者。Bindが適用されてからReturnする影響でリークする可能性があるのかな？(実装を全部読む時間が足りない…)まぁ、無駄な呼び出しはしないほうが良いのは確かだ。

Asyncとは関係ないが、let!でもSource適用するのになんでdo!にもつけたのだろう。それも片方の変換だけ…

Async.Catch

コンピュテーション式内でtry withを使うのとAsync.Catchで包むの、どちらが良いのだろう？え、Choice使いたくない？まぁ、はい。

overload

https://github.com/fsharp/fsharp/blob/1745b5f7b19bdb285f3a9c06527b22baf01d41f9/tests/fsharp/typecheck/sigs/pos12.fs

テストで思い切りビルダーに対して拡張メソッドを定義している…わりとよくやるのだろうか。というか、F# 3.0以降なら

type Microsoft.FSharp.Control.AsyncBuilder with
    member x.Source(computation:Task<'T>) = Async.AwaitTask computation

でいいのでは感。どうせなら次のバージョンで標準搭載されてほしい。


会社に遅刻するので、今日はここまで。

Microsoft MVP for F# を再受賞しました

その他

再受賞しました。今年は無理だろうと思っていたので驚いています。これも私にF#を愛でるチャンスをくださり、後押ししてくださった皆様のおかげです。ありがとうございました！今後とも、よろしくお願いします。

去年は何かを作る方向でゆるふわできなかったので、今年は作るほうでゆるふわできたらと考えています。

F#!F#!

社会人になってから1年経過して思ったことなど

詳しく書くほどでもないと思うので箇条書き。

  • 多少日本語になっていない会話でも、なんとかならなくはないのかもしれない
  • たまには外の空気を吸うべき(家と会社の往復のみは思考停止する)
  • コード書く"毎日"は、それはそれで生きていると実感できる
  • 仕事は選べる"かもしれない"
  • 定時帰宅を続けると遅刻回数が減る
  • いざというときに行動するためには、それなりの資金がいる(あたりまえだけど、あらためて)
  • 帰宅しないという選択肢
  • C++とBoostは、これはこれで面白い
  • F#!
  • あだ名重要説
  • SQLアンチパターンは読むべき(背景：この職業、SQLから逃れるのは厳しいのではないか)
  • つい昔話してしまう…これが老いか
  • ノリと勢い、それと運
  • 逆に考えるんだ、「進捗しなくてもいいじゃない」ってさ
  • 夜行バスからの出社は仕事にならない
  • 勉強会で「新卒です」って言ったら驚かれたことがあったのはなんでなんだぜ？

逃避行終わり。資料を書こう…。

パーサコンビネータを使って簡単なNGワードフィルタリング機能を作る

F#

昔、 RSpec の入門とその一歩先へ - t-wadaの日記 を読んで「自分だったらどうつくるかなー」と考えていた。

そして時が経ち、パーサコンビネータを知った今となっては、簡単なものであればこれでいいんじゃないかと思っている。

というわけで、以下は F# の ParsecClone というライブラリを使った例。

フィルタリング対象の文字列を発見する

利用者が指定したワードにマッチするようにすればよい。

// cutting : string -> string
// word: NGワード
let dirtyToTurn cutting word = matchStr word |>> cutting

マッチしたら伏せ字に入れ替える関数を適用すれば、それらしいものになる。

NGワードを複数登録できるようにする

NGワードリスト内のどれかにマッチするようにする。

// words: NGワードリスト
let dirtyToTurn cutting words = anyOf matchStr word |>> cutting

それ以外の文字列

任意の文字列にマッチすれば良い。ParsecClone の場合は any 関数が合致する。

文章を構成する

文章は、NGワードとそれ以外の文字列が０個以上組み合わさっている、と考えられる。

let parser cutting dirtyWords =
  many (dirtyToTurn cutting dirtyWords <|> aby) >>= foldStrings

foldStrings は ParsecClone に存在する関数で、parse した文字列のリストを連結してくれる Parser。

NGワードが含まれているか判定したい

巷のパーサコンビネータライブラリは状態を持つことができるような仕組みを提供していることが多い。ParsecClone にも存在する。

let dirtyToTurn cutting words =
  anyOf matchStr word |>> cutting .>> setUserState true

let parser cutting dirtyWords =
  many (dirtyToTurn cutting dirtyWords <|> aby)
  >>= foldStrings
  .>>. getUserState

これで、最終結果としてNGワードが存在するかどうかとフィルタリング結果が取得できるようになる。

他にも色々やりたい

全角半角を区別せずにフィルタリングしたいとか、でもフィルタリング対象以外の文字列はきちんと復元されてほしいとか色々あるなら、もう少し実装を考える必要がある。

ソースコード

今回のコードは以下においている。

https://github.com/pocketberserker/Harvester

名前の由来はそのうち書く。

他の言語でできるの？

経験から、少なくとも Boost.Spirit(Qi, Karma)はこの手法で実装できる。 あと、割りと新顔の ParsecClone でもできるので、他のライブラリでもできるのではないかなとは思っている。

F# 用非公式 MessagePack ライブラリを作ってみている

F#

F# 特化型です。

ソースコード

公式

公式は CLI 向けの msgpack-cli が存在します。

なぜ作ったの？

公式のものが F# 向きかと言われるとうーんと思い、なら勉強がてら趣味開発に利用しようというのと、公式の F#ラッパーを書く体力がなかったことが発端です。品質などを考えると、公式をラップしたほうが良いというのはわかっているのですが…。

現状

  • pack するためには MsgPackValue<'T when 'T :> comparison> という判別共用体に落としこむ必要あり
  • comparison なのは Map の影響
  • ext を任意の型にしたい場合は packExt<'T when 'T :> IPackable, comparison>, unpackExt<'T when 'T :> comparison>
  • ext を byte [] のまま保持するなら pack, unpack
  • 任意の型にしない場合、もしくは ext を使わない場合は MsgPackValue 型を用いる
  • tyep MsgPackValue = MsgPackValue;; (pack の関係で Unitが使えなかった…)
  • MsgPackValue を簡単に生成するための Limited モジュール
  • 旧仕様は OldSpec モジュールで提供
  • テストは基本的に FsCheck (array32 と map32 の重さに耐えられなかったけど！)
  • unpack の内部実装は PasecClone
  • 実行速度は後で考える

そのうちやりたい

  • 性能検査
  • シグネチャ調整
  • README含むドキュメント整備
  • Type Provider実装
  • Mono 対応 (Mono 3.2.7 だと F# 3.0 にバージョンを下げないといけない…etc)
  • Xamarin 系対応
  • パフォーマンス・チューニング
  • NuGet公開

「御託はいいからさっさと NuGet に公開しろ！」とか言われたら、最優先で対処します。

他にこれほしい、というものあれば twitter なり issue なり pull request なりでお願いします。ユーザ自分しかいなさそうですけどっ！

F# プロジェクトが利用できそうな外部CIサービスについてのメモ

F# AppVeyor

タイトル通りだけど無料版っぽいものがあるもののみ対象。候補は4つ。

Travis

http://travis-ci.com/

みんな大好き Travis ちゃん。 どうやって動かすのかと思いきや、なんとLinux系ならapt-get、Macならmonoをwgetしてインストールするという荒業を使う。以下Macな環境を対象とした .travis.yml の例。

language: objective-c

env:
  matrix:
    - MONO_VERSION="3.2.7"

install:
  - wget "http://download.xamarin.com/MonoFrameworkMDK/Macx86/MonoFramework-MDK-${MONO_VERSION}.macos10.xamarin.x86.pkg"
  - sudo installer -pkg "MonoFramework-MDK-${MONO_VERSION}.macos10.xamarin.x86.pkg" -target /

script:
  - お好みにあわせて記述

Monoでテストが通るか試せるのは大きいけど、いいのかこれ…？ mono 3.2.7 だとまだ FSharp.Core 4.3.1.0 は同梱されていないんじゃないかなー。あと色々面倒くさいので FAKE を併用したほうがよさげ。 FAKE 使いたくないのだけどなー。

利用実績

TeamCity

http://www.jetbrains.com/teamcity/

最初に"無料版っぽいもの"と書いた理由がこの人。 活発でウェブサイトを持っている、活動が活発なコミュニティの、フリーで非営利な開発プロジェクトについて（このあたり英訳あやしいので間違っていたらすみません）Open Source Licenseがあったりする。あくまでコミュニティ用。 使ったことがないのでこれ以上の言及は避ける。

利用実績

  • fsharp

AppVeyor

[2014/03/18 URL修正]

http://www.appveyor.com/

.NETに特化したようなCIサービス。特化しているだけあって、準備がラクダ。 ほとんど設定せずとも F# 3.1 で VS2013 なプロジェクトがビルド & テストできる。試してないけどデプロイもできるようだ。

利用実績

[2014/03/19 Visual F# Power Toolsを追加. id:bleis-tift さん、情報提供ありがとうございます。]

Visual Studio Online

http://www.visualstudio.com/products/visual-studio-online-basic-vs

コラボレーション(?)サービスなので、正確にはCIサービスではないけど一応。BasicだとExpressも対象に含められる。 "Basic プランでの最初の 5 人のユーザーと、資格のあるすべての MSDN サブスクライバー (Visual Studio Professional with MSDN 以上) "という記述の通りである。 F# 3.1 は試したことがないけど、たぶん大丈夫なのではー。

利用実績

自作ライブラリで試したことくらいしかないので、実績求む。

感想

用途にあわせて選べば良いかと。