Rust のパーサコンビネータライブラリ combine を使う時の tips
Rust のパーサコンビネータライブラリの一つである Marwes/combine: A parser combinator library for Rust を使ってみています.
詳しい使い方はきちんとしたドキュメントがあるのでそちらを参照してください.
ざっくりいうと Haskell の parsec: Monadic parser combinators | Hackage の Rust 版という感じです.
(ちなみに私も combine を参考に C++ でパーサコンビネータを作ってみたりしました. ) agtn.hatenablog.com
で、このライブラリ、とてもジェネリックなコードで書かれているので、かなりコンパイル時間が増加します… (Boost.Spirit 系に近いです. コンパイルエラーなどは遥かに読みやすいのであまり困ることはないですが)
パーサを書いている時にはテストは頻繁に行いたいので,ちょっとコンパイルがおそいのはつらい.
なにか解決策はないかなぁと思っていたら本家に issue がたっていました.
Extremely long compile times · Issue #21 · Marwes/combine
今回この issue にかかれていた内容を検証してみたので,ここでまとめておこうと思います.
結論
パーサの定義を,ジェネリックな構造体のメソッドとして定義するとコンパイル時間が大幅に短くなる
方法
まずはじめに言われているのは,入力ストリーム型をI: Stream<Item=char>
から &str
にしてしまうという方法です.
(It might be possible to specialize the parsers directly as well, say
fn expr(input: State<&str>) -> ParseResult<Expr, &str>
instead offn expr<I: Stream>(input: State<I>) -> ParseResult<I, &str>
)
これは作ったパーサをジェネリックな入力に対して適用することができなくなりますが,ライブラリの利用者側としては,char
のストリームといったらだいたい &str
だと思うので,ぶっちゃけジェネリックじゃなくてもいいじゃんという感じです.
そしてもう一つが, ジェネリックな構造体を作って,パーサの定義をその中に閉じ込めるという方法です.
ちょっとこちらはコード例を実際に見たほうがわかりやすいと思うので後で説明します.
実験コード
というわけで,
の三種類について,コンパイル時間をはかってみます.
パーサ界のハローワールド,計算機で実験してみます. まずはジェネリックなパーサです.
use combine::*; use combine::primitives::Stream; pub fn integer<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { many1::<Vec<_>, _>(digit()) .map(|is| is.into_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64))) .parse_state(input) } pub fn factor<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { between(char('('), char(')'), parser(expr)).or(parser(integer)).parse_state(input) } pub fn term<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { let op = char('*').or(char('/')).map(|c| { move |lhs, rhs| match c { '*' => lhs * rhs, '/' => lhs / rhs, _ => unreachable!(), } }); chainl1(parser(factor), op).parse_state(input) } pub fn expr<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { let op = char('+').or(char('-')).map(|c| { move |lhs, rhs| match c { '+' => lhs + rhs, '-' => lhs - rhs, _ => unreachable!(), } }); chainl1(parser(term), op).parse_state(input) } pub fn parse<I>(input: I) -> Result<(i64, I), ParseError<I>> where I: Stream<Item = char> { parser(expr).parse(input) }
それぞれの関数が一つのパーサの役割を担います.それぞれのパーサが独立していて,それぞれ別々に型変数を導入しています.
次に &str
だけを受け取るパーサです.これは上記のジェネリックなパーサの,型変数を &str
に置き換えるだけなのでとても簡単です.
一部だけ掲載します.
pub fn expr(input: State<&str>) -> ParseResult<i64, &str> { let op = char('+').or(char('-')).map(|c| { move |lhs, rhs| match c { '+' => lhs + rhs, '-' => lhs - rhs, _ => unreachable!(), } }); chainl1(parser(term), op).parse_state(input) } pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> { parser(expr).parse(input) }
最後が,ジェネリックな構造体のメソッド中に,ジェネリックでないパーサを定義して閉じ込める方法です.
use combine::*; use combine::primitives::Stream; use std::marker::PhantomData; truct P<I>(PhantomData<fn(I) -> I>); impl<I> P<I> where I: Stream<Item = char> { pub fn integer(input: State<I>) -> ParseResult<i64, I> { many1::<Vec<_>, _>(digit()) .map(|is| is.into_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64))) .parse_state(input) } pub fn factor(input: State<I>) -> ParseResult<i64, I> { between(char('('), char(')'), parser(P::<I>::expr)) .or(parser(P::<I>::integer)) .parse_state(input) } pub fn term(input: State<I>) -> ParseResult<i64, I> { let op = char('*').or(char('/')).map(|c| { move |lhs, rhs| match c { '*' => lhs * rhs, '/' => lhs / rhs, _ => unreachable!(), } }); chainl1(parser(P::<I>::factor), op).parse_state(input) } pub fn expr(input: State<I>) -> ParseResult<i64, I> { let op = char('+').or(char('-')).map(|c| { move |lhs, rhs| match c { '+' => lhs + rhs, '-' => lhs - rhs, _ => unreachable!(), } }); chainl1(parser(P::<I>::term), op).parse_state(input) } } pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> { parser(P::expr).parse(input) }
言葉で説明すると難しいのですが,型変数を導入する部分を構造体の定義部分だけにしてあげることで,型変数をそれぞれのパーサが別々に導入する必要がなくなっています.
コードも割りとすっきりしますね.
結果
上記をコードを cfg
を使ってコンパイル時に切り替えながらコンパイルしてみました.
本当はきちんと繰り返し計測すべきですが,ちょっとサボっています.まぁ何度実行してもだいたい同じくらいになったので許してください.
実装方法 | コンパイル時間 |
---|---|
ジェネリック | 2.666s |
&str |
1.70s |
構造体内で定義 | 1.55s |
このような結果になりました.
つまり,先ほどの issue で述べられているコンパイル時間の短縮方法はかなり効き目があるということですね.
構造体の中に閉じ込める方法が,&str
しか受理しないようにする方法よりもはやくコンパイルできるのは意外でした… 参照を引数にとると暗黙に lifetime 変数が導入されたと記憶しているので,その関係なのかな?
構造体内で定義する方法では,&str
以外の入力ストリーム型を受けつけることを可能にしつつもコンパイル時間を短縮できるということで,積極的にこの方式でパーサを定義するべきということがわかりました.
注意点として,構造体内で別のパーサを呼ぶときには,必ず P::term
という形ではなく,P::<I>::term
という形で呼び出すようにする必要があるようです.
きちんと明示的に指定しないと,結局型推論するはめになって意味がないということのようです.
C++ でパーサコンビネータを書きました
C++ で構文解析といえば,Boost.Spirit や yacc系などが有名ですが,どうにも使うの辛かったので作りました.
2016/05/01 追記
いろいろ更新しました.肯定先読み以外はプリミティブも実装し終わっているかと思います.
ドキュメントはまだ無いのですが,すべての機能についてテストは書いてあるので,それを見てもらえればなんとか使い方もわかるかと思います.
coco::combix
がパーサコンビネータライブラリの namespace です.
Boost.Spirit は高機能かつ高性能なんですが,かなり変態的な構文で記述する必要があり(まぁ C++ なんですけど),さらにその性能や便利さ,構文のために異常なまでにテンプレートを多用しています.私は構文解析後の構文木の構築に Boost.Variant を使ってみているのですが,Boost.Spirit と Boost.Variant の両面から,ジェネリックすぎるがゆえのコンパイルエラー爆発攻撃を食らって本当に辛いです.
そこで,Haskell の parsec や Rust の combine を参考にしつつ,C++ でパーサコンビネータを書いてみました.(実際これを使ってもコンパイルエラーは割りと発狂しますが)
例
例となるコードは agatan/coco-combix-demo においてあります.
ドキュメントもないので,なんとなく雰囲気だけコードから読み取る必要があります.(例に出ていない機能もちょいちょい実装されてしまっています.)
以下にちょっと簡略版のコードを載せてみます.ありがちな電卓です.AST を作らず直接計算しています.
#include <string> #include <iostream> #include <functional> #include <coco/combix.hpp> namespace cbx = coco::combix; using stream_type = cbx::iterator_stream<std::string::const_iterator>; cbx::parser<int, stream_type> expression(); cbx::parser<int, stream_type> number() { return cbx::expected(cbx::map(cbx::many1(cbx::digit()), [](auto&& is) { int acc = 0; for (auto i : is) { acc = acc * 10 + i; } return acc; }), "integer number"); } cbx::parser<int, stream_type> factor() { return cbx::choice( number(), cbx::between(cbx::skip(cbx::token('('), cbx::spaces()), cbx::skip(cbx::token(')'), cbx::spaces()), cbx::skip(cbx::lazy_fun(expression), cbx::spaces()))); } cbx::parser<int, stream_type> term() { auto op = cbx::map( cbx::skip(cbx::choice(cbx::token('*'), cbx::token('/')), cbx::spaces()), [](auto c) -> std::function<int(int, int)> { if (c == '*') { return std::multiplies<int>(); } else { return std::divides<int>(); } }); return cbx::chainl1(cbx::skip(factor(), cbx::spaces()), op); } cbx::parser<int, stream_type> expression() { auto op = cbx::map( cbx::skip(cbx::choice(cbx::token('+'), cbx::token('-')), cbx::spaces()), [](auto c) -> std::function<int(int, int)> { if (c == '+') { return std::plus<int>(); } else { return std::minus<int>(); } }); return cbx::chainl1(cbx::skip(term(), cbx::spaces()), op); } int main() { std::string src; std::getline(std::cin, src); auto n = number(); auto stream = cbx::range_stream(src); auto const parser = expression(); if (auto res = cbx::parse(parser, stream)) { std::cout << res.unwrap() << std::endl; } else { std::cout << cbx::to_string(res.unwrap_error()) << std::endl; } }
特徴
parsec を知っている方であれば読めるはずです...
特徴としては,多くのパーサは入力ストリームの型に依存せずに作れるようになっていることです.例えば,あらゆる入力一つを受け付け消費する any
というパーサは,入力が char
のストリームであろうと int
のストリームであろうとパースを実行できるようになっています.
本来はエラーメッセージの爆発や読みづらさを防ぐために,すべてのパーサ自体にストリームの型をひも付けたかったのですが,そうすると,any
を使うたびに,any<cbx::iterator_stream<typename std::vector<int>::const_iterator>>()
とか any<cbx::iterator_stream<std::string::const_iterator>>()
とかしなくてはなりません.これは Haskell や Rust と違って C++ の型推論が限定的であるためです.(Haskell や Rust では後でその値がどう使われているかも推論の根拠として使われます.)
そこで,パーサ自体には入力ストリームの型を指定させずに,実際にパースする部分で初めて入力ストリームの型を検査することにしました.
で,cbx::parser<int, stream_type>
はパーサを type erasure を使ってラップします.普通に使っていると簡単に cbx::expected<cbx::map_parser<cbx::many1_parser<cbx::digit_parser>, (lambda at ...)>>
型とかが出てきます(cbx::expected(cbx::map(cbx::many1(cbx::digit()), [](auto&&) {...}), "integer number")
の型です)
これを関数定義のたびに書くとか発狂してしまうので,type erasure を使って型をラップし短絡します.
ただしパフォーマンスの観点から行くとおそらく型をラップするために仮想関数を使ってしまうので,インライン展開等がきかなくなると思われます.まぁ仕方ないです.
ただ,型を膨らませすぎずに適度にラップしてやると,コンパイルエラーの内容がかなり読みやすくなるはずです.なのでなんかわからんけどエラーになるっていうときは細かくパーサを分割してラップしてやると良いかもしれません.
まとめ
あまりにもドキュメントやコメント書かなすぎてひどいですが,ちょっと構文解析したいとかっていうときに便利だと思います.
Boost.Spirit と違って普通に C++ のプログラムとして書けます.(Boost.Spirit も C++ プログラムとして書けてはいるんですが,なんかあれはあれで別の言語を覚えているような気分になってしまったので...)
あと PEG のプリミティブをまだ完全に実装していないと思います.先読みや否定先読みが出来ません.(実装します…)
Rust における return文の LLVM IR 表現について
if
文が値を返すreturn
文を持つ
以上のような特徴を持つ言語はどういう感じでコンパイルされるのか知りたくて,Rust について調べてみました.
Rust では以下の様なことが出来ます.
fn f() { let x = if cond { return None; } else { 1 }; ... }
Scala とかもできると思います.cond
が真だった場合は,x
の値を返すのではなく,関数から抜けてしまうという意味です.
これを Rust ではどんな LLVM IR に落とし込んでいるのか.
return
文がない場合
fn noreturn(x: isize) -> isize { x }
最も単純な場合です.この場合,生成される LLVM IR は,
define internal i64 @_ZN4hoge8noreturn17h811bf1a871f85432E(i64) unnamed_addr #0 { entry-block: %x = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x ret i64 %1 }
となります.
名前がマングルされていますが,上記の noreturn
関数です.
やっていることは単純で,第一引数を読み込んで返すだけです.
return
に相当する文が一つのみの場合
fn onereturn(x: isize) -> isize { let y = if x == 0 { 1 } else { x }; return x; }
実際に値を返す部分が一箇所しかない場合です.途中に分岐があっても最終的に一箇所になっていれば多分同じ結果になります.
define internal i64 @_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed_addr #0 { entry-block: %x = alloca i64 %y = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-18-, label %else-block then-block-18-: ; preds = %entry-block store i64 1, i64* %y br label %join else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %y br label %join join: ; preds = %else-block, %then-block-18- %4 = load i64, i64* %x br label %clean_ast_10_ return: ; preds = %clean_ast_10_ ret i64 %4 clean_ast_10_: ; preds = %join br label %return }
return
という BasicBlock ができています.これは return
文が現れると作られるよう?です.
で,その中では単純に x
に該当する値を返しています.
最後の return x;
文を 単純に x
に置き換えてみると,
define internal i64 @_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed_addr #0 { entry-block: %x = alloca i64 %y = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-18-, label %else-block then-block-18-: ; preds = %entry-block store i64 1, i64* %y br label %join else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %y br label %join join: ; preds = %else-block, %then-block-18- %4 = load i64, i64* %x ret i64 %4 }
となります. return
ブロックが消えていますね.なので return
文があると return
ブロックが作られる、で良さそう?
複数のパスから値を返す
fn multireturn(x: isize) -> isize { let y = if x == 0 { return -1; } else { x }; y }
さて,では最初に述べた,if
の分岐内にある return
についてです.
これは,
define internal i64 @_ZN4hoge11multireturn17had379e8ce5a18f08E(i64) unnamed_addr #0 { entry-block: %sret_slot = alloca i64 %x = alloca i64 %y = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-18-, label %else-block then-block-18-: ; preds = %entry-block store i64 -1, i64* %sret_slot br label %return else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %y br label %join join: ; preds = %else-block %4 = load i64, i64* %y store i64 %4, i64* %sret_slot br label %return return: ; preds = %join, %then-block-18- %5 = load i64, i64* %sret_slot ret i64 %5 }
こうなりました.
まず,return
文があるため?,return
ブロックが作られています.
しかし今回は,パスによって返すものが違います.(値が違うという意味ではなく,同じ変数ですらないという意味です...)
よく IR を読むと,関数の頭で %sret_slot
という名前でスタック領域を確保していることがわかります.
そして,return
ブロック内では,これを読んできて返しています.
さらに,if
文の then 節にあたる,then-block-18-
というブロックでは,%sret_slot
に値を格納して return
ブロックへジャンプしています.
else 節のあとの部分 (join
ブロック) でも同様に, %sret_slot
に値を格納して return
ブロックへジャンプしています.
まとめ
というわけで,様々な Rust コードを LLVM IR に変換して見てみた結果,複数のパスから値を返す場合は,「ローカル変数として返り値を定義し,そこに返したい値を格納してから return
に goto」という形になっていることがわかりました.
(ほとんど LLVM IR を乗っけるだけになってしまった...)
ちなみに ...
if
文の返す値をそのまま返す
fn ifreturn(x: isize) -> isize { if x == 0 { 1 } else { x } }
Rust に慣れていないとちょっとわかりにくいですが,x == 0
の場合は 1 を返し,そうでない場合は x
を返す関数です.
これは,
define internal i64 @_ZN4hoge8ifreturn17hcdaab6e376d6c95cE(i64) unnamed_addr #0 { entry-block: %sret_slot = alloca i64 %x = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-15-, label %else-block then-block-15-: ; preds = %entry-block store i64 1, i64* %sret_slot br label %join else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %sret_slot br label %join join: ; preds = %else-block, %then-block-15- %4 = load i64, i64* %sret_slot ret i64 %4 }
こうなります.やっていることは上記の例たちとあまり変わりません.
しかし,return
文がないので?,return
ブロックが作られていません.が, %sret_slot
は定義されていますね...
これはどういうことなんでしょう.rustc
のコードを読むべきなのかもしれませんが,イマイチ内部処理が想像しにくいです...
普通に翻訳していったら,
let x = if x == 0 { 1 } else { x }; x
と同じ感じになる気がするので,%sret_slot
という名前が出てくる余地は無い気がするのですが...(実質同じ処理ではあります)
分岐が直接返戻値になる場合は特別扱いしているのかな?
C++ の複雑な型を整形するプログラムを作りました
テンプレートをバリバリ使っている C++ プログラムのコンパイルエラーが,死ぬほど辛かったので作りました.
型を綺麗に出力するだけです.
C++の型版 jq
みたいなやつありそうだけど無いのかな?
たとえば,
boost::spirit::x3::raw_directive<boost::spirit::x3::lexeme_directive<boost::spirit::x3::sequence<boost::spirit::x3::alternative<boost::spirit::x3::char_class<boost::spirit::char_encoding::standard, boost::spirit::x3::alpha_tag>, boost::spirit::x3::literal_char<boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type> >, boost::spirit::x3::kleene<boost::spirit::x3::alternative<boost::spirit::x3::char_class<boost::spirit::char_encoding::standard, boost::spirit::x3::alnum_tag>, boost::spirit::x3::literal_char<boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type> > > > > >::parse<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::basic_string<char> >, boost::spirit::x3::context<boost::spirit::x3::error_handler_tag, const std::reference_wrapper<boost::spirit::x3::error_handler<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::basic_string<char> > > >, boost::spirit::x3::context<boost::spirit::x3::skipper_tag, const boost::spirit::x3::char_class<boost::spirit::char_encoding::ascii, boost::spirit::x3::space_tag>, boost::spirit::x3::unused_type> >, std::__cxx11::basic_string<char>, char>
こんなエラーがよく有りますよね.
これを tf
の標準入力に流しこむと,
boost::spirit::x3::raw_directive< boost::spirit::x3::lexeme_directive< boost::spirit::x3::sequence< boost::spirit::x3::alternative< boost::spirit::x3::char_class< boost::spirit::char_encoding::standard, boost::spirit::x3::alpha_tag >, boost::spirit::x3::literal_char< boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type > >, boost::spirit::x3::kleene< boost::spirit::x3::alternative< boost::spirit::x3::char_class< boost::spirit::char_encoding::standard, boost::spirit::x3::alnum_tag >, boost::spirit::x3::literal_char< boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type > > > > > >::parse< __gnu_cxx::__normal_iterator< constchar*, std::__cxx11::basic_string< char > >, boost::spirit::x3::context< boost::spirit::x3::error_handler_tag, conststd::reference_wrapper< boost::spirit::x3::error_handler< __gnu_cxx::__normal_iterator< constchar*, std::__cxx11::basic_string< char > > > >, boost::spirit::x3::context< boost::spirit::x3::skipper_tag, constboost::spirit::x3::char_class< boost::spirit::char_encoding::ascii, boost::spirit::x3::space_tag >, boost::spirit::x3::unused_type > >, std::__cxx11::basic_string< char >, char >
こうなります.
単純に <
, >
, ,
を見てインデントを調整しながら出力しているだけです.
空白はスキップします.
構文解析とかは全くしていないので,コンパイルエラーをそのまま流し込んでも悲惨な事になります.
あと今気がついたのですが,
修正しましたconst hoge
が consthoge
になっていますね.
boost::spirit::x3::raw_directive< boost::spirit::x3::lexeme_directive< boost::spirit::x3::sequence< boost::spirit::x3::alternative< boost::spirit::x3::char_class< boost::spirit::char_encoding::standard, boost::spirit::x3::alpha_tag >, boost::spirit::x3::literal_char< boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type > >, boost::spirit::x3::kleene< boost::spirit::x3::alternative< boost::spirit::x3::char_class< boost::spirit::char_encoding::standard, boost::spirit::x3::alnum_tag >, boost::spirit::x3::literal_char< boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type > > > > > >::parse< __gnu_cxx::__normal_iterator< const char *, std::__cxx11::basic_string< char > >, boost::spirit::x3::context< boost::spirit::x3::error_handler_tag, const std::reference_wrapper< boost::spirit::x3::error_handler< __gnu_cxx::__normal_iterator< const char *, std::__cxx11::basic_string< char > > > >, boost::spirit::x3::context< boost::spirit::x3::skipper_tag, const boost::spirit::x3::char_class< boost::spirit::char_encoding::ascii, boost::spirit::x3::space_tag >, boost::spirit::x3::unused_type > >, std::__cxx11::basic_string< char >, char >
Type Erasure による Visitor パターンの実装
プログラミングしていて,木構造をうまく扱いたいという状況は結構良くあると思います.
代数的データ型とパターンマッチを持つ言語であればとても美しく完結に表現できる木構造ですが,オブジェクト指向言語でやろうと思うと結構たいへんです.
典型的には Visitor パターンというやつを用います.デザインパターン - Visitor パターン再考 - Qiitaが非常にわかりやすく,理解の助けになりました.ありがとうございます.
一方,C++ の有名なライブラリ,Boost には Boost.Variant というモジュールがあり,これまたとても美しく Visitor っぽいことが出来ます.
#include <boost/variant.hpp> #include <string> #include <iostream> using sample = boost::variant<int, double, std::string>; sample s1 = 1; sample s2 = 2.0; sample s3 = "sample3"; boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s1); // => 1 boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s2); // => 2.0 boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s3); // => sample3
しかし,Boost.Variant は非常に高機能ですが,テンプレートをガンガン使っていたりするので,コンパイルコストが大きいという問題があります.
そこで,Type Erasure を使って visitor パターンをうまく表せれば,コンパイルコストを下げられるのでは?というお話です.
Type Erasure は「型消去」とかでググると色々解説してくださっている記事などが出てくると思います.(ありがとうございます)
この話,私が考えたわけではなくて,どこかのソースコードで見たようなきがするんですが,当時は Type Erasure とか意味不明だったのでスルーしていました.
今ならなんとなくやりたいことは出来るような気がするので(&ちょうど必要になったので)記事にしてみていますが,もしオリジナルっぽいものや同じようなことを提案しているソースコード・記事を見かけた方は是非ご連絡いただけると嬉しいです.
1st step
Visitor
今回表現したいデータ構造をまず定めます.簡単のために,足し算・掛け算・整数定数の 3 種類のノードを持つ木構造を考えます.
(1 + 2) * 3
なら, mul( add(1, 2), 3 )
みたいな感じです.
この構造を visit する Visitor クラスから先に考えます.
Visitor クラスは,visit
というメンバ関数をもつ型の値を,型を消去して保持させます.
class visitor { private: class visitor_base_holder { public: virtual void visit(add &) = 0; virtual void visit(mul &) = 0; virtual void visit(constant &) = 0; virtual ~visitor_base_holder() = default; }; template <typename V> class visitor_holder : public visitor_base_holder { private: V &v; public: visitor_holder(V &v) : v(v) {} void visit(add &a) override { v(a); } void visit(mul &a) override { v(a); } void visit(constant &a) override { v(a); } virtual ~visitor_holder() = default; }; std::unique_ptr<visitor_base_holder> holder; public: template <typename V> visitor(V &v) : holder(std::make_unique<visitor_holder<V>>(v)) {} template <typename Visitable> void visit(Visitable &v) { holder->visit(v); } };
今回は const
修飾についてすべて無視しています.( const
を考慮するならば,各 visit
について,visitor の const
性と node の const
性を考える必要があります.つまり 4 種類のメンバ関数を定義しなければなりません.)
visit した対象となるそれぞれのデータについてオーバーロードする形で visit
を定義しています.
visitor
のコンストラクタに,operator()(add&)
, operator()(mul&)
, operator()(constant&)
を全て持つオブジェクト(C++14 のジェネリックラムダでもOK)を渡すことで,型消去された visitor が出来上がります.
visitor
のコンストラクタにどんな型の値を渡しても,出来上がる visitor
にはその型情報は含まれないので,様々な visitor を統一して扱う( vector
に突っ込むとか)事ができるようになります.
Node
次にノードの方について考えます. 通常,Visitor パターンでは, visit される側のクラスに accept
を実装します.
visit される側のデータを統一的に扱う( vector
に突っ込むとか)ためには,継承やインターフェースを用いるのが普通です.
C++ では,Visitor 側に使った Type Erasure のテクニックが使えます.
std::vector<node>
などのように,統一的にノードを扱いつつも,visit される際には,visit(add&)
や visit(mul&)
のような適切なオーバーロード関数を呼び出すようにしてやればオッケーです.
class node { private: class node_base_holder { public: virtual void accept(visitor &v) = 0; virtual ~node_base_holder() = default; }; template <typename T> class node_holder : public node_base_holder { public: node_holder(T const &n) : node(n) {} node_holder(T &&n) : node(n) {} void accept(visitor &v) override { v.visit(node); } ~node_holder() = default; private: T node; }; std::shared_ptr<node_base_holder> holder; public: template <typename Node> node(Node const &n) : holder(std::make_shared<node_holder<Node>>(n)) {} template <typename Node> node(Node &&n) : holder(std::make_shared<node_holder<Node>>(n)) {} void accept(visitor &v) { holder->accept(v); } template <typename Visitor> void accept(Visitor &v) { visitor visit(v); holder->accept(visit); } };
これ結構わかりにくと思うのですが,自分でもコンパイラに怒られながら書いたのでいまいちよく分かってません.
先ほどの visitor
の場合と異なり,node
には特別満たすべきインターフェースは有りません.
Type Erasure を使う理由は,適切な visit
関数へのディスパッチのためです.
使う
visitor
と node
が出来たので,使ってみます.
その前にデータ構造を定義しておきます.
struct constant { int value; }; struct add { node lhs; node rhs; }; struct mul { node lhs; node rhs; };
add
や mul
のフィールドに,node
が使用されている点が大事です.
add.lhs
や mul.rhs
には,constant
が来るか add
が来るか mul
が来るか分かりません.
そこで,visit 可能な型なら何でもOKという意味で,node
型の値をフィールドとします.
node n = mul{add{constant{1}, constant{2}}, constant{3}};
これで,(1 + 2) * 3
が表現できています.
add
や constant
から node
へと暗黙変換が行われていることに注意してください.
次に visitor を定義します.これは,operator()
をオーバーロードした関数オブジェクトです.
式を出力する printer
と 式を計算する calculator
を定義します.
struct printer { void operator()(add &a) { std::cout << "("; a.lhs.accept(*this); std::cout << ")"; std::cout << "+"; std::cout << "("; a.rhs.accept(*this); std::cout << ")"; } void operator()(mul &a) { std::cout << "("; a.lhs.accept(*this); std::cout << ")"; std::cout << "*"; std::cout << "("; a.rhs.accept(*this); std::cout << ")"; } void operator()(constant &c) { std::cout << c.value; } }; struct calculator { int result; void operator()(add &a) { calculator l, r; a.lhs.accept(l); a.rhs.accept(r); result = l.result + r.result; } void operator()(mul &m) { calculator l, r; m.lhs.accept(l); m.rhs.accept(r); result = l.result * r.result; } void operator()(constant &c) { result = c.value; } };
こんな感じです.
visit
や accept
を void
を返す関数として定義したので,calculator
は自前のフィールドに結果を保持する必要があります.
(あとで改善します)
使い方は
node n = mul{add{constant{1}, constant{2}}, constant{3}}; printer p; n.accept(p); calculator calc; n.accept(calc); std::cout << std::endl; std::cout << calc.result << std::endl; return 0;
です.
まとめ
この方法の利点としては,データの定義そのものに Visitor パターンのためのノイズが入らないことが挙げられます.
普通の Visitor パターンでは継承必須ですし.
const
つけてないせいで一時オブジェクトが使えないので printer p;
という行が必要になってしまっています.これはconst
をがんばってつけるだけなのでまぁ問題有りません.
一方,calculator
の方はダサいですね.値を返す visitor も定義できるようにしたい.
visitor
の定義もツライです.const
を考慮した場合,同じような内容のメンバ関数を 4 回ずつ書く必要がある.
このへんの問題点は解決可能な気がするので出来たら後で記事にするつもりです.
難しすぎて普通の visitor パターンで良くね?感出てきた
#include をソートするVimプラグインを作りました
Haskellでimport文をソートするプラグイン vim-haskell-sort-import を作りました - プログラムモグモグという記事を拝見して,コードを見たらすごくわかりやすくて,これの C/C++ 版がほしいと思い,書いてみました.
vim script はほとんど書いたことがないんですが,やっぱりエディタ拡張用のスクリプトなので,普通の言語と違う部分は多いですね… でもその分エディタという UI が既に用意されている状態なので,なんというか書いていて楽しかったです.さくっと書けますし.(先ほどのコードを参考にしているというのもありますが)
使い方
NeoBundle
や vim-plug
のようなプラグインマネージャを使うなどして runtime path に突っ込んでください.
提供する機能は SortInclude
コマンドのみです.
こんな感じの動作をします.
#include
は ""
を使う場合と <>
を使う場合があり,それぞれファイルパスの探索場所が異なるので,それぞれ別のグループとしてソートするようにしました.
#include <iostream> #include "a.h" #include "z.h"
が
#include "a.h" #include <iostream> #include "z.h"
にソートされたら気持ち悪いと思うので.
あとは参考にさせていただいたプラグインと同様,空行を挟むなどブロック化されている場合は,ブロック内でソートします.
#include
をソートするとか既にありふれてそうですが,はじめての vim プラグインということで.
せっかくなのでドキュメントなども vim の help フォーマットにしたがって書いてみました.
コンパイラ内部の AST 表現について
コンパイラは大体,ソースコードを構文解析し,AST を作り,意味解析,コード生成という流れで実装されると思います.
さて,AST は単純に書くと
type expr = | Int of int | Add of expr * expr | Apply of expr * expr list | ...
みたいな感じに書けると思います.
これで確かにソースコードの syntax 上の余計な飾りをとっぱらった木構造になっているので抽象構文木としては十分機能します. 一方,既存のコンパイラを見ると,構文解析の後,型検査などの意味解析時にプログラムの不正を見つけた場合,きちんとソース上の位置を合わせて通知してくれます. このためには,AST に位置情報を含める必要があります.
また,型推論の前後で,木構造としては同じ構造だけれども,型情報の持ち方に違いがあるという状況もあります.
(* 型推論前 *) type expr = | Int of int | Add of expr * expr | Apply of expr * expr list (* 型推論後 *) type texpr = | Typed_int of int | Typed_add of texpr * texpr | Typed_apply of texpr * texpr list
このように AST の表現は,木構造としては同じだが付随する情報だけが異なるという場合があります.
いろいろな言語のコンパイラの AST 表現を調査してみたところ,Elm コンパイラの方式が良かったのでまとめておきたいと思います.
type Expr annotation definition variable tipe = A.Annotated annotation (Expr' annotation definition variable tipe) data Expr' ann def var typ = Literal Literal.Literal | Var var | Range (Expr ann def var typ) (Expr ann def var typ) | ExplicitList [Expr ann def var typ] | Binop var (Expr ann def var typ) (Expr ann def var typ) | Lambda (Pattern.Pattern ann var) (Expr ann def var typ) | App (Expr ann def var typ) (Expr ann def var typ) | If [(Expr ann def var typ, Expr ann def var typ)] (Expr ann def var typ) | Let [def] (Expr ann def var typ) | Case (Expr ann def var typ) [(Pattern.Pattern ann var, Expr ann def var typ)] | Data String [Expr ann def var typ] | Access (Expr ann def var typ) String | Update (Expr ann def var typ) [(String, Expr ann def var typ)] | Record [(String, Expr ann def var typ)] -- for type checking and code gen only | Port (PortImpl (Expr ann def var typ) typ) | GLShader String String Literal.GLShaderTipe
Elm コンパイラは Haskell で実装されています.
Expr
が型引数として,annotation
などを持っています.(definition
, tipe
についてはいまいちなんのための抽象化か理解していません...)
annotation
は,AST に付随する情報です.A.Annotated
という型が,核となる情報に,情報を annotate する役割を担います.
data Annotated annotation a = A annotation a
そして,AST の核となる構造自体は Expr'
が持ちます.
こうすることで,annotation
の内容を変えるだけで,木構造を何度も書き直す必要なく,コンパイラの各ステップに適した AST 表現を作る事ができます.
ちなみに variable
はどうやら変数などの名前を表現する型を表しているようです.(始めは単なる String
)