Arantium Maestum

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

Monadic Parser実装を通して近付く「モナドのお気持ち」

OCamlでMonadic Parserを作ってみる 前編後編で書ききれなかったポエム的なもの。さきにそちらを読んでもらえればわかりやすいかと思う。

HaskellのTypeclassopediaに

The wise student will focus their attention on definitions and examples, without leaning too heavily on any particular metaphor. Intuition will come, in time, on its own.

と書いてある通り、モナドと愉快な仲間たちの概念はまず抽象的な定義をよく読んでから、概念の使用例にたくさん触れていってお気持ちを理解していく必要がある。

今回はパーサコンビネータを通じてモナドの便利さの一側面を見ていきたい。

ネタとしては:

え、パーサをモナドに?・・・できらあ!

そもそもパーサをモナドにするとはどういうことなのか?

そもそもパーサとは?

定義を見てみると「構文解析をするプログラムの総称」とのことで、まあ文字列を受け取ってなんらかの言語だと認識してその構造を表すデータに変換するものだと考えられる。

例えば「文字のリストを受け取って、構文の規則にマッチしているならその部分を表すデータ構造と残った文字列を返し、マッチしないなら失敗する」という流れになる。型で表すなら:

type parser = char list -> (token list * char list) option

とか

type parser = char list -> (expr * char list) option

のようなものになるだろう。

パーサをモナドにする第一歩は、ここでぐっと我慢して

type 'a parser = char list -> ('a * char list) option

と任意の型'aをパラメータにとるよう抽象化することである。

ここで抽象化する理由は「こうしておけばtokenを返すパーサもexprを返すパーサも同じライブラリで作れるし便利」ということではない。結果的にそういう利点もあるが、そこは主眼ではない。

それよりもparserを「任意の型に対するコンテキスト」としての型だと定義していることがMonad的には大事。最終的にexprを返すパーサを作る過程で「文字を返すパーサ」「文字列を返すパーサ」「整数を返すパーサ」、さらには「関数を返すパーサ」などを定義して、その上でそれらを組み合わせていく。正直これはMonadic Parserを調べていた当初はかなり非直感的な考え方だった。

Functor

'a型の値を返すパーサに対して'a->'b型の関数を『適用』して'b型の値を返すパーサを作成する関数mapを定義してやれば'a parser型はFunctor(またの名を関手)となる。

これ単独だと、文字を返すパーサにChar.codeを適用して数字を返すパーサにしたり、Char.uppercase_asciiを適用して文字をパースして大文字に変換して返すパーサを作ったりできる。が、それくらいで表現力はまだまだ弱い。

Functorだと「パーサ同士を組み合わせる」ということができない。これだとまだコンビネータじゃない。

Applicative

FunctorをApplicativeに拡張するには

  • 'a型の値を、その値を返すパーサに変換するpure関数
  • 'a->'b型の関数を返すパーサと'a型の値を返すパーサを組み合わせて'b型の値を返すパーサを作成するapply関数

を追加する必要がある。

余談だがpureapplyはFunctorのmapを二段階に分解したパーツだとイメージすることもできる。

これでパーサが組み合わせられる!やった!

そんな風にテンションが上がっても仕方ないくらい、実際Applicativeで一気に表現力があがってパーサらしいことができるようになる。

let get_two = pure (fun x y -> [x; y]) <*> get_char <*> get_char

で二つの文字をパースして文字リストを返すパーサを、一文字をパースするget_charと、普通の関数であるfun x y -> [x; y]で作れる。(<*>applyの中置演算子である)

ちなみに上記の例ではcurryingが行われていて、まずこれが:

pure (fun x y -> [x; y]) : ('a -> 'a -> 'a list) parser

こうなって:

(pure (fun x y -> [x; y]) <*> get_char) : (char -> char list) parser

こうなる:

(pure (fun x y -> [x; y]) <*> get_char <*> get_char) : char list parser

パーサの型の中に関数がはいっていて、それを他の型のパーサと組み合わせている。

Applicativeのpureapplyを使っていろいろと他にも便利な関数や構文が用意できる:

(* パーサ二つを順に組み合わせて左側のパーサの結果を結果とする *)
let ( <* ) xp yp = (fun x _ -> x) <$> xp <*> yp

(* パーサ二つを順に組み合わせて右側のパーサの結果を結果とする *)
let ( *> ) xp yp = (fun _ x -> x) <$> xp <*> yp


let product xp yp = (fun x y -> (x, y)) <$> xp <*> yp

let (let+) x f = map f x
let (and+) xa ya = product xa ya

ここらへんの演算子や構文の使用例は「OCamlでMonadic Parserを作ってみる 前編後編」に多く書いた。

Functorと合わせて、Parser世界とは関係ない関数を使って、複数の(型が異なる可能性もある)パーサを組み合わせていけるようになり、かなり表現力が増した。

しかし、まだかなり重要な二つのことができない:

  • パーサの分岐(あるパースを試してみて、もし失敗したら違うパースを試す)
  • 前の部分のパース結果の値によって、その後のパースを決める

Alternative

パーサの分岐(あるパースを試してみて、もし失敗したら違うパースを試す)

というのはパーサを書いている時にかなり重要な機能だ。

そもそも、Functor/Applicativeまでの機能だと「パーサは失敗するかもしれない」という概念自体が明示的に現れない。

「失敗するかもしれない」という概念を導入し、「このパーサが失敗した場合は次にこのパーサを試す」という分岐ができるようにするために

  • 必ず失敗するパーサempty
  • パーサを2つ受け取り、「片方が失敗したらもう片方を試す」パーサを作成する<|>演算子

を定義することになる。

これでさらに表現力が強まる。例えばあるパーサを0回以上、あるいは1回以上適用する、というmanysomeを:

let rec many p cs =
  (some p <|> pure []) cs
and some p cs =
  (List.cons <$> p <*> many p) cs

のように定義できるようになる(eta conversionのためのcs引数がダサいが)

Monad

前の部分のパース結果の値によって、その後のパースを決める

というのはかなり抽象的な物言いだが、パーサコンビネータ実装にあたってこの段階でモナドがすごく欲しくなる理由が一つある。

プリミティブな(つまりコンビネータをまったく使わずに定義された)パーサがget_charだけな場合、モナドなしでは「この文字や文字列以外はパース失敗」というパーサが書けない!

get_charが空リストを受け取ると失敗するので「文字列の長さが一定以上かどうか」を確認するパーサは書けるが・・・

モナドbind(やその演算子>>=)があれば'a parserと関数'a -> 'b parserを組み合わせることができる。

let satisfy p =
  let f x =
    if p x
      then pure x
      else empty
  in
  get_char >>= f

fは文字xをとってp x = trueならxを返すパーサ、falseなら失敗するパーサを返す。(実際にはもっと多相な関数だが、get_charと一緒にしか使っていないため)

これで「次がある文字であればパース成功、それ以外ならパース失敗」というパーサが作れる。

これをFunctor/Applicative/Alternativeとして定義した関数・演算子などと組み合わせて複雑化していけば「任意の文字列」だとか「四則演算式」だとか「プログラミング言語」だとかをパースできるようになる。

パーサコンビネータモナドにすると何が嬉しいのか

パーサの型をパラメトリック多相にして、Functor、Applicative、AlternativeそしてMonadとしての演算を定義してパーサコンビネータを作ってきた。

パーサコンビネータ自体はこのような形式をとる必要はない。一例として以下の記事ではF#でパーサコンビネータを作っているが「Monad」の単語も出てこない:

fsharpforfunandprofit.com

(ちなみにこの記事はかなり丁寧なチュートリアルで非常に勉強になった。モナモナせずにただパーサコンビネータについて知りたい、という場合はここから始めるのもいいと思う)

今回パーサコンビネータモナドにして感じたメリットは二つ:

  • モナド(と仲間たち)は非常に組み合わせやすく破綻しにくいAPIであること
  • パーサ以外のコンテキストでも出てくる共通のAPIであること

まず第一のポイント。コンビネータを作る時に「どうやって組み合わせて作っていくのか」を隅々までイメージして作るのは非常に困難だ。気をつけないとすぐ「この組み合わせ方は想定していなかった」ということで、ある処理を記述できなかったり、あるいはバグったりする。それに対して、Monadなどの処理は(数学的なバックグラウンドがあることもあって)抽象性が高く、組み合わせやすい。組み合わせて様々な処理ができ、その処理がなんらかの最低限の保証があるよう、すでに考えられ使われている。そのAPIデザインにタダ乗りできる、というのはとてもありがたい。

第二のポイント。MonadAPIは様々なコンテキストで同一のものが出てくる。Haskellなどを見るとオプション型からIO型からエラー型まで全部モナドのインタフェースで操作できる。OCamlはそこまでモナモナしていないにしろ、option型はちゃんと定義すればMonad的に扱えて便利だし、非同期プログラミングのLwtライブラリなどはPromiseをモナドとして操作するようになっている。パーサコンビネータモナド化することはユーザに馴染みの深いAPIを提供することになる(特定界隈の人たち限定ではあるけど)。

というわけでモナドは嬉しい(必須ではないが)

パーサコンビネータモナドにすると何が嬉しいのか

実はあまり嬉しくないかもしれない・・・

と書くとついさっき述べたことと矛盾しているようだが、そうではない(はず)。

パーサに限ればモナドにしなくてもAlternativeで十分じゃないか?という議論についてである。

Applicative parsing | Notes on Computing

Parsing context-sensitive languages with Applicative | blog :: Brent -> [String]

今回モナドを導入した最大の理由は「パース結果を元にパースが成功したか失敗したかを決定する」satisifyを書くためで、これをプリミティブとしてコンビネータを使わずに書いてしまえばいい。

モナドの他の使いどころとしては

let rec expr cs =
  (let* t = term in
    (pure ((+) t) <*> (get_symbol "+" *> expr)) <|> pure t) cs
(* 以下略 *)

let* t = ...のように、<|>でまったく同じ部分を二度パースする手間を省くために使ったりなどもする。ここらへんは多分コンビネータで書かれたパーサを一旦静的解析して効率化すれば必要なくなるはず。

なのでMonadじゃなくてその手前のApplicative(というよりAlternative)までの機能を提供するだけのほうがいいかもしれない。ただし、その場合それなりに使える効率を出すには実装はもっと難しくなって、パーサをAST化して静的解析して云々、が必要になりそう。

モナドのお気持ち

モナドというのはXみたいなものだ」というのは界隈では有名なジョークみたいなもので、Xにはいるものがなんであれ、この主張の妥当性は常に疑わしい。

「『モナドというのはXみたいなものだ』という人は、象の一部分を触って『象というのはYみたいなものだ』と主張する盲人のようなものだ」とは言えるかもしれない。

パーサをモナド的に作ったからといって「だからモナドはこうなんだ」というにはモナドの抽象性と意外なところでの有用性は高すぎる。

私が言えるのは「パーサをモナド的に作ってみたらこんな感じだったよ」(「象をぺたぺた触ってみたら、触った部分はなんか長くてぐにゃぐにゃしてたよ」)というくらいである。

ただ、「モナドのお気持ち」への理解は、数多くのこのような「ぺたぺた触ってみた」経験の総体の先にあるのではないだろうか。

というわけでこの文章が誰かの「モナドのお気持ち」理解の一助になれば幸いである。

追記

以前の記事でも述べたが、この記事の元になっているのはGraham HuttonのProgramming in Haskellの第13章、タイトルはそのまんま「Monadic Parsing」。邦訳もあるようなのでオススメである。