Arantium Maestum

プログラミング、囲碁、読書の話題

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

ちょっとダサいが・・・

コンビネータ

manysomeを使ってさらにコンビネータを定義:

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

ちょっとダサいが・・・ いや、これは実際かなりダサい。somemanyの場合はパーサコンビネータ側でパーサの実装が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のほうが充実している。OCamlString.of_listis_upperなどがStandard Libraryにないのは悲しい。
  • 遅延評価 vs 先行評価。これが一番大きい。プログラミング言語の定義は大概再帰的になっているので、パーサのいろんなところでeta conversionする必要が出てくるように思う。ダサい・・・

コンビネータ部分やFunctor/Applicative/Alternative/Monad部分をlazyを使って遅延化すれば避けられるか?とも考えたのだが、exprtermfactorのようなユーザコード側での相互再帰的な定義に対しての影響力はないはず(引数部分が先行で評価されてしまう)。けっきょくユーザコードでもlazyを使う羽目になるし、それだったらeta conversionするのもほとんど変わらないはず?効率化の観点からはlazyのほうがいいかもしれないが・・・

ちなみに全然違うやり方として以下の記事で紹介されている「パーサをいったん独自のAST的データ構造で表現し、パースするときはそのコードを評価する」という手法もあるらしい。機会があったら試してみたい。

jobjo.github.io

今回のコード

github.com