OCamlでMonadic Parserを作ってみる(後編)
前回に続いてMonadic Parser Combinatorを実装していく。
再帰
OCamlのような先行評価の言語でMonadic Parserの定義に再帰を使うと問題になる場合とならない場合があるぞい。
問題にならない場合:
let match_string s = let rec f = function [] -> pure [] | c::cs -> let* _ = match_char c and* _ = f cs in pure (c::cs) in String.to_list s |> f |> map String.of_list
ある文字列がパース対象の先頭にあるか、というパーサ。「先頭にあってほしい文字列」に対して再帰しているので普通に停止する。
問題になる場合:
let rec many p = some p <|> pure [] and some p = List.cons <$> p <*> many p
あるパーサを0回以上適用するmany
と1回以上適用するsome
を相互再帰で定義している、つもりなコード。
これはHutton本に出てくるHaskell版:
many x = some x <|> pure [] some x = pure (:) <*> x <*> many x
のほぼ直訳で、残念ながらOCamlではうまくいかない。使ってみるとStack Overflowを起こす:
utop # parse (many get_char) "abc";; Stack overflow during evaluation (looping recursion?).
コードをよく読んでみればわかるが、先行評価では無限再帰してしまう。ちょっとダサくなるが、eta conversionを入れる(明示的にパーサの引数を書く)ことで無限再帰を回避できる:
let rec many p cs = (some p <|> pure []) cs and some p cs = (List.cons <$> p <*> many p) cs
ちょっとダサいが・・・
コンビネータ
many
やsome
を使ってさらにコンビネータを定義:
let match_ident = let match_ident_list = List.cons <$> match_lower <*> many match_alphanum in String.of_list <$> match_ident_list let match_nat = int_of_string <$> (String.of_list <$> some match_digit) let match_int = match_nat <|> ((~-) <$> (match_char '-' *> match_nat))
小文字から始まるidentifierや整数をパースできるようになった。
次はまわりの空白を無視してパースするget_token
関数:
let get_token p = many match_space *> p <* many match_space
get_token
を使っていろいろ定義してみる:
let get_ident = get_token match_ident let get_nat = get_token match_nat let get_int = get_token match_int let get_symbol s = get_token (match_string s)
使ってみる:
let get_nats = let+ _ = get_symbol "[" and+ n = get_nat and+ ns = many (get_symbol "," *> get_nat) and+ _ = get_symbol "]" in n :: ns
utop # parse get_nats "[1, 2, 3, 4, 5]";; - : (int list * char list) option = Some ([1; 2; 3; 4; 5], [])
余談だがlet+
は使わずにget_nats
を定義することもできる:
let get_nats = pure List.cons <* get_symbol "(" <*> get_nat <*> many (get_symbol "," *> get_nat) <* get_symbol ")"
どっちが読みやすいか・・・ これだけ長いとlet+
を使った方がどの部分が最終的な結果に使われるかわかりやすいように思う。というわけでApplicative letは便利。
計算順序に則った数式パーサ
パーサコンビネータとしてある程度機能が揃ってきたので、これを使って計算順序を守った足し算・掛け算式のパーサを書いてみる。
Haskell版:
expr = do t <- term do symbol "+" e <- expr return (t + e) <|> return t term = do f <- factor do symbol "*" t <- term return (f * t) <|> return f factor = do symbol "(" e <- expr symbol ")" return e <|> natural
ダメなOCaml版:
let rec expr = let* t = term in (pure ((+) t) <*> (get_symbol "+" *> expr)) <|> pure t and term = let* f = factor in (pure (( * ) f) <*> (get_symbol "*" *> term)) <|> pure f and factor = get_symbol "(" *> expr <* get_symbol ")" <|> get_nat;;
何故ダメなのかというと、やっぱり無限再帰の問題である。
解決策はやはりeta conversion:
let rec expr cs = (let* t = term in (pure ((+) t) <*> (get_symbol "+" *> expr)) <|> pure t) cs and term cs = (let* f = factor in (pure (( * ) f) <*> (get_symbol "*" *> term)) <|> pure f) cs and factor cs = (get_symbol "(" *> expr <* get_symbol ")" <|> get_nat) cs
ちょっとダサいが・・・ いや、これは実際かなりダサい。some
やmany
の場合はパーサコンビネータ側でパーサの実装がchar list -> ('a * char list) option
であることを利用してeta expansionしているわけだが、expr
の場合はコンビネータのユーザ側のコードで同じことをせざるを得なくなっている。うまい解決方法があればいいのだが、思いつかない(&調べたところeta expansionしろ、というのがStack Overflowなどでは一般的な助言のようだ)。ぐぬぬ。
使ってみるとこんな感じ:
utop # parse expr "1+2*3+4*(5+6)";; - : (int * char list) option = Some (51, [])
感想
大枠ではHaskellとほぼ同一の表現でいけることがわかった。
違いとしては
- Stringがchar listじゃない。すこし変換の手間がかかるが大したことではない
- HaskellのStandard Libraryのほうが充実している。OCamlで
String.of_list
やis_upper
などがStandard Libraryにないのは悲しい。 - 遅延評価 vs 先行評価。これが一番大きい。プログラミング言語の定義は大概再帰的になっているので、パーサのいろんなところでeta conversionする必要が出てくるように思う。ダサい・・・
コンビネータ部分やFunctor/Applicative/Alternative/Monad部分をlazy
を使って遅延化すれば避けられるか?とも考えたのだが、expr
、term
、factor
のようなユーザコード側での相互再帰的な定義に対しての影響力はないはず(引数部分が先行で評価されてしまう)。けっきょくユーザコードでもlazy
を使う羽目になるし、それだったらeta conversionするのもほとんど変わらないはず?効率化の観点からはlazy
のほうがいいかもしれないが・・・
ちなみに全然違うやり方として以下の記事で紹介されている「パーサをいったん独自のAST的データ構造で表現し、パースするときはそのコードを評価する」という手法もあるらしい。機会があったら試してみたい。