概要
皆さんはパーサコンビネータをご存知ですか？
いわゆる構文解析器の実装方法の一つで、一つの終端/非終端文字を一つの関数（小さな解析器）に対応付けて表現し、その組み合わせで解析器全体を作る手法です。
例えば次の文法
$$
S \to aSb \mid \varepsilon
$$
に合致するか判定するプログラムを、以下のような見た目で書くことができます。
// Context-free grammar
// S -> aSb | ε
use monapa::*;
fn start() -> Parser<()> {
pdo! (
single('a');
start();
single('b');
return ()
) | Parser::ret(())
}
fn main() {
let parser = start();
assert!(parser.parse("aabb").is_ok());
}
single('a');
start();
single('b');
↑この部分が生成規則の $aSb$ に直接対応していて、とても素直なのが特長です。
C++のBoost.Spirit、Rustのcombine、JavaScriptのparsimmonなど、世の中には既に多くのパーサコンビネータライブラリがあります。
しかし、パーサコンビネータの利点である「記法の素直さ」を最大限に引き出すにはモナドに対するdo記法が極めて重要です。
今回、私はRust言語にて、do記法を模倣する pdo! マクロ、およびこれを組み込んだモナディックパーサライブラリ monapa を開発しました。その紹介記事となります。
序章：デザインパターンとしてのモナド
モナドとは、自己関手 $T : \mathcal{C} \to \mathcal{C}$ と二つの自然変換 $\eta : \text{Id} \to T$ および $\mu : T^2 \to T$ からなる三項組 $(T, \eta, \mu)$ のうち、クライスリ射の合成がモノイド則を満たすもののこと
などのお題目は置いておき。
実用上の意味をあえて強調して説明すると、モナドとは「bind関数というメソッドが用意されていて、それのおかげでなんか便利に使えるようになっているクラス」の総称です。本記事では学術用語の意味がかなり不正確になることを覚悟で、これをモナドの定義であるとしてしまいます。
一例としてJavaScriptにある Promise はモナドです。
const p = Promise.resolve(5);
p.then(x => Promise.resolve(x + 2))
thenメソッドは「数値を受け取りPromiseを返す無名関数」を引数として受け取っています。
このような種類のメソッド（正確には m a -> (a -> m b) -> m b というシグネチャを持つ高階関数）はbind関数と呼ばれ、これさえ備えていれば、言ってしまえば全部モナドです。
他にもRustのOptionとResult型、多くの言語にあるリスト型など、この種類のメソッドを持っている型は割とありふれています。「bind関数を備えている」という意味でなら、モナドは既に一種のデザインパターンとして一定の地位を築いていると言えるでしょう。
monapa の基本
さて、モナドの話は一旦忘れて、本題である拙作の monapa ライブラリの紹介に移ります。
monapa は、解析表現文法 (PEG) を対象としたシンプルなパーサコンビネータライブラリです。特定の文字列を読み取る chunk("hoge")、任意の英数字1つを読み取る alphanumeric() などの基本パーツがあらかじめ用意されており、ユーザはこれらを組み合わせることで複雑な文法の解析器を作成していきます。
Parser<T> 型が一つのパーサを表します。そしてこれらのパーサを「連接」「選択」「繰り返し」などの形で合成して、新たな Parser<T'> を作ることができます。
// 選択
let p1: Parser<String> = chunk("Apple");
let p2: Parser<String> = chunk("Orange");
let p3: Parser<String> = p1 | p2;
// "Apple" と "Orange" を受理
// 0回以上の繰り返し
let p1: Parser<String> = chunk("Apple");
let p2: Parser<Vec<String>> = p1 * (0..)
// "Apple" や "AppleApple" などを受理
// 連接
let p1: Parser<String> = chunk("Apple");
let p2: Parser<String> = chunk("Orange");
let p3: Parser<String> = p1.bind(move |_| p2);
// "AppleOrange" を受理
連接を表すのにbindメソッドなるものを使っているのがポイントです。
bindは Parser<T> 型に生えているメソッドであり、Fn(T) -> Parser<S> を受け取って Parser<S> を返します。直観的には「Parser<T> と Parser<S> を連続して実行するパーサを生成する」という意味合いです。
パーサ二つをただ連結させたいならば p1 & p2 のように書くのが自然に思うかもしれません。しかし、そうすると前方のパーサのパース結果（後述）を後ろのパーサに渡す術が無くなってしまいます。これを防ぐ工夫として、bindは引数としてFn(T) -> Parser<S>というラムダ式を受け取るようにしているのです。
そして、このbindメソッドの型を専門的に書くと Parser T -> (T -> Parser S) -> Parser S となります。これは前章で紹介した"モナドにおけるbind関数"の型シグネチャ m a -> (a -> m b) -> m b そのものです！
というわけで、Parser はモナドです。モナディックパーサです。
パースの結果を取得する
パーサ Parser<T> は受理or拒否をYes/Noで判定できるだけでなく、パース結果を任意の T 型で返すことができます。
以下のプログラムは、カッコで囲われた文字列からカッコ内の内容を抽出します（(piyo) を与えると piyo が返る）。
use monapa::*;
fn text() -> Parser<String> {
(alphanumeric() * (0..)).map(|vc| vc.into_iter().collect())
}
fn start() -> Parser<String> {
single('(')
.bind(move |_| text().bind(move |t| single(')').bind(move |_| Parser::ret(t.clone()))))
}
fn main() {
let parser = start();
println!("{}", parser.parse("(piyo)").unwrap());
}
初見だとかなり難解なコードですが、start()内にてbindメソッドで連接を複数回行っているのがポイントです。
そう、パーサコンビネータといえども、普通に書くだけでは可読性の真価を発揮することはできません。これをもっと分かりやすく書き換える武器として、pdo! マクロを導入します！
pdo! マクロ
先ほどのようなbindメソッドの入れ子構造を、平坦な見た目に置き換えてくれるマクロが pdo! です。
start()関数は、以下のような等価な形で置き換えられます。
use monapa::*;
fn text() -> Parser<String> {
(alphanumeric() * (0..)).map(|vc| vc.into_iter().collect())
}
fn start() -> Parser<String> {
pdo! {
single('(');
t <- text();
single(')');
return t
}
}
fn main() {
let parser = start();
println!("{}", parser.parse("(piyo)").unwrap());
}
pdo! マクロは、p.bind(move |x| pdo!{...}) という形を生成するよう再帰的に展開するマクロであり、Haskellにおけるdo記法の忠実な模倣です。
ちなみに「parserのdo」なので pdo! と名付けています。
pdo! マクロが具体的にどう展開されるのか、直観的には以下の3つの規則にまとめられます。
規則１：基本形
基本的には以下のような形で、再帰的に展開されます。（あくまでイメージ）
pdo! {
x <- p1;
y <- p2;
z <- p3;
p4
}
// ↓↓↓ 展開 ↓↓↓
p1.bind(move |x|
pdo! {
y <- p2;
z <- p3;
p4
}
)
// ↓↓↓ 展開 ↓↓↓
p1.bind(move |x|
p2.bind(move |y|
pdo! {
z <- p3;
p4
}
)
)
// ↓↓↓ 展開 ↓↓↓
p1.bind(move |x|
p2.bind(move |y|
p3.bind(move |z|
pdo! {
p4
}
)
)
)
// ↓↓↓ 展開 ↓↓↓
p1.bind(move |x|
p2.bind(move |y|
p3.bind(move |z|
p4
)
)
)
規則２：矢印は省略可能
モナドから抽出する値が不要のときは、矢印およびその左側の仮引数を省略できます。
pdo! {
p1;
y <- p2;
p3;
p4
}
// ↑↑↑ 等価 ↓↓↓
pdo! {
_ <- p1;
y <- p2;
_ <- p3;
p4
}
// ↑↑↑ 等価 ↓↓↓
p1.bind(move |_|
p2.bind(move |y|
p3.bind(move |_|
p4
)
)
)
規則３：最後の式のreturnキーワード
最後の式にモナド p を置く代わりに、return xという構文を置くことができます。これはParser::ret(x)の簡略記法です。
※このreturnキーワードはあくまでマクロ内で特別に意味を持つものであり、関数の戻り値を表す組み込み構文とは別物です。
pdo! {
p1;
y <- p2;
p3;
return y
}
// ↑↑↑ 等価 ↓↓↓
pdo! {
p1;
y <- p2;
p3;
Parser::ret(y)
}
// ↑↑↑ 等価 ↓↓↓
p1.bind(move |_|
p2.bind(move |y|
p3.bind(move |_|
Parser::ret(y)
)
)
)
ここで、Parser::ret はモナドにおけるpure/return関数です。パーサとしては空文字列 $\varepsilon$ をパースすることで常に成功する動作を表します。
（追記）規則４：let文を挿入できる
解説を忘れるところでした。
これは使いやすさのためのおまけ機能とも捉えられますが、let文を挟むことが可能です。
pdo! {
p1;
y <- p2;
let val = some_conversion(y);
p3;
return val
}
// ↑↑↑ 等価 ↓↓↓
p1.bind(move |_|
p2.bind(move |y| {
let val = some_conversion(y);
p3.bind(move |_|
Parser::ret(val)
)
})
)
規則は以上の3 (+1) つだけです。do記法に慣れていない方はだいぶ混乱するかもしれませんが、とりあえずbindのネストを略記する方法であることを抑えた上で、上記の規則をじっくり眺めてくれたらと思います。
pdo! マクロの実装
ここから先は開発記録となります。
キャプチャした変数の所有権を厳格に管理するというRust言語の特性ゆえに、単純な再帰的展開だけではうまく実装できませんでした。
対処法として、各クロージャの直前に環境をすべてクローンするという工夫により解決しています。
以下その確認がてら、完成した pdo! マクロの実装全体を見渡してみましょう。宣言的マクロです。
#[macro_export]
macro_rules! pdo {
($($t:tt)*) => {
$crate::pdo_with_env!{~~ $($t)*}
};
}
#[macro_export]
macro_rules! pdo_with_env {
// 値を取り出してbindする（>>=）
(~$($env:ident)*~ $i:ident <- $e:expr; $($t:tt)*) => {
$crate::Parser::bind($e, move |$i| {
$(let $env = $env.clone();)*
$crate::pdo_with_env!{~$($env)* $i~ $($t)*}
})
};
// モナドから取り出した値を使わない場合（>>）
(~$($env:ident)*~ $e:expr; $($t:tt)*) => {
$crate::Parser::bind($e, move |_| {
$(let $env = $env.clone();)*
$crate::pdo_with_env!{~$($env)*~ $($t)*}
})
};
// let文
(~$($env:ident)*~ let $i:ident = $e:expr; $($t:tt)*) => {
let $i = $e;
$crate::pdo_with_env!{~$($env)* $i~ $($t)*}
};
// return関数
(~$($env:ident)*~ return $e:expr) => {
$crate::Parser::ret($e)
};
// returnでなくモナドを直接指定して返す
(~$($env:ident)*~ $e:expr) => {
$e
};
}
pdo! マクロの実態は pdo_with_env! です。このマクロは引数の先頭で ~$($env:ident)*~ という構文木片を受け取ります。
使用例としては pdo_with_env!{~foo bar~ ...} という形です。この~ ~（チルダ）で囲まれた部分に、変数名 foo bar などをスペース区切りで書いておくと、それらがクロージャの直前で都度シャドーイングクローンされるようになっています。
一つ懸念されることは、複製による性能悪化です。パーサを使い捨てでなく何度も呼び出せるようにする（内部でFnOnceでなくFnを持つ）ためにどうしても必須だろうという判断でクローンしているのですが、より良い設計があれば積極的に探求していく所存です。
動作例
最後に、cargo expandを用いてマクロを実際に展開してみた結果を載せておきます。
Before:
use monapa::*;
fn text() -> Parser<String> {
(alphanumeric() * (0..)).map(|vc| vc.into_iter().collect())
}
fn start() -> Parser<String> {
pdo! {
single('(');
t <- text();
single(')');
return t
}
}
fn main() {
let parser = start();
println!("{}", parser.parse("(piyo)").unwrap());
}
After:
#![feature(prelude_import)]
#[prelude_import]
use std::prelude::rust_2021::*;
#[macro_use]
extern crate std;
use monapa::*;
fn text() -> Parser<String> {
(alphanumeric() * (0..)).map(|vc| vc.into_iter().collect())
}
fn start() -> Parser<String> {
::monapa::Parser::bind(
single('('),
move |_| {
::monapa::Parser::bind(
text(),
move |t| {
::monapa::Parser::bind(
single(')'),
move |_| {
let t = t.clone();
::monapa::Parser::ret(t)
},
)
},
)
},
)
}
fn main() {
let parser = start();
{
::std::io::_print(format_args!("{0}\n", parser.parse("(piyo)").unwrap()));
};
}
👍✨
まとめ
今回は、do記法を搭載することで、生成規則（特に連接）を素直に表現できるようにしたパーサコンビネータライブラリ monapa を紹介しました。
monapa を開発するにあたって、Haskellの megaparsec ライブラリから多大な影響を受けました。パーサに対するモナド的操作を考え、それをdo記法で簡潔に記述する。他ではあまり見られない技法ですが、一見の価値がある美しいテクニックです。
モナドの概念は使いこなすのが難しく、もっと言ってしまえばその数理的な発展度合いとは裏腹に、「これは便利だね」と言える卑近な活用例があまり考案・周知されていない分野だと感じます。do構文のような糖衣構文を使える言語が少ないという事実もそれに拍車を掛けています。
そんな状況下での数少ない実用例が、このパーサコンビネータなのではないでしょうか。Rustのマクロには幸い、それを実現するだけの十分なパワーがありました。
さて、monapa はまだまだ荒削りのライブラリです。
- 先読みができない。つまり入力を消費せずに確認することができない
- packrat parsingには非対応
- 左再帰対策が甘い（形によっては一応rust-analyzerが警告を出してくれる）
- 解析失敗時のエラー出力が貧弱
-
pdo!マクロ内で補完が効かない（つらい…）
それでも「生成規則を素直に書き表せる」という長所に興味を持ったならば、ぜひ触れてみてください。この記事がパーサやモナドの可能性に気付くきっかけとなれば幸いです。