
「値」と「参照」という言葉があります。
このへんの言葉について、今の理解をまとめておこうと思います。
言葉の定義や理解が誤っている部分があればご指摘ください。

まず、前提として以下では、「値」ベースの言語として C, C++, Rust などを、「参照」ベースの言語として Java, C#, Ruby などを想定しています。
（もちろん言語によってはハイブリッドなものもあります: Crystal, Go, D, ...）

## そもそも「値」「参照」とは

「値」は「実体」、「参照」は「実体へのポインタ」です。

`int` の配列みたいなものを考えてみます。
`[1, 2, 3]` をメモリ上にどう表現できるでしょうか。

配列ですから、単純にメモリ上のどこかに以下のような領域を作ればよさそうです。

```
+---+
| 1 |
+---+
| 2 |
+---+
| 3 |
+---+
```

これが「値」であり配列の実体です。
そして、実体の配置されたメモリ領域へのポインタが「参照」です。

## スタック上の表現

さて、プログラム上ではこの配列のようなオブジェクトを、ローカル変数としてスタック上で表現したり、関数に引数として渡したりします。
では、スタック上での配列の表現はどうなっているのか考えてみます。

ここで、「値」と「参照」という言葉が重要になります。

「値」ベースな言語では、スタック上に

```
+---+
| 1 |
+---+
| 2 |
+---+
| 3 |
+---+
```

をそのままべたっと配置します。

一方で、「参照」ベースな言語では、ヒープ上に

```
+---+
| 1 |
+---+
| 2 |
+---+
| 3 |
+---+
```

を配置し、スタック上では実体へのポインタという表現になります。
（必ずしもヒープに置くとは限らない？処理系や最適化によってはスタックに置くこともありえる？とにかくローカル変数などの表現としては実体へのポインタという形をとるということ）

## 値渡し・参照渡し

値渡しとか参照渡しという言葉があります。

以下に擬似コードを一つ書いてみます。（C 風に書いていますが C ではないと思ってください）

```
void inc\_age(Person p) {
  p.age++;
}

Person john = Person { "john", 20 };
inc\_age(john);
print(john.age); // => ??

```

このコード、処理系が「値」ベースか「参照」ベースかで結果が異なります。

#### 「値」ベースの場合

値ベースの言語の場合、`inc_age` の引数に `john` を渡した時には、`inc_age` 内のローカル変数（引数） `p` のために、`john` のコピーが作られます。

`inc_age` 内で `p.age++` としていますが、`p` は `john` のコピーであって `john` ではありませんから、`inc_age` から戻ってきて `john.age` を参照しても 20 のまま変化が無いはずです。

したがって結果として `20` が出力されます。

#### 「参照」ベースの場合

参照ベースの言語の場合、`john` 変数のメモリ上での表現は、ヒープに置かれた `Person { "john", 20 }` というオブジェクトへのポインタになります。

`inc_age` にこれを引数として渡すと、ポインタの値がコピーされますから、`p` と `john` は同じオブジェクトを参照しているポインタになります。

`p.age++` とすると `p` が参照するオブジェクトが変更されます。これは `john` が参照するオブジェクトと同一ですから、`john.age` も 21 に変化します。

したがって結果として `21` が出力されます。

### C の場合

C の場合、ポインタが直接表現できますから、参照渡しの挙動を模倣することができます。

```
void inc\_age(Person *p) {
    p->age++;
}

Person john = Person { "john", 20 };
inc\_age(&john);
print(john.age); // => 21

```

`p` が `Person*` 型であること、そして `inc_age` に `john` のアドレスを渡していることに注目してください。
この場合、`p` は `john` を参照するポインタですから、結果は `21` になります。

### C++ の場合

C++ の場合、言語機能として「参照渡し」という機能があります。

```
void inc\_age(Person& p) {
    p.age++;
}

Person john = Person { "john", 20 };
inc\_age(john);
print(john.age); // => 21

```

`p` が `Person&` 型であること、`inc_age` には `john` をそのまま渡しているように見えることに注目してください。
これは C++ の提供する機能で、コンパイルすると、`Person&` は実質 `Person*` と同じ表現になります。
`p->age` ではなく `p.age` と書けること、`&john` ではなく `john` のままで参照渡しが実現できるようになっています。
単純なポインタを使っても同じことが出来ますが、ポインタと違って `nullptr` になることがないという特徴があります。

## 参照のハマりやすい点

個人的に参照ベースの言語でハマりやすいなと感じるのは以下のようなコードです。

```
void some\_function(Person p) {
    p.age++;
    p = new Person("bob", 30);
}

Person p = new Person("john", 20);
some\_function(p);
println(p.name); // => john
println(p.age); // => 21

```

`p.age++` の部分は呼び出し元のオブジェクトに反映されるのに、`p = new Person(...)` の部分はなんで反映されないの！ってなります。（なりません？）
本質的にポインタの値渡しにすぎないんだということを理解していればまぁ納得なのですが...

（ちなみに C++ や D の参照渡しだと `p = new Person(...)` 的なコードも呼び出し元に反映されます。）

## 値のハマりやすい点

ハマりやすいというか、気がつかないままパフォーマンスが悪くなりやすいのが値ベースの言語の弱点でしょう。

```
void print\_object(HugeObject obj) {
   printf("%s\n", obj.name);
}
HugeObject obj = ...;
print\_object(obj);

```

このようなコードを書くと、ただ名前を表示するだけの関数が激重になる可能性があります。
値ベースの言語では、引数として値を渡すとまるっとそのコピーをつくりますから、不要にもかかわらず巨大な値のコピーを作ってしまいます。

## まとめ

「ムーブセマンティクス」とか「immutable と参照」とかについてまとめようと思ったのですが、前提として「値」「参照」についてまとめていないと書きにくいなと思ったのでまとめておきました。

内部表現を知ることでハマりやすい点の回避にもつながると思うので、この辺はきちんと理解しておきたいです。

---

---


値と参照について


再帰的にパスをたどりながらパターンにマッチする行を検索する grep 系のツールを作っています。

[agatan/crepe](https://github.com/agatan/crepe)

有名どころとしては、[ack](http://beyondgrep.com/) とか [ggreer/the_silver_searcher](https://github.com/ggreer/the_silver_searcher)(ag) とか [monochromegane/the_platinum_searcher](https://github.com/monochromegane/the_platinum_searcher) とか [tkengo/highway](https://github.com/tkengo/highway) なんかがあります。群雄割拠ですね。

これらの有名ツール達はそれぞれ特徴があって(速さとか出力形式とかエンコード対応とか)便利に使わせていただいております。

今回 `crepe` を作ろうと思った理由は、なんとなく C++ でちゃんとスレッド立てて並行処理みたいなコードを書いてみたくなったからです。

速度等も測っていないのでどこまで意味があるのか怪しいのですが、とりあえず現状 3 つの仕事を並列に動かしています。

一つ目は出力を担当するスレッドで、マッチ結果を受け取って出力するだけです。

二つ目はマッチを担当するスレッドで、ファイル名と `FILE*` を受け取ってマッチ結果を生成し出力担当スレッドに渡します。

三つ目はパスを walk するスレッドで、ディレクトリを掘りながらファイルを開いてマッチスレッドに送ります。

現状はまだ部分一致の matcher しか実装していないので正規表現や fuzzy マッチは未実装です。

標準入力かパスから部分一致する行を探してきて出力します。

出力形式は `ag` に近い形式で、ファイルごとにグループ分けして行番号とともに出力します（オプションでこの辺の挙動はいじれるようにはなっています）

バイナリファイルっぽいファイルはスキップするようになっています。

## やりたいこと

最終目標として `crepe` は [peco](https://github.com/peco/peco) のような interactive な検索を実装してみたいなと思っています。

`ag` と `peco` の組み合わせで云々みたいなユースケースが割りとあるなぁと思ったので。

ただこれメモリ使用量とか速度上の制約からまともに働くのかはよくわかっていません。

単純に考えると、ユーザが一文字入力するたびにファイルの read からやり直す必要があるので...

入力ファイルが多すぎた場合にどこまでキャッシュするのかとかその辺を相当うまくやらないと死ぬのでは？という気がします。

短期的な目標としては

- .gitignore 対応 (意外とめっちゃ面倒で苦しんでいます)
- fuzzy マッチ
- 正規表現マッチ

あたりから順にやっていきたいなと思っています。とりあえずこっちからやろうかなと思います。

というわけで気合を入れる意味も込めて記事にしました。プルリクやフィードバック大歓迎なのでぜひよろしくお願いします。

---

COMMENT:
AUTHOR: smaranrebub
EMAIL: ruysqucp@gmail.com
URL: http://cialisvipsale.com
IP: 200.26.168.127
DATE: 03/24/2018 15:30:29

Very good info, Thanks!
walgreens price for cialis [buy brand cialis cheap](http://cialisvipsale.com)
prices on cialis 10 mg [http://cialisvipsale.com](http://cialisvipsale.com)
acheter du cialis a geneve [effetti del cialis](http://cialisvipsale.com)
prices for cialis 50mg

---

---


再帰的 grep ツール crepe を作っています


Haskell や Rust など多くの強力な型システムを持つプログラミング言語は、`Either` とか `Result` といった「失敗するかもしれない」計算の値を示す型を持っています。

現在の C++ の標準ライブラリにはこのような型はありませんので、それを自作してみようというわけです。

ちなみに現在策定中の C++17 には `std::optional` が入ることが決定しているようです。これは、`result` と同様に失敗するかもしれな値を示しますが、失敗した原因がなんなのかを通知する仕組みを持っていません。

## そもそもどういう型か

Rust の `Result` 型を例にみてみます。

```
enum Result<V, E> {
  Ok(V),
  Err(E),
}

```

Rust における `Result` 型はだいたいこんな感じで定義されています。

`Result` は型引数を２つとります。`V` が成功時の値で、`E` が失敗時のエラー情報です。
例えば、`fn parse_int(s: &str) -> Result<isize, String>;` は、文字列を受け取り、それが整数としてパース出来れば `isize` に変換し、`Ok(isize)` として返します。
もし整数としてパース出来ないなどのエラーがあれば、それを `String` で表現し、`Err(String)` で返します。

本質的にはこれが全てです。ここに、`Result` から中身を取り出す(`Err` なら `panic` する)関数などを定義してあげれば便利にエラー状態を表現できます。

(Rust の `try` マクロはとても便利ですよね)

## まずはベースとなる result を作る

まずはベースとなる `result` 型を作ってみます。

```
template <typename T, typename E>
struct result {

  result(T const& ok) : t(tag::OK) {
    ok\_ = ok;
  }

  result(E const& e) : t(tag::OK) {
    err\_ = e;
  }

  ~result() {
    switch (t) {
      case tag::OK:
        ok\_.~T();
        break;
      case tag::ERROR:
        err\_.~E();
        break;
    }
  }

  result(result const& r): t(r.t) {
    switch (t) {
      case tag::OK:
        ok\_ = r.ok\_;
        break;
      case tag::ERROR:
        err\_ = r.err\_;
        break;
    }
  }

  T const& get() const {
    if (t != tag::OK) {
      throw "invalid get operation";
    }
    return ok\_;
  }

  E const& get\_error() const {
    if (t != tag::ERROR) {
      throw "invalid get operation";
    }
    return err\_;
  }

private:
  enum class tag {
    OK,
    ERROR,
  };
  tag t;
  union {
    T ok\_;
    E err\_;
  };

};

```

かなり雑ですが、ざっくりこんな感じになるはずです。
C++11 から拡張されて自由度がかなり高くなった `union` がとても便利です。

これで `result<int, std::string>(1).get()` とやれば `1` が返るし `result<int, std::string>(std::string("test")).get_error()` で `"test"` が返るはずです。

## C++ でやると何が難しいか

C++ で難しいのは、Rust より弱い型推論が引き起こす問題です。

Rust では、`Ok(1isize)` とか `Err("error!".to_owned())` とすれば、その値がどういう型であることが期待されているのかまで含めて型推論や単一化が行われます。
すなわち、`Ok(1isize)` だけを見てもエラーの型がわからないため、`Result<isize, E>` の `E` を決定することが出来ないが、Rust は強力な型推論機構を持つため、これを決定することが出来ます。

一方、C++ では `result<int, std::string> f() { return 1; }` は `int` から `result<int, std::string>` の暗黙変換がきくので可能ですが、`result<int, int>` などとした瞬間、暗黙変換に頼ることはできなくなります。
そこで、出来れば `ok(1)` とか `err("test")` という感じにしたいのですが、これは一筋縄では行きません。

```
template <typename T, typename E>
result<T, E> ok(T);

```

これだと `T` は推論されても `E` が推論されないので、`ok<int, std::string>(1)` などとしなければなりません。これは使いづらすぎます。

## じゃあどうするか

先ほどとは違う形ですが、やっぱり暗黙の型変換を応用します。

要するに `ok` を表す型と `error` を表す型を区別しつつ、`result<V, E>` とはなるべくシームレスに変換をしたいというわけですから、それぞれ専用の型を作ってしまえば良いのです。

```
template <typename T>
struct ok\_value {
  explicit ok\_value(T t): t(t) {}

  template <typename V, typename E>
  operator result<V, E> () const;

private:
  T t;
};

template <typename T>
template <typename V, typename E>
ok\_value<T>::operator result<V, E> () const {
  return result<V, E>(t);
}

template <typename T>
ok\_value<T> ok(T t) {
  return ok\_value<T>(t);
}

```

`ok` 側だけ示しました。

`ok` 関数はテンプレートになっており、`T` 型の値をとって `ok_value<T>` を返します。（本当は値渡し以外にも対応すべきですが、簡単のために値渡しだけ実装しています）

`ok_value<T>` は型変換演算子 `operator result<V, E>() const` を持ちます。これによって `ok_value` から `result` への暗黙変換が可能になります。

`ok_value<T>` は `result<T, E>` に変換出来れば良さそうに見えるのですが、それでは不十分です。

`ok("test")` は `ok_value<const char*>` を返します。`ok_value<T> -> result<T, E>` の変換しか提供していない場合は、`result<std::string, E>` への変換ができなくなってしまいます。これは不便ですよね。

そこで新たにテンプレート引数を導入することでこれを解決しています。もっときちんとやるなら `std::is_constructible` などを使ってチェックをするべきだとは思いますが。

`error` 側もほぼ同様のコードを書いてやれば、

```
result<int, std::string> parse\_digit(char c) {
  if (c < '0' || '9' < c) {
    return error("invalid character");
  }
  return ok(c - '0');
}

```

というように書けます。

## まとめ

`T` から `result<T, E>` への暗黙変換を許すという方針も全然ありだとは思いますが、個人的に Rust などで `ok` なら `ok` と明示するスタイルに慣れているので、こっちのほうが気に入っています。

明らかに正常に値を返していそうな感じがコードにあらわれて好きです。

暗黙の型変換って危険だしあまり良いイメージはないと思うのですが、やっぱりあれば便利ですね。
C++ を使っている時点で気を抜いたら死なので、「取り扱いを把握して全力で注意しながら使えば危険じゃない」という気持ちで便利に使いたいものです。

---

---


C++ で result 型を作る


C++テンプレートの有名なイディオムとして、CRTP というものがあります。
今回はそれについて。
複雑な部分特殊化みたいな話もないですし、メリットもわかりやすい良いイディオムだと思うので、ちょっとまとめておきます。
(Control キーのことをよく CTRL と書くので、CTRP とタイポしがち）

詳細はこちらを参照してください。
[More C++ Idioms/奇妙に再帰したテンプレートパターン(Curiously Recurring Template Pattern) - Wikibooks](<https://ja.wikibooks.org/wiki/More_C%2B%2B_Idioms/%E5%A5%87%E5%A6%99%E3%81%AB%E5%86%8D%E5%B8%B0%E3%81%97%E3%81%9F%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3(Curiously_Recurring_Template_Pattern)>)

## CRTP の利点

細かい実装の話の前に、CRTP を使うと何がうれしいのかを簡単に。

**静的 Template Method パターンの実現**\_ 。これが CRTP の利点です。

Template Method パターンについてはここでは説明しませんが、大枠のアルゴリズムを共有しつつその内部で使用する実装の詳細をクラスごとに切り替えるといった目的に使われるデザインパターンです。

通常 Template Method パターンを C++ で実現しようと思うとどうしても仮想関数を使うことになると思います。これによって実行時のオーバヘッドがかかってしまいます。
Template Method パターンは、いわゆるクラスベースの動的なポリモーフィズムを必要としないクラスであっても、アルゴリズムの共有やボイラープレートコードの削減に非常に有用なパターンです。
これを静的に実現するのが CRTP の目的なのです。

## 実装

CRTP とは、その名の通り、奇妙に再帰したテンプレートのパターンのことです。
情報量０の文章ですね。実際のコードも見たほうがわかりやすいと思います。

以下に、`compare` というメソッドから比較演算子を _derive_ (自動導出) する例をのせます。

```
#include <iostream>

template <typename T>
struct comparable {
  template <typename U>
  friend bool operator==(comparable const& lhs, U const& rhs) {
    return static\_cast<T const&>(lhs).compare(rhs) == 0;
  }

  template <typename U>
  friend bool operator>(comparable const& lhs, U const& rhs) {
    return static\_cast<T const&>(lhs).compare(rhs) > 0;
  }

  template <typename U>
  friend bool operator<(comparable const& lhs, U const& rhs) {
    return static\_cast<T const&>(lhs).compare(rhs) < 0;
  }
};

struct person : comparable<person> {
  int age;

  int compare(person const& rhs) const {
    return age - rhs.age;
  }
};

int main() {
  person p1, p2;
  p1.age = 10;
  p2.age = 100;

  std::cout << std::boolalpha << (p1 == p2) << std::endl;
  std::cout << std::boolalpha << (p1 < p2) << std::endl;
  std::cout << std::boolalpha << (p1 > p2) << std::endl;
}

```

`person` クラスには `operator==` など定義していないにもかかわらず、`person` を比較することが出来ています。

CRTP の中心となるのは `struct person : comparable<person>` という部分です。
クラスを定義する際に、自分をテンプレート引数にとるクラスを継承するというコード、これこそが「奇妙な再帰」なのです。
実際、`struct person : comparable<person>` の部分ではまだ `person` がどんな実装になるかはわかっていません。奇妙ですね。

さて、まずは `person` の中身を見てみます。
`person` では、`person const&` を引数にとり、それが自分より大きければ正の値を、小さければ負の値を、等しければ 0 を返すような、`compare` というメソッドを定義しています。
`person` の仕事はこれだけです。

`comparable` は、テンプレート引数にひとつの型をとります。

`comparable` はその型が `compare` というメソッドをもつことを期待しています。(暗黙のインターフェース)

`comparable` の仕事は `compare` というひとつのメソッドから、`operator==`, `operator<`, `operator>` を自動的に導くことです。

Template Method パターンをご存じの方ならすんなり理解できるかと思います。

CRTP のすごいところは、仮想関数をまったく使わないことです。つまり、実行時のテーブルルックアップは発生しません。すべてが静的に決定されるのです。

## おまけ

先に挙げた `compare` から `operator==` を自動導出する例ですが、Haskell の `Ord` 型クラスを意識しています。

```
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<), (<=), (>), (<=) :: a -> a -> Bool
  max, min :: a -> a -> a

```

`Ord` 型クラスのインスタンスになるためには、最低でも `compare` を実装している必要があります。
逆にいえば、`compare` だけ実装すれば、他の関数は自動的に実装されます。

Haskell では、`Ord` になるためには `Eq` のインスタンスである必要があります。
これを C++ で表現するためには、

```
template <typename T>
struct ord : eq<T> {
  ...
};

```

こんな感じでしょうか。もちろん型クラスの代替にはなりえないんですけどね。
Haskell の型クラスの利点のひとつである、最小限のインターフェース実装による関数の自動導出っぽいこともできるよというお話でした。

実際にテンプレートライブラリを書いてみて改めて有用性がわかったテクニックでした。
拙作の coco にも導入したい... すべてのパーサにユーティリティメンバ関数を追加するみたいなことが出来るはず... いつかやります。

---

---


C++テンプレートイディオム CRTP


C++ のテンプレートがなぜ必要で，どんな構文・種類のものがあるかについては前回までにまとめました。

というわけで次は C++ ではテンプレートという機能を使用するとどんなバイナリが生成されるのかについて見ていきます。

C++ のテンプレートの強力さとか勘所みたいなものを把握するために非常に重要な部分なので、覚えておくとよいと思います。

## C++ でテンプレートをコンパイルしてみる

早速ですが、実際に C++ でテンプレートを使っているコードをコンパイルしてみます。

アセンブリよりも LLVM IR のほうがわかりやすいかな？と思うので、LLVM IR を clang++ で生成させてみます。
（LLVM IR については [大学院生のための LLVM | インフラ・ミドルウェア | POSTD](http://postd.cc/llvm-for-grad-students/) あたりを読んでおくとなんとなく概念がつかめると思います。公式は[LLVM Language Reference Manual — LLVM 3.9 documentation](http://llvm.org/docs/LangRef.html)）

対象となるコードはこちら。

```
// main.cpp
template <typename T>
T identity(T x) {
  return x;
}

int main() {
  float f = 0.0f;
  identity(f);

  int d = 0;
  identity(d);
  return 0;
}

```

clang++ で LLVM IR を生成させるには，`-S -emit-llvm` をオプションに指定します。また、今回のコードは最適化されてしまうとほとんどコードが残らないので、最適化を抑制するよう、`-O0` を付けます。

```
$ clang++ -O0 -S -emit-llvm main.cpp
```

すると `main.ll` というファイルが出来ています。これが LLVM IR です。

## IR を読む

LLVM IR は，LLVM というコンパイラ基盤技術における中間表現 (Intermediate Representation) です。

ざっくり言うと、アーキテクチャに依存しない、読みやすいアセンブリです。

`main.ll` はそこまで長くないですが、エッセンスだけ抜粋します。

```
define i32 @main() #0 { ;; main 関数
  %1 = alloca i32, align 4
  %f = alloca float, align 4
  %d = alloca i32, align 4
  store i32 0, i32* %1
  store float 0.000000e+00, float* %f, align 4
  %2 = load float* %f, align 4
  %3 = call float @\_Z8identityIfET\_S0\_(float %2)
  store i32 0, i32* %d, align 4
  %4 = load i32* %d, align 4
  %5 = call i32 @\_Z8identityIiET\_S0\_(i32 %4)
  ret i32 0
}

define linkonce\_odr float @\_Z8identityIfET\_S0\_(float %x) #1 { ;; identity<float> の実体
  %1 = alloca float, align 4
  store float %x, float* %1, align 4
  %2 = load float* %1, align 4
  ret float %2
}

define linkonce\_odr i32 @\_Z8identityIiET\_S0\_(i32 %x) #1 { ;; identity<int> の実体
  %1 = alloca i32, align 4
  store i32 %x, i32* %1, align 4
  %2 = load i32* %1, align 4
  ret i32 %2
}
```

コメントでも書きましたが、3 つの関数が定義されていることがわかると思います。
ここで重要なのは、 **identity<int>と identity<float>がそれぞれ別の関数として定義されている** ことです。

`identity<int>` と `identity<float>` は `main` の中で使われています。

つまり、テンプレートは、「使った分だけ実体が作られる。かつその処理はコンパイル時に終わる。」ということがわかります。

たとえばソースコード中に `identity<bool>` の実体化を要求するコードがあれば、その時はじめて `identity<bool>` が作られます。
独自定義でも構いません。`identity<MyClass>` の実体化を要求するコードがあれば、その時はじめて `identity<MyClass>` が作られます。

もちろん、一度実体化されたテンプレートは再利用されます。つまり、`identity<int>` を要求するコードが、一つのソースコードに何度現れても、ただひとつの `identity<int>` が生成されます。

## Java との比較

Java にもジェネリクスという仕組みがあります。

概念的にはテンプレートに似たものなので、比較してみます (テンプレートの方がより強力ですが、型を汎用化したいという目的であれば、両者とも同様に使用できます。)

同じようなコードをコンパイルしてバイトコードを見てみます。

```
class Main {
  static <T> T identity(T x) {
    return x;
  }

  public static void main(String[] args) {
    Integer d = 1;
    Float f = 0.0f;
    Main.identity(f);
    Main.identity(d);
  }
}

```

`javac Main.java` してから、`javap -v Main` します。これでバイトコードが出力されます。

```
class Main
/* 中略 */
{
  Main();
    descriptor: ()V
    flags:
    Code:
      stack=1, locals=1, args\_size=1
         0: aload\_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 1: 0

  static <T extends java.lang.Object> T identity(T);
    descriptor: (Ljava/lang/Object;)Ljava/lang/Object;
    flags: ACC\_STATIC
    Code:
      stack=1, locals=1, args\_size=1
         0: aload\_0
         1: areturn
      LineNumberTable:
        line 3: 0
    Signature: #14                          // <T:Ljava/lang/Object;>(TT;)TT;

  public static void main(java.lang.String[]);
    descriptor: (Ljava/lang/String;)V
    flags: ACC\_PUBLIC, ACC\_STATIC
    Code:
      stack=1, locals=3, args\_size=1
         0: iconst\_1
         1: invokestatic  #2                  // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
         4: astore\_1
         5: fconst\_0
         6: invokestatic  #3                  // Method java/lang/Float.valueOf:(F)Ljava/lang/Float;
         9: astore\_2
        10: aload\_2
        11: invokestatic  #4                  // Method identity:(Ljava/lang/Object;)Ljava/lang/Object;
        14: pop
        15: aload\_1
        16: invokestatic  #4                  // Method identity:(Ljava/lang/Object;)Ljava/lang/Object;
        19: pop
        20: return
      LineNumberTable:
        line 7: 0
        line 8: 5
        line 9: 10
        line 10: 15
        line 11: 20
}
SourceFile: "Main.java"
```

注目すべきは `// Method identity:(Ljava/lang/Object;)Ljava/lang/Object;` というコメントのついた行です。

2 行ありますが、それぞれ `identity(d)` と `identity(f)` に相当します。

`Integer.valueOf` や `Float.valueOf` を含むコメントを見ていただければわかると思いますが、このコメント部分には呼び出しているメソッドの型が記されています。

つまり、`identity` は `Integer` で呼んでも `Float` で呼んでも `Object identity(Object)` を呼んでいるということです。

これは [Java のジェネリクスの大きな特徴で型消去などと呼ばれる性質です。ジェネリクスによる型はすべてコンパイル時にのみ利用され、実行時にはすべて `Object` として表現しつつ適切にキャストを挟むような構造になっています。

キャストはキャストでも、正しいことがコンパイラによって保証されたキャストになるので、`List` よりも `List<String>` のほうが安全というわけです。

## それぞれの利点と欠点

テンプレートやジェネリクスを実現する方法として、2 つの例を上げました。

一つは C++ の採用している方式で、テンプレート引数ごとに新しく実体を作ってしまう方式です。

もう一つは Java の採用している方式で、`Object` のようにすべての型を受け取れる基底クラスのようなものを用いて、実行時には型情報を残さない方式です。

今回はたまたま C++ と Java を例にあげましたが、他の言語でもこのような方式を使っている言語は多いです。（みんなだいすき D 言語は C++ の方式を採用しています）

さてそれぞれの利点と欠点についてです。

### Java 方式

- 利点
  - 分割コンパイルが容易（ジェネリックな関数を提供する側は `Object` を入れたバイナリやバイトコードと、型情報だけを生成すればよい。使用する側は、型情報から型検査を行った後、`Object` へのキャストなどを含めたバイナリやバイトコードをはけば良い）
- 欠点
  - 実行時にやることが増えるのでオーバヘッドがある

### C++ 方式

- 利点
  - 実行時オーバヘッドなし（全てコンパイル時に解決される）
- 欠点
  - バイナリサイズの増加
  - 分割コンパイルが困難 (テンプレートを実体化しようと思うと、型情報だけでは足りない。使用者側が定義そのものをまるまる知っている必要がある。)

こんな感じでしょうか。

この比較はあくまで型を汎用化したいという目的に関しての比較です。C++ のテンプレートにできて Java のジェネリクスに出来ないことはたくさんあります。

## まとめ

C++er はみんな実行時のオーバヘッドが嫌いです。テンプレートは、今までに紹介してきた使用法からは想像も出来ないほど豊富な計算を、コンパイル時にすべて行うことが出来ます。実行時のオーバヘッドなしで。

コンパイル時にテンプレートの解決が終わるということは、強力な最適化が望めるということでもあります。つまり、実行時のキャストといったわかりやすいオーバヘッド以上に、実行速度には差が生まれるでしょう。

というわけで今回はテンプレートの実現方法について、Java と比較しながら説明してみました。

---

---


C++ のテンプレートの実装


C++ のテンプレートについてまとめているのでそれらをまとめておきます。

今後の予定も合わせて目次にしておきます。

1. なぜテンプレートが必要なのか
   [agtn.hatenablog.com](http://agtn.hatenablog.com/entry/2016/05/30/234647)
2. テンプレートの種類と構文
   [agtn.hatenablog.com](http://agtn.hatenablog.com/entry/2016/05/31/175756)
3. (おまけ) テンプレートの実行時表現とコンパイル方法
4. 特殊化と部分特殊化
5. メタ関数
6. SFINAE

後々 CRTP や type erasure についてもまとめていけたらと思います

---

---


C++ のテンプレートについてまとめるのまとめ


前回テンプレートがなぜ必要なのかについて簡単にまとめたので、今回はその構文や種類についてまとめたいと思います。

[agtn.hatenablog.com](http://agtn.hatenablog.com/entry/2016/05/30/234647)

## アウトライン

- テンプレートの種類と構文
  - 定義する
  - 使用する(インスタンス化)
- クラステンプレート
- 関数テンプレート
- メンバテンプレート
- エイリアステンプレート(C++11〜)
- 変数テンプレート(C++14〜)
- まとめと今後

## テンプレートの種類と構文

C++ のテンプレートは，大きく 5 種類に分類することが出来ます。

1. クラステンプレート
2. 関数テンプレート
3. メンバ関数テンプレート
4. エイリアステンプレート
5. 変数テンプレート

これらについて、以降で詳しくまとめていきます。

まずざっくり共通するシンタックスを示しておきます。

### 定義する

何かのテンプレートを定義したい場合は、通常の定義の前に `template` 宣言を記述します。

```
template <typename T>
class stack {
  ...
};

```

複数のテンプレート引数を取りたい場合や、型以外のテンプレート引数を取りたい場合には、以下のようにします。

```
template <typename T, int N>
class my\_array {
  ...
};

```

上の例はクラステンプレートでしたが、関数でもエイリアスでも、`template` を宣言する部分は共通です。

### 使用する(インスタンス化)

次にテンプレートを使用する場合です。

テンプレートはあくまでテンプレートなので、使用する際には、具体的なテンプレート引数を与えて実体化する必要があります。これを **インスタンス化** といいます。

インスタンス化の構文も、テンプレートの種類によらず基本的には共通しています。

```
stack<int> int\_stack;
my\_array<std::string, 5> five\_strings;

```

`テンプレート名 < 引数 >` という感じです。

一応注意書きをしておきますと、`stack<stack<int>>` がシンタックスエラーになる場合があります。
意味としては `stack<int>` のスタックです。

`stack<stack<int>>` がコンパイルエラーになる場合は、使っているコンパイラが古いかもしれません。
C++03 では、`>>` の部分がシフト演算子として解釈されてしまうためです。

`g++ -std=c++11` とか `clang++ -std=c++11` とか `g++ -std=c++14` とか `clang++ -std=c++14` とか、コンパイラが新しい規格を参照するようにオプションを渡してあげれば動きます。

(もし動かない場合はコンパイラが古すぎます。もう 2016 年ですから、最低でも C++11 以降を使いましょう。別物です。)

では、以降、それぞれのテンプレートについて詳しく見ていきます。

## クラステンプレート

クラステンプレートは、クラスのテンプレートです。前回の `stack` がこれにあたります。

一番わかり易いユースケースは、コンテナ型の定義でしょう。

スタックや単方向リスト、ハッシュマップなど、内部に保持する型に依存しないデータ構造を定義するために使えます。

前回の `stack` を再掲しておきます。

```
template <typename T>
class stack {
public:
  stack() : data(), n() {}

  void push(T x) {
    if (n >= MAX\_ELEM) {
      throw "stack is full!!";
    }
    data[n++] = x;
  }

  T pop() {
    if (n < 0) {
      throw "stack is empty!!";
    }
    return data[--n];
  }
private:
  T data[MAX\_ELEM];
  int n;
};

```

## 関数テンプレート

関数テンプレートは以下の様なものです。

```
template <typename T>
T max(T left, T right) {
  if (left > right) {
    return left;
  } else {
    return right;
  }
}

int x = max<int>(1, 0); // => x == 1
double y = max<double>(0.5, 100.0); // => y == 100.0

```

`max` 関数は、「ある型 T について、２つの引数のうち、大きい方を返す」関数です。

明示的に `max<int>` や `max<double>` とすることで、`int` や `double` についての「大きい方を返す」関数を得ています。

### テンプレート引数の推論

実は、関数テンプレートの場合、明示的にテンプレートを引数を渡す必要がない場合があります。

今回の `max` 関数はまさにそのケースです。

```
int x = max(1, 0);

```

これは、テンプレート引数の型推論の結果です。

`max` 関数の第一引数、第二引数はそれぞれ `T` です。そして、実際に渡されている `1` や `0` は `int` 型です。

これらの情報から、コンパイラは `T == int` であることを推論します。

したがって暗黙に `max<int>` と指定されることになります。

この推論は色々複雑だったりしますが、はじめは引数から単純に推論できれば推論されると思っておけば良いんじゃないかなと思います。

一方、クラステンプレートなど、関数テンプレート(とメンバ関数テンプレート)以外のテンプレートの場合には、この推論は行われません。

勘違いしやすいので気をつけましょう。特にクラステンプレートは間違いやすいです。

### メンバ関数テンプレート

```
class printer {
public:
  explicit printer(std::ostream& os) : os(os) {}

  template <typename T>
  void print(T const& v) {
    os << v;
  }
private:
  std::ostream& os;
};

```

メンバ関数テンプレートは、関数テンプレートとほとんど同じです。違いは、メンバ関数として定義されていることだけです。

```
printer p(std::cout);

```

ここまではテンプレートでもなんでもないただのクラスです。

```
p.print(0);
p.print("abc");
p.print<double>(0.1);

```

こんな感じで使います。関数テンプレートとほぼ同じですね。

### エイリアステンプレート

エイリアステンプレートは、C++11 から使用できるテンプレートです。

```
template <typename T, typename U>
struct pair;

template <typename T>
using with\_int\_t = pair<T, int>;

```

`using` で型名のエイリアスを作ることが出来ますが、それをテンプレートにすることが出来ます。

```
with\_int\_t<bool> p(true, 0);  // pair<bool, int> p(true, 0);
with\_int\_t<std::string> s("abc", 100);  // pair<std::string, int> s("abc", 100);

```

ちなみに C++11 より前は、エイリアステンプレートの代替として、

```
template <typename T>
struct with\_int {
  typedef pair<T, int> type;
}

with\_int<bool>::type p(true, 0); // pair<bool, int> p(true, 0);

```

という記述をしていました。(今でもライブラリなどで現役の表現ですので覚えておきましょう)

### 変数テンプレート

最後の変数テンプレートは、C++14 から使用できるテンプレートです。

```
template <typename T>
constexpr T pi = static\_cast<T>(3.1415926);

int x = pi<int>;
double y = pi<double>;

```

`constexpr` は定数式というやつです。

ちなみに C++14 より前は、代替として

```
template <typename T>
struct pi {
  static const T value = static\_cast<T>(3.1415926);
};

int x = pi<int>::value;
double y = pi<double>::value;

```

という記述をしていました。(こちらも現役の表現です)

## まとめと今後

というわけで今回はテンプレートの種類とそれぞれのシンタックスについてまとめてみました。

今後、特殊化や部分特殊化などのお話をするときに種類によって微妙に違いがあったりするので、しっかり区別しておいたほうが良さそうです。

---

---


C++ テンプレートの種類と構文


こんにちは。

ちょっと C++ への熱を冷まさないために、C++ のテンプレートについてまとめてみたいと思います。

## 対象

- C++ のテンプレートが怖い人
- C++ のコンパイルエラーメッセージが怖い人
- C++ の規格とブログポストを比較して誤りを探したい人(もし誤っていたら教えて下さい...)

## テンプレートとは

> プログラミングにおけるテンプレートは、静的型付けの C++でデータ型にとらわれずにコードを書くことを可能にする機能であり、C++においてはジェネリックプログラミングに用いられる。
>
> [テンプレート (プログラミング) - Wikipedia](<https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)>)より

他の静的型付きなプログラミング言語をすでに知っている場合は，すんなり入りやすいかもしれません。

Java や Scala, C# でいうところのジェネリクスに近い存在です。

OCaml や Haskell だと多相とか。

雑に表現するならば、リストとか連想配列のように内部のデータ型に依らないデータ構造を、静的型のもとにどうやったらうまく表現できるかな、に対する解の一つです。

### 例

では一つの例として、スタックというデータ構造をプログラムに落としこむことを考えます。

まずは `int` 型のスタックを定義してみます。

```
#define MAX\_ELEM 10

class int\_stack {
public:
  int\_stack() : data(), n() {}

  void push(int x) {
    if (n >= MAX\_ELEM) {
      throw "stack is full!!";
    }
    data[n++] = x;
  }

  int pop() {
    if (n < 0) {
      throw "stack is empty!!";
    }
    return data[--n];
  }
private:
  int data[MAX\_ELEM];
  int n;
};

```

簡単のため、かなりお粗末なスタックですが、最低限のスタックとしての見た目はしていると思います。

では次に、`std::string` 型のスタックや `double` 型のスタックを作りたいとなったらどうすればよいでしょうか。

コピーして `int` を置換しますか？あまり褒められた方法ではなさそうです。

#### C でのアプローチの一つ

C 言語の場合、このような問題に対しては `void*` というアプローチがあります。

`void*` は java でいう `Object` のように扱われます。

```
#define MAX\_ELEM 10

struct stack {
  void *data[MAX\_ELEM];
  int n;
};

void push(stack *s, void *elem) {
  ....
}

void *pop(stack *s) {
  ....
}

/* Usage */
stack *s = new\_stack();
int *x = (int*)malloc(sizeof(int));
*x = 1;
push(s, (void*)x);
int *y = (int*)pop(s);
printf("%d\n" *y); /* => 1 */

```

こんな感じでしょうか。実装の細かい部分は省略しています。

`push` の際にはあらゆるポインタを `void*` にキャストし、逆に `pop` する際には `void*` を求める型にキャストしています。

ジェネリクスのなかった頃の java は、これを `Object` へのキャスト・`Object` からのキャストとして表現していました。

##### void\* のデメリット

`void*` を使う場合のデメリットは、型システムを台無しにしている点です。(`malloc` や `free` が必要であることは C 言語特有の問題なのでスルー)

つまり、`int` のスタックから `pop` してきたとき、`int*` に正しくキャストを行う責任はプログラマにあり、コンパイラは何も手助けをしてくれないということです。

したがって、 `int` スタックに `double` の値を `push` したり、 `double` スタックから `char*` を `pop` したりというミスが簡単に引き起こされてしまうということです。

#### そこでテンプレート

では C++ ではどのようなアプローチを取るかというと、テンプレートを使います。

今回は型に関するテンプレートの話しかしないので、java のジェネリクスも大体同じ話だと思って構わないと思います。(実行時の表現やコンパイラの動きなどの違いはあるが、対象としている問題は同じ)

さきほどの `int_stack` の実装では、要素型が `int` に固定化されてしまっているのが問題でした。

そこで、テンプレートでは、型を抽象化し、ある種の引数のように扱っています。

```
template <typename T>
class stack {
public:
  stack() : data(), n() {}

  void push(T x) {
    if (n >= MAX\_ELEM) {
      throw "stack is full!!";
    }
    data[n++] = x;
  }

  T pop() {
    if (n < 0) {
      throw "stack is empty!!";
    }
    return data[--n];
  }
private:
  T data[MAX\_ELEM];
  int n;
};

```

先頭の `template <typename T>` (`template <class T>` でも可)は、型引数の導入の役割を果たしています。

`stack` クラスの定義内に登場する `T` は型引数として導入された型を表します。

利用する際には、`stack<int>` とか `stack<std::string>` とか、型を `stack` に渡してあげれば OK です。

```
stack<int> int\_stack;
int\_stack.push(1);
int\_stack.push(2);
int x = int\_stack.pop();
int\_stack.push("abc"); // => Compile error!

stack<std::string> str\_stack;
str\_stack.push("abc");
str\_stack.push(1); // => Compile error!

```

このように、同じコードをコピペすることなく、複数の型に対応したスタックという汎用的なデータ構造を表現することが出来ています。

さらに、この方法では、`void*` や `Object` と異なり、型的に誤った使用方法をしようとするとコンパイルエラーになるというメリットがあります。

ランタイムエラーよりコンパイルエラーのほうがデバッグしやすいし発見しやすいですよね。

## 一旦まとめ

というわけで今回はテンプレートがなぜ便利かという話のほんのさわりの部分について書いてみました。

次はテンプレートやジェネリクスの実現方法、ランタイムにおける表現方法などについて書いてみます。

そこからはテンプレート引数として値をとる話や、TMP についても触れていければと思っています。

---

---


C++ : なぜテンプレートが必要なのか


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

### 2016/05/01 追記

いろいろ更新しました．肯定先読み以外はプリミティブも実装し終わっているかと思います．

ドキュメントはまだ無いのですが，すべての機能についてテストは書いてあるので，それを見てもらえればなんとか使い方もわかるかと思います．

[agatan/coco](https://github.com/agatan/coco)

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

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

そこで，Haskell の [parsec](https://hackage.haskell.org/package/parsec) や Rust の [combine](https://github.com/Marwes/combine) を参考にしつつ，C++ でパーサコンビネータを書いてみました．(実際これを使ってもコンパイルエラーは割りと発狂しますが)

## 例

例となるコードは [agatan/coco-combix-demo](https://github.com/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 のプリミティブをまだ完全に実装していないと思います．先読みや否定先読みが出来ません．(実装します…)

---

---


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


テンプレートをバリバリ使っている C++ プログラムのコンパイルエラーが，死ぬほど辛かったので作りました．
型を綺麗に出力するだけです．
C++の型版 `jq` みたいなやつありそうだけど無いのかな？

[agatan/tf](https://github.com/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 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
>

```

---

---


C++ の複雑な型を整形するプログラムを作りました


プログラミングしていて，木構造をうまく扱いたいという状況は結構良くあると思います．

代数的データ型とパターンマッチを持つ言語であればとても美しく完結に表現できる木構造ですが，オブジェクト指向言語でやろうと思うと結構たいへんです．

典型的には Visitor パターンというやつを用います．[デザインパターン - Visitor パターン再考 - Qiita](http://qiita.com/lyrical_logical/items/bc6126f34a571a2c4f97)が非常にわかりやすく，理解の助けになりました．ありがとうございます．

一方，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 パターンで良くね？感出てきた

---

---


Type Erasure による Visitor パターンの実装


[Haskell で import 文をソートするプラグイン vim-haskell-sort-import を作りました - プログラムモグモグ](http://itchyny.hatenablog.com/entry/2016/01/23/190000)という記事を拝見して，コードを見たらすごくわかりやすくて，これの C/C++ 版がほしいと思い，書いてみました．

vim script はほとんど書いたことがないんですが，やっぱりエディタ拡張用のスクリプトなので，普通の言語と違う部分は多いですね…
でもその分エディタという UI が既に用意されている状態なので，なんというか書いていて楽しかったです．さくっと書けますし．（先ほどのコードを参考にしているというのもありますが）

## 使い方

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

![f:id:agtn:20160124191335g:plain](/i/20160124191335.gif "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 フォーマットにしたがって書いてみました．

---

---


#include をソートするVimプラグインを作りました


[agtn.hatenablog.com](http://agtn.hatenablog.com/entry/2015/12/17/190505)
[agtn.hatenablog.com](http://agtn.hatenablog.com/entry/2015/12/17/232003)

引き続き，`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` で再帰的なパーサを記述する方法は[前回の記事](http://agtn.hatenablog.com/entry/2015/12/17/232003)にまとめました．

```
  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_f` は `assign` と異なり，関数オブジェクトを１つ引数に取ります．

そして，その関数オブジェクトを `_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_expr` は `1` や `(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_expr` は `mul_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 除算のエラーを通知する際，どの部分でのエラーなのかを吐いてくれればうれしいですよね).

パース失敗時にもどこで失敗したのかをレポートしてくれたほうが便利です．

`X3` で `on_error`, `on_success` を使ってこれらを実装してみようと考えています．

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

---

---


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


[Boost.Spirit.X3 の練習 1 - プログラミングのメモ帳 ➚](http://agtn.hatenablog.com/entry/2015/12/17/190505)に引き続き，`Boost.Spirit.X3` のお勉強メモです．

## セマンティックアクション

構文解析にはセマンティックアクションというのがつきものです．

`yacc` や `parsec` など有名な構文解析のためのツール/ライブラリにもありますね．

セマンティックアクションとは，定義したパーサのルールにマッチした時に実行するプログラムのことです．

といってもわかりにくいと思うので，コードを出してしまいます．

以下のコードは，浮動小数点数にマッチしてその値を標準出力に出力するパーサの定義です．

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

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

auto const print\_action =
  [](auto& ctx) { std::cout << \_attr(ctx) << std::endl; };

int main()
{

  std::string src{ "( 123.4 )" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);

  auto parser = ("(" >> x3::double\_ >> ")")[print\_action];

  bool success = x3::phrase\_parse(first, last, parser, x3::ascii::space);

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

```

```
$ clang++ -std=c++14 main.cpp
$ ./a.out
123.4
```

パーサの結果を受け取らないようにしています．`parser` は `double` を返しますが，その結果は無視しています．

そして，セマンティックアクション部分で，出力を行っています．

`auto const print_action` の定義が，セマンティックアクションです．

`C++14` のジェネリックラムダの機能をつかっています．

セマンティックアクションは，`X3` パーサのコンテキストを第一引数に取ります．

その具体的な型を気にしてはいけません．ジェネリックラムダで受け取ります．

`_attr(ctx)` で，現在マッチしているパーサの attribute にアクセス出来ます．
`"(" >> x3::double_ >> ")"` の attribute は `double` 型なので，`_attr(ctx)` はマッチした浮動小数点数になります．

`Qi` のセマンティックアクションは，関数オブジェクトなどを単純に使用することが出来ませんでした(?) が，`X3` ではセマンティックアクションはただの関数オブジェクトです．

パーサのコンテキストを引数に受け，結果や attribute への参照をそのまま関数内で扱えるようになったため，セマンティックアクションの記述がより _普通_ の関数っぽくかけるようになったと感じました．

## 名前付きパーサの定義

今までのサンプルでは，シンプルなパーサを１つ定義しているだけでした．

一方現実には，パーサが再帰的になることは珍しくありません．

そこで，パーサの名前を前方宣言し，あとから定義を記述するようなパーサの書き方を使用します．

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

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

namespace detail {

  x3::rule<class constant, int> const constant;

  auto const constant\_def = x3::int\_;

  BOOST\_SPIRIT\_DEFINE(constant);

} // namespace detail

using detail::constant;

int main()
{

  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);


  int result;
  bool success = x3::phrase\_parse(first, last, constant, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

```

`namespace detail` の中身がパーサの定義になっています．
(`namespace` を分けたのは，`constant` そのものの名前以外を隠すためです．)
`X3` では，`x3::rule<class, result type>` というテンプレートクラスがパーサルールになります．`class` 部分は今は前方宣言だけで構わないようです．(後で `on_error` とかの属性を付与する際に必要になる？)

`result type` はそのパーサが返すべき値になります．

つまり，`x3::rule<class constant, int> const constant;` は，`int` 型の値を返す，特別な属性を持たない `constant` という名前のパーサを宣言したことになります．

そして，その実装は `constant_def` という名前で与えられます．

`hogehoge_def` という名前にする規約のようです．(`BOOST_SPIRIT_DEFINE` 部分を書き換えれば違う名前にしても大丈夫のようだが，素直に従っておけば良さそう)

今回はシンプルに `x3::int_` そのものとしています．

最後に `BOOST_SPIRIT_DEFINE` することで，`constant` というパーサの宣言と，`constant_def` という実装をひも付けます．

使い方は今までと全く同じです．

## 使ってみる

セマンティックアクションと名前付きパーサの両方を使って，整数を受け取って 2 倍にした値を返すパーサを書いてみます．

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

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

namespace detail {

  auto const twice = [](auto& ctx) { \_val(ctx) = \_attr(ctx) * 2; };

  x3::rule<class constant, int> const constant;

  auto const constant\_def = x3::int\_[twice];

  BOOST\_SPIRIT\_DEFINE(constant);

} // namespace detail

using detail::constant;

int main()
{

  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);


  int result;
  bool success = x3::phrase\_parse(first, last, constant, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

```

セマンティックアクション内では，パーサの `result type` に `_val(ctx)` でアクセス出来ます．
`_val(ctx)` は参照を返すので，ここに適当な値を代入してやれば，パーサの返り値にすることが出来ます．

`_attr(ctx)` は先程と同じです．`x3::int_` の attribute は `int` です．

実行してみると，`Parse: 246` が返るはずです．

## 一旦まとめ

セマンティックアクションと名前付きパーサの宣言と定義をまとめました．

`Qi` のころより，セマンティックアクションはかなり書きやすくなっている気がします．

今回の例では，`_attr(ctx)` が単純な値だったのでわかりやすいですが，`x3::int_ >> x3::double_` の `_attr(ctx)` は `Boost.Fusion` が登場したりしてちょっとややこしそうです．

また，再帰的パーサを定義できるようにパーサの宣言をまとめたのに，再帰的パーサを書いていませんが，これは別記事に電卓でも作ってまとめたいと思います．

---

---


Boost.Spirit.X3 の練習 2


# Boost.Spirit.X3 の練習 1

[Boost.Spirit.X3](http://ciere.com/cppnow15/x3_docs/) という C++ のための パーサコンビネータライブラリを使ってみています．

`Boost.Spirit` というと， C++ の黒魔術の塊みたいなイメージがあります． ちなみに `Boost.Spirit.Qi` が安定版のパーサコンビネータライブラリで， `X3` はまだ開発中のようなので注意してください．

`X3` は `Qi` と異なり，C++14 以降の規格を前提にしています．そのため，ジェネリックラムダなどを用いてよりわかりやすいプログラムが書けるようになっているようです．

`Qi` はコンパイル時間が爆発していたのですが， `X3` だと多少マシのようです．

## 第一歩

まずは猛烈にシンプルなパーサを使ってみましょう．
`X3` も `Qi` 同様に定義済みのパーサがあるので，それを単純に使用するだけのサンプルです．

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

#include <iostream>
#include <string>


int main()
{
  namespace x3 = boost::spirit::x3;

  int result;
  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);
  bool success = x3::parse(first, last, x3::int\_, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

```

### コンパイル & 実行

```
$ clang++ -std=c++14 int\_parser.cpp
$ ./a.out
Parse: 123
```

`Boost.Spirit.X3` を使用する場合は, `#include <boost/spirit/home/x3.hpp>` とすればオッケーです．(これは使用していない機能のヘッダも読み込んでしまっているので，コンパイルは重くなります… が，これ以降使う機能を増やす度にヘッダを書き換えるのは面倒ですし，`X3` の機能の多くを使用するプログラムの場合は，大差ないと思います．)

名前空間は `boost::spirit::x3` です．頻繁に出てくるので `namespace x3` でエイリアスしました．

実際にパースしている部分は,

```
bool success = x3::parse(first, last, x3::int\_, result);

```

の部分です．

`x3::parse` は，第一引数にソース文字列の先頭イテレータ，第二引数にソース文字列の終端イテレータをとります．

第三引数が，パーサの定義です．ここでは， `x3::int_` という定義済みパーサを使用しました． これは, 整数を表す文字列を受けて，それを整数に変換するパーサです． たとえば `"1"` を `1` に変換します．整数以外にあたった場合はマッチせず，パースに失敗します．(`x3::parse` の返り値が `false` になる)
第四引数は，指定したパーサの返す値です．ここちょっと説明が難しいですね．

`x3::int_` は `int` 型の値を返すパーサです(これを `x3::int_` の attribute が `int` 型であると表現している？).

そこで，`x3::int_` の返す値を格納する変数として，`int result` の参照を渡しているという感じです．

パースが成功していれば，`result` の中身は `x3::int_` の返り値になっているはずです．

パースの成否判定は `success` と `first == last` で行います．

```
if (!success || first != last) {

```

`success` はそもそもパーサにソースがマッチしなかった場合, `false` になります．

また，`"123abc"` に `x3::int_` をマッチさせると，`"123"` だけが消費され，`"abc"` が残ります．この時，`first` は `"a"` の位置まで進んでいます．
もしソースが先頭から終端まで，パーサにマッチしていたならば，`first == last` となるはずです．

というわけでこのプログラムは，`x3::int_` に `"123"` をパースさせるプログラムでした．結果，きちんと整数の `123` が取得できていることがわかります．

## コンビネータ

`Boost.Spirit.X3` はパーサコンビネータライブラリです．個々のパーサを組み合わせてみましょう．

`" ( 1234.5)"` とか `"(67.8 ) "` にマッチして，`double` を返すようなパーサを定義してみます．

```
auto parser = x3::lit("(") >> x3::double\_ >> x3::lit(")");
bool success = x3::phrase\_parse(first, last, parser, x3::ascii::space, result);

```

まずは `parser` の定義です．
`x3::lit` はリテラルを表します．引数にとった文字列にマッチし，何も返さないパーサです．`x3::lit("(")` は `(` にマッチし，何も返さないパーサということになります．

`x3::double_` は `x3::int_` と同じく，定義済みパーサで，浮動小数点数にマッチしその値を返します．

そして重要なのが，`>>` です．

これは，「左辺にマッチした後，右辺にマッチするパーサ」を作り出すコンビネータです．

ここでは，`x3::lit("(") >> x3::double_` ですから，`(` にマッチした後，浮動小数点数にマッチするパーサ，ということになります.

通常，`>>` は左辺の返す値と右辺の返す値のタプルを返します．(`x3::int_ >> x3::double_` ならば，`int` と `double` のタプル)

しかし，左辺右辺どちらか一方が値を返さない(正確には `x3::unused_type` を返す) 場合には，もう一方の値だけを返します．

つまり，`x3::lit("(") >> x3::double_` は `double` だけを返し，`>> x3::lit(")")` と続けても `double` だけが返ります．

次に，空白の読み飛ばしについてです．

```
bool success = x3::phrase\_parse(first, last, parser, x3::ascii::space, result);

```

ひとつ目の例と異なり，`x3::parse` ではなく `x3::phrase_parse` を使っています．

こちらは，`attribute` を示す最後の引数の前に，スキップパーサを取ります．
スキップパーサとは，文字通り，スキップしてほしい文字列にマッチするパーサです．

`x3::ascii::space` は定義済みのパーサで，スペース，改行文字，タブにマッチします．したがって，これらの文字はスキップされます．
スキップ判定のタイミングは `>>` の部分です．つまり，"12 3" は `x3::int_` でパースすると, `12` までしかマッチしません．`x3::int_ >> x3::int_` とすることで，スペースがスキップされます．

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

#include <iostream>
#include <string>


int main()
{
  namespace x3 = boost::spirit::x3;

  std::string src{ "( 123.4 )" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);
  double result;
  auto parser = x3::lit("(") >> x3::double\_ >> x3::lit(")");
  bool success = x3::phrase\_parse(first, last, parser, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

```

ちなみに，`x3::lit("(") >> x3::double_ >> x3::lit(")")` の部分ですが，`operator<<` の引数の内，片方がパーサであれば，`char const*` から暗黙変換が働くので， `"(" >> x3::double_ >> ")"` と書くことが出来ます．

コンビネータは他にもあります．

- `|`
  - `a | b` で，`a` にマッチするか `b` にマッチするか
  - `a` を先に試すので，両方にマッチする場合でも `a` にマッチしたことになる (PEG の特徴ですね)
  - 返り値は `boost::variant<a, b>` です．`a` と `b` が同じ型を返す場合はその型を返します
- `>`
  - `>>` とほぼ同じです．
  - `a >> b` は `a` にマッチして `b` にマッチしなかった場合，`a` の前にバックトラックします.
  - `a > b` はその場合，即座にパース失敗を通知します．
- `*`
  - `*a` という形で使う
  - `a` の 0 回以上の繰り返し
  - 返り値は `std::vector<a>`
- `+`
  - `+a` という形で使う
  - `*` の一回以上繰り返し版
- `-`
  - `-a` という形で使う
  - `a` が来ても来なくても良いというパーサ
  - 返り値は `boost::optional<a>`

...

`>` と `>>` の違いはわかりにくいですね．

`(x3::lit("(") >> ")") | ("(" >> x3::int_ >> ")")` に `"(123)"` を食わせると，`|` の後半部分にマッチしてくれます．
一方, `>>` を `>` に置換えた場合，ソース先頭の`"("` が`x3::lit("(")` にマッチするにもかかわらず，その直後に`")"` が来ていないため，その時点でエラーを通知してしまいます．

## 一旦むすび

とりあえず最も基本的な部分をまとめてみました．

ここまでは `Qi` と同じなんですよね．

セマンティックアクションや `on_error` などの扱いががっつり変わっているようなので，一旦ここで切って，それぞれ調べてからまとめたいと思います．
何か間違い等あればぜひご指摘お願いします．

---

---


↗ agatan blog ↗

#C++