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.
と書いてある通り、モナドと愉快な仲間たちの概念はまず抽象的な定義をよく読んでから、概念の使用例にたくさん触れていってお気持ちを理解していく必要がある。
今回はパーサコンビネータを通じてモナドの便利さの一側面を見ていきたい。
ネタとしては:
- パーサコンビネータをモナド(と愉快な仲間たち)にするというのはどういうことか
- Functor/Applicative/Alternative/Monadと段階的に表現力を強くしていく過程で何が得られるのか
- パーサコンビネータをモナドにすると何が嬉しいのか
- 圏論の話はしない(よく知らないので・・・)
え、パーサをモナドに?・・・できらあ!
そもそもパーサをモナドにするとはどういうことなのか?
そもそもパーサとは?
定義を見てみると「構文解析をするプログラムの総称」とのことで、まあ文字列を受け取ってなんらかの言語だと認識してその構造を表すデータに変換するものだと考えられる。
例えば「文字のリストを受け取って、構文の規則にマッチしているならその部分を表すデータ構造と残った文字列を返し、マッチしないなら失敗する」という流れになる。型で表すなら:
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
関数
を追加する必要がある。
余談だがpure
とapply
は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のpure
とapply
を使っていろいろと他にも便利な関数や構文が用意できる:
(* パーサ二つを順に組み合わせて左側のパーサの結果を結果とする *) 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回以上適用する、というmany
やsome
を:
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」の単語も出てこない:
(ちなみにこの記事はかなり丁寧なチュートリアルで非常に勉強になった。モナモナせずにただパーサコンビネータについて知りたい、という場合はここから始めるのもいいと思う)
まず第一のポイント。コンビネータを作る時に「どうやって組み合わせて作っていくのか」を隅々までイメージして作るのは非常に困難だ。気をつけないとすぐ「この組み合わせ方は想定していなかった」ということで、ある処理を記述できなかったり、あるいはバグったりする。それに対して、Monadなどの処理は(数学的なバックグラウンドがあることもあって)抽象性が高く、組み合わせやすい。組み合わせて様々な処理ができ、その処理がなんらかの最低限の保証があるよう、すでに考えられ使われている。そのAPIデザインにタダ乗りできる、というのはとてもありがたい。
第二のポイント。MonadのAPIは様々なコンテキストで同一のものが出てくる。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」。邦訳もあるようなのでオススメである。