読者です 読者をやめる 読者になる 読者になる

右上➚

プログラミングに関するメモをのこしていきます

C++ でパーサコンビネータを書きました

C++構文解析といえば,Boost.Spirit や yacc系などが有名ですが,どうにも使うの辛かったので作りました.

2016/05/01 追記 

いろいろ更新しました.肯定先読み以外はプリミティブも実装し終わっているかと思います.
ドキュメントはまだ無いのですが,すべての機能についてテストは書いてあるので,それを見てもらえればなんとか使い方もわかるかと思います.

agatan/coco

coco::combix がパーサコンビネータライブラリの namespace です.

Boost.Spirit は高機能かつ高性能なんですが,かなり変態的な構文で記述する必要があり(まぁ C++ なんですけど),さらにその性能や便利さ,構文のために異常なまでにテンプレートを多用しています.私は構文解析後の構文木の構築に Boost.Variant を使ってみているのですが,Boost.Spirit と Boost.Variant の両面から,ジェネリックすぎるがゆえのコンパイルエラー爆発攻撃を食らって本当に辛いです.

そこで,Haskellparsec や 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 みたいなやつありそうだけど無いのかな?

agatan/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<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 hogeconsthoge になっていますね. 修正しました

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 関数へのディスパッチのためです.

使う

visitornode が出来たので,使ってみます.
その前にデータ構造を定義しておきます.

struct constant {
  int value;
};

struct add {
  node lhs;
  node rhs;
};

struct mul {
  node lhs;
  node rhs;
};

addmul のフィールドに,node が使用されている点が大事です.
add.lhsmul.rhs には,constant が来るか add が来るか mul が来るか分かりません.
そこで,visit 可能な型なら何でもOKという意味で,node 型の値をフィールドとします.

node n = mul{add{constant{1}, constant{2}}, constant{3}};

これで,(1 + 2) * 3 が表現できています. addconstant から 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; }
};

こんな感じです.
visitacceptvoid を返す関数として定義したので,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 が既に用意されている状態なので,なんというか書いていて楽しかったです.さくっと書けますし.(先ほどのコードを参考にしているというのもありますが)

使い方

NeoBundlevim-plug のようなプラグインマネージャを使うなどして runtime path に突っ込んでください. 提供する機能は SortInclude コマンドのみです.

f:id:agtn:20160124191335g:plain

こんな感じの動作をします.

#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)

Boost.Spirit.X3 で簡易電卓を実装 1

agtn.hatenablog.com agtn.hatenablog.com

引き続き,Boost.Spirit.X3 です.
今回は,前回までの知識をつかって,簡易電卓を実装してみます.

仕様

今回定義する電卓は,

  • +
  • -
  • *
  • /

の 4 つの演算と単項の - をサポートします.
また,整数型のみを扱うものとします.
(, ) でくくることで,演算子の結合優先順位を書き換えられ,*/+- より優先されるとします.

要するに整数の四則演算のみをサポートする電卓です.

このような電卓を実装するサンプルは Boost.Spirit.X3 以外のライブラリ/ツールでも大量に出てくると思います.
今回は,構文解析そのものというよりは Boost.Spirit.X3 の使い方についてメモしたいので,構文解析そのものの話はぐぐってみてください.

パーサの骨格

演算子の結合規則をサポートするために,primary(定数と () で囲まれた式), neg_expr(単項 -), mul_expr(*, /), add_expr(+, -), expression というパーサをそれぞれ定義します.
先頭から順に結合強度が強くなっています.(expression が最弱, primary が最強)

primary() で囲まれた式,つまり "(" > expression > ")" を受け付ける必要があり,また,primary 自体も expression の一部です.
したがって,この規則を定義するためには,再帰的なパーサを記述する必要があります.

X3再帰的なパーサを記述する方法は前回の記事にまとめました.

  struct primary;
  struct neg_expr;
  struct mul_expr;
  struct add_expr;
  struct expression;

  x3::rule<primary, int> const primary;
  x3::rule<neg_expr, int> const neg_expr;
  x3::rule<mul_expr, int> const mul_expr;
  x3::rule<add_expr, int> const add_expr;
  x3::rule<expression, int> const expression;

それぞれのパーサは attribute として整数型を持ちます.ここに演算結果が格納されることになります.
struct primary などは,今は前方宣言のみで十分です.on_error などを実装したくなった時に定義します.

primary

まずは primary を定義します.
primary は整数定数か, () で囲まれた expression を受理します.

auto const primary_def =
    x3::int_
  | "(" > expression > ")"
  ;

attribute を考慮しなければこんな感じでしょうか.expression は既に宣言されているので使用可能です.(expression の実装がこの時点で見えていなくても使用できます.)

単純に attribute を結果として返すセマンティックアクションはこの後もよく出てくるので,ヘルパとして定義しておきます.

namespace detail {

  decltype(auto) assign()
  {
    using x3::_attr;
    using x3::_val;
    return [](auto&& ctx) { _val(ctx) = _attr(ctx); };
  }

} // namespace detail

assign は attribute を結果に代入する関数オブジェクトを返します.
関数にする必要が特にありませんが,この後出てくるヘルパと見た目を合わせたいので関数にしました.

これを使うと,

auto primary_def =
    x3::int_[detail::assign()]
  | ("(" > expression > ")")[detail::assign()]
  ;

こんな感じで primary が定義できます.

単項マイナス

次に neg_expr を定義します. セマンティックアクションを考えなければ,

auto const neg_expr_def =
    primary
  | "-" > primary
  ;

となります.
"-" > primary のセマンティックアクションとしては,attribute を符号反転して結果に格納するというアクションが求められます.
ここはちょっと汎用的に,attribute に関数オブジェクトを適用して結果に格納するアクションを返すような関数を定義して解決してみます.

namespace detail {
  template <typename F>
  decltype(auto) assign_f(F&& func)
  {
    return [func](auto&& ctx) { _val(ctx) = func(_attr(ctx)); };
  }
} // namespace detail

assign_fassign と異なり,関数オブジェクトを1つ引数に取ります.
そして,その関数オブジェクトを _attr(ctx) に適用し結果に格納します.

これを使って,neg_expr

auto const neg_expr_def =
    primary[detail::assign()]
  | ("-" > primary)[detail::assign(std::negate<int>{})]
  ;

となります.std::negate<functional> で定義された型で,ここでは int 型の値を符号反転する関数オブジェクトとして使用しています.

乗除

次に結合強度が強いのは */ です.
ちょっとわかりにくいですが,セマンティックアクションを無視すれば,mul_expr

auto const mul_expr_def =
    neg_expr
    >> *(
        ("*" >> neg_expr)
      | ("/" >> neg_expr)
    )
  ;

と定義できます.mul_expr1(1 + 2), -1 の後に,* 1 とか / -3 とか * (1 - 2) とかが 0 回以上現れるような式です.
1 * -2 はちょっと気持ち悪い気もしますが… 今気がついたので許してください.

セマンティックアクションとしては,("*" >> neg_expr) が現れる度に,_val(ctx)_val(ctx) * _attr(ctx) に更新すれば良いです.
始めの neg_expr の結果を _val(ctx) に格納すれば,_val(ctx) は常に現在の計算結果を表すことになります.("*" >> neg_expr) は現在の計算結果に,今処理した式(* の後に続く式のこと) を処理した結果をかければ良いということです.

というわけで分かりにくいとは思いますが,ほしいアクションは,

[](auto&& ctx) { _val(ctx) = _val(ctx) * _attr(ctx); }

です.

さて,では / の場合を考えます.
/ の場合であってもほとんどは * と同じであることがわかります.
ほしいアクションは

[](auto&& ctx) { _val(ctx) = _val(ctx) / _attr(ctx); }

であり,*/ の違いしか有りません.

そこでこれも関数にまとめてしまいます.

namespace detail {

  template <typename Op>
  decltype(auto) calc_op(Op&& op)
  {
    return [op](auto&& ctx) { _val(ctx) = op(_val(ctx), _attr(ctx)); };
  }

} // namespace detail

こんな関数を定義して,

auto const mul_expr_def =
    neg_expr[detail::assign()]
    >> *(
        ("*" >> neg_expr)[detail::calc_op(std::multiplies<int>{})]
      | ("/" >> neg_expr)[detail::calc_op(std::divides<int>{})]
    )
  ;

と使います.
calc_op は関数オブジェクトを引数に取り,_val(ctx)_attr(ctx) に適用した結果を格納するアクションを返します.

add_exprmul_expr とほぼおなじなので詳細はスキップします.

expression

最後に expression です.これは単純に add_expr と一致します.
命名のわかりやすさと,今後拡張していく際に便利そうということで分けてあるだけです.

auto const expression_def =
    add_expr[detail::assign()]
  ;

確認

コード全体を掲載します.

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>
#include <functional>

namespace x3 = boost::spirit::x3;

namespace grammar {

  namespace detail {

    decltype(auto) assign()
    {
      using x3::_attr;
      using x3::_val;
      return [](auto&& ctx) { _val(ctx) = _attr(ctx); };
    }

    template <typename F>
    decltype(auto) assign_f(F&& func)
    {
      return [func](auto&& ctx) { _val(ctx) = func(_attr(ctx)); };
    }

    template <typename Op>
    decltype(auto) calc_op(Op&& op)
    {
      return [op](auto&& ctx) { x3::_val(ctx) = op(x3::_val(ctx), x3::_attr(ctx)); };
    }

  } // namespace detail

  struct primary;
  struct neg_expr;
  struct mul_expr;
  struct add_expr;
  struct expression;

  x3::rule<primary, int> const primary;
  x3::rule<neg_expr, int> const neg_expr;
  x3::rule<mul_expr, int> const mul_expr;
  x3::rule<add_expr, int> const add_expr;
  x3::rule<expression, int> const expression;

  auto const primary_def =
      x3::int_[detail::assign()]
    | ("(" > expression > ")")[detail::assign()]
    ;

  auto const neg_expr_def =
      primary[detail::assign()]
    | ("-" > primary)[detail::assign_f(std::negate<int>{})]
    ;

  auto const mul_expr_def =
      neg_expr[detail::assign()]
      >> *(
          ("*" >> neg_expr)[detail::calc_op(std::multiplies<int>{})]
        | ("/" >> neg_expr)[detail::calc_op(std::divides<int>{})]
      )
    ;

  auto const add_expr_def =
      mul_expr[detail::assign()]
      >> *(
          ("+" > mul_expr)[detail::calc_op(std::plus<int>{})]
        | ("-" > mul_expr)[detail::calc_op(std::minus<int>{})]
      )
    ;

  auto const expression_def =
      add_expr[detail::assign()]
    ;

  BOOST_SPIRIT_DEFINE(
      primary,
      neg_expr,
      mul_expr,
      add_expr,
      expression
      );

} // namespace grammar
using grammar::expression;

int main()
{
  std::string str;
  std::getline(std::cin, str);

  auto first(std::cbegin(str));
  auto const last(std::cend(str));

  int result;
  bool success = x3::phrase_parse(first, last, expression, x3::ascii::space, result);

  if (!success || first != last) {
    std::cerr << "Parse failed." << std::endl;
    return 1;
  }

  std::cout << "Parsed: " << result << std::endl;
  return 0;
}

実行してみます.

$ clang++ -std=c++14 main.cpp
$ ./a.out
1 + 2 * 3
Parsed: 7
$ ./a.out
(1 + 2) * 3
Parsed: 9

演算子の優先順位が正しく解決できていることが確認出来ます.

まとめ

今回は,セマンティックアクションで計算自体を行ってしまいましたが,普通は抽象構文木(AST) に変換するためにセマンティックアクションを使うのが正道だと思います.
X3 は AST のための色々を提供してくれていますが,自前で作った AST でもちょっと苦労はするかもしれませんが変換できるはずなので,時間があれば,自前 AST に変換してから実行する電卓も作ってみたいと思います.

また,AST に変換して計算する場合,AST に位置情報を付与することで,エラーレポートが便利になったりするはずです( 0 除算のエラーを通知する際,どの部分でのエラーなのかを吐いてくれればうれしいですよね).
パース失敗時にもどこで失敗したのかをレポートしてくれたほうが便利です.
X3on_error, on_success を使ってこれらを実装してみようと考えています.

今回のコードでは decltype(auto) など,C++14 の機能を使っています.X3C++14 前提のライブラリなので,迷いなくこういった機能を使用できて幸せデスね.