Julia Advent Calendar 2017の5日目の記事です。今日は,去年の今頃開発を開始したAutoma.jlというパッケージを紹介しようと思います。ここでは,最新リリース版のAutoma.jl 0.4.0を元に記述しています。

Automa.jlとは

Automa.jlは正規表現(regular expression)のドメイン特化言語(DSL: Domain Specific Language)からJuliaのコードを生成するパッケージです。正規表現はJuliaの標準ライブラリにもありますが,Automa.jlの最大の特徴は,正規表現を合成したりマッチングの途中でJuliaのコードを実行したりできる点にあります。これを使えば,正規言語であるファイルフォーマットのパースや,文脈自由文法などで書かれた言語のトークン化などができます。

実際のコードは以下のようになります。このコードは,数値っぽい文字列の種類の判定(8進数か,10進数か,16進数か,浮動小数点数か,など)とトークン化を行います。

import Automa
import Automa.RegExp: @re_str
const re = Automa.RegExp

# 正規表現でパターンを記述
oct      = re"0o[0-7]+"
dec      = re"[-+]?[0-9]+"
hex      = re"0x[0-9A-Fa-f]+"
prefloat = re"[-+]?([0-9]+\.[0-9]*|[0-9]*\.[0-9]+)"
float    = prefloat | re.cat(prefloat | re"[-+]?[0-9]+", re"[eE][-+]?[0-9]+")
number   = oct | dec | hex | float
numbers  = re.cat(re.opt(number), re.rep(re" +" * number), re" *")

# イベント発生時に実行するアクションを登録
number.actions[:enter] = [:mark]
oct.actions[:exit]     = [:oct]
dec.actions[:exit]     = [:dec]
hex.actions[:exit]     = [:hex]
float.actions[:exit]   = [:float]

# 正規言語を有限状態機械にコンパイル
machine = Automa.compile(numbers)

# 有限状態機械の可視化
# write("numbers.dot", Automa.machine2dot(machine))
# run(`dot -Tpng -o numbers.png numbers.dot`)

# Juliaのコードをアクションに関連付け
actions = Dict(
    :mark  => :(mark = p),
    :oct   => :(emit(:oct)),
    :dec   => :(emit(:dec)),
    :hex   => :(emit(:hex)),
    :float => :(emit(:float)),
)

# 有限状態機械とアクションに紐付いたコードからトークン化関数を生成
context = Automa.CodeGenContext()
@eval function tokenize(data::String)
    tokens = Tuple{Symbol,String}[]
    mark = 0
    $(Automa.generate_init_code(context, machine))
    p_end = p_eof = endof(data)
    emit(kind) = push!(tokens, (kind, data[mark:p-1]))
    $(Automa.generate_exec_code(context, machine, actions))
    return tokens, cs == 0 ? :ok : cs < 0 ? :error : :incomplete
end

# トークン化の実行と最終状態の取得
tokens, status = tokenize("1 0x0123BEEF 0o754 3.14 -1e4 +6.022045e23")

実行例です。

~/.j/v/Automa (master) $ julia -qL example/numbers.jl
julia> tokens
6-element Array{Tuple{Symbol,String},1}:
 (:dec,"1")
 (:hex,"0x0123BEEF")
 (:oct,"0o754")
 (:float,"3.14")
 (:float,"-1e4")
 (:float,"+6.022045e23")

julia> status
:ok

コメントに書いたように,Automa.jlは正規表現をコンパイルして有限状態機械(finite state machine: FSM)をつくり,そこからJuliaのコードを吐き出します。上の例で,途中で作られるFSMを可視化すると次のようになります。

最初の状態は左端の◯で囲まれた状態1です。◎の状態は受理状態を表します。この機械は1文字(正確には1バイト)ずつ入力を受け取り状態間を遷移していきます。特殊な入力として,入力の終端を表すEOFという入力もあります。状態遷移の間の辺には,/の後にアクション名が記述されているものもあります。これは,状態遷移の間でその名前のアクションが実行されることを意味しています。アクションには任意のJuliaのコードを記述できるので,状態遷移の際にJuliaのプログラムを差し込めるわけです。上の例では,状態遷移の間でemitという関数を呼び出してマッチしたトークンを文字列から取り出しています。

何に使うのか

Automa.jlはBioJuliaというJuliaで生物学のソフトウェア基盤を作るプロジェクトで,テキストファイルのパーサを生成するために使用しています。生物学で登場するファイルフォーマットは正規言語のものが多いので,Automa.jlの表現力があれば十分対応できます。しかし,ファイル形式が複雑怪奇で,手でたくさんあるファイル形式のパーサを正確に書くのはかなりしんどいです。例えば,VCFというファイル形式のパーサはhttps://github.com/BioJulia/GeneticVariation.jl/blob/master/src/vcf/reader.jlのようになります。これは何十もある状態の間を遷移しますので,普通に手で書くとバグの温床になるでしょう。

また,生物学で使われるファイルはサイズが巨大(1ファイルで数十から数百GBになることも)なことも多く,パフォーマンスも要求されます。そのため,Automa.jlでは正規言語による高レベルな記述を行えば,Automa.jlにあるコンパイラとJulia処理系のコンパイラの力を使って少ない手間で効率が良いコードが生成されるようになっています。

Automa.jlの実装

Automa.jlでは,正規表現の記述からJuliaのコード生成までに幾つかの中間表現を経由します。まずは,Automa.jlの内部で行われる処理を概観してみましょう。次の図は,Juliaの文字列として与えられた正規表現(左端)が,様々な変換と最適化を経てJuliaのコード(右端)になるまでを表しています。

Automa.png

変換の様子を順を追ってみてみましょう。

String -> RE
文字列をパースして正規表現の構文木を作ります。*+?といった量化やe1|e2での選択,[a-z]のような文字クラス,(e)によるグループ化などをサポートしています。パースのアルゴリズムは,簡単なShunting-yardアルゴリズムです。アクションの名前は,各正規表現のオブジェクトにひも付きます。この辺ではJuliaの非標準文字列リテラル(non-standard string literal)を使っていて,例えばre"a+"と書けば正規表現の構文木になります。実装はhttps://github.com/BioJulia/Automa.jl/blob/d81f46ab0ac51ce47dcd49fbc444261ba6c6eb01/src/re.jlにあります。

RE -> NFA
正規表現から,再帰的なThompsonの構成法で非決定性(non-deterministic)のFSMを作っています。このFSMをNFA(non-deterministic finite automaton)といいます。このとき,アクションの優先順位を決定したりしています。また,正規表現の構文糖衣を取る処理もこのレベルで行っています。実装はhttps://github.com/BioJulia/Automa.jl/blob/d81f46ab0ac51ce47dcd49fbc444261ba6c6eb01/src/nfa.jlにあります。

NFA -> DFA
NFAから,powerset construction法で決定性のFSMを作っています。このFSMをDFA(deterministic finite automaton)といいます。実装はhttps://github.com/BioJulia/Automa.jl/blob/d81f46ab0ac51ce47dcd49fbc444261ba6c6eb01/src/dfa.jlにあります。

DFA -> DFA (minimal)
前段階で作られたDFAは状態数が最小になっておらず,冗長な状態があることがあります。そのため,状態数が最小である等価なDFAに変換することで,Juliaのコードを生成した際に小さくなるようにしています。アクションがあるのでちょっと注意が必要ですが,アルゴリズムは素直なものです。実装は上と同じファイルです。

DFA (minimal) -> Julia
変換の最中に発生した到達不可能な状態などを除いた後,Juliaのコードを生成します。Automa.jlには3種類のコード生成器があります。状態と遷移を表引きで決めるもの・状態を変数で扱って遷移をif-elseの分岐でするもの・状態をコードの位置で暗に保持して遷移をif-elseの分岐でするものです。生成されるコードはこの順に大きくなっていくのですが,実行速度はこの順に速くなっていくため,トレードオフでどれにするかを決めます。また,状態の遷移先が自分自身の場合,それをループとみなしてループのアンローリングをする機能もあります。こうすることで,同じ文字パターンが反復される場合にはマッチングが高速になることがあります。生成されるコードは人間が読めたものではありませんが,参考として,最初に上げた例から生成されるコードをhttps://gist.github.com/bicycle1885/379052656354e18d357756a80b0e1423に置きました。実装はhttps://github.com/BioJulia/Automa.jl/blob/d81f46ab0ac51ce47dcd49fbc444261ba6c6eb01/src/codegen.jlにあります。

パフォーマンス比較

Automa.jlが生成するコードのパフォーマンスをPCREと比較してみましょう。データの形式として,簡単な[ACGTacgt]と改行からなるデータに対して4種類の正規表現をマッチさせてみます。ベンチマークスクリプトはrunbenchmarks.jlにあります。なお,この記事を書くに当たり遅くなるケースを見つけたので,ちょっとチューニングしてから計測しました。計測した最初の正規表現では,FSMは次の図のようになります。

case1.png

以下の結果は実行時間の中央値で,値が小さいほど高速です。"Automa.jl (unrolled)"とあるのは,ループのアンローリングをするコードを生成した場合です。

Case 1 ([A-z]*\r?\n)*
PCRE:                 Trial(45.982 μs)
Automa.jl:            Trial(36.971 μs)
Automa.jl (unrolled): Trial(20.481 μs)

Case 2 ([A-Za-z]*\r?\n)*
PCRE:                 Trial(39.038 μs)
Automa.jl:            Trial(59.503 μs)
Automa.jl (unrolled): Trial(47.807 μs)

Case 3 ([ACGTacgt]*\r?\n)*
PCRE:                 Trial(81.441 μs)
Automa.jl:            Trial(59.509 μs)
Automa.jl (unrolled): Trial(47.810 μs)

Case 4 ([A-Za-z\*-]*\r?\n)*
PCRE:                 Trial(81.444 μs)
Automa.jl:            Trial(62.832 μs)
Automa.jl (unrolled): Trial(34.591 μs)

この結果にあるように,Case 2のパターン以外ではAutoma.jlの方が高速になりました。入力は60,000バイトのデータなので,60μsでマッチングを終えたとするとスループットはちょうど1GB/sとなります。Automa.jlが結構高速なコードを生成しているのが分かると思います。

このような感じでJuliaを使うとメタプログラミングを使ったDSLの記述が比較的しやすいです。また,上手く工夫すればそれなりに高速なコードも生成できますので機会があったら試してみて下さい。Automa.jl自体の詳しい使い方はドキュメントを参照して下さい。