右上➚

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

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

C++ コンパイラ LLVM

C++ のテンプレートがなぜ必要で，どんな構文・種類のものがあるかについては前回までにまとめました。
というわけで次は C++ ではテンプレートという機能を使用するとどんなバイナリが生成されるのかについて見ていきます。
C++ のテンプレートの強力さとか勘所みたいなものを把握するために非常に重要な部分なので、覚えておくとよいと思います。

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

早速ですが、実際に C++ でテンプレートを使っているコードをコンパイルしてみます。
アセンブリよりも LLVM IR のほうがわかりやすいかな？と思うので、LLVM IR を clang++ で生成させてみます。 （LLVM IR については 大学院生のためのLLVM | インフラ・ミドルウェア | POSTD あたりを読んでおくとなんとなく概念がつかめると思います。公式はLLVM Language Reference Manual — LLVM 3.9 documentation）

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

// 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 方式

  • 利点
  • 欠点
    • 実行時にやることが増えるのでオーバヘッドがある

C++ 方式

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

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

まとめ

C++er はみんな実行時のオーバヘッドが嫌いです。テンプレートは、今までに紹介してきた使用法からは想像も出来ないほど豊富な計算を、コンパイル時にすべて行うことが出来ます。実行時のオーバヘッドなしで。
コンパイル時にテンプレートの解決が終わるということは、強力な最適化が望めるということでもあります。つまり、実行時のキャストといったわかりやすいオーバヘッド以上に、実行速度には差が生まれるでしょう。

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

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

C++

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

agtn.hatenablog.com

アウトライン

  • テンプレートの種類と構文
  • クラステンプレート
  • 関数テンプレート
  • メンバテンプレート
  • エイリアステンプレート(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++でデータ型にとらわれずにコードを書くことを可能にする機能であり、C++においてはジェネリックプログラミングに用いられる。
テンプレート (プログラミング) - Wikipedia)より

他の静的型付きなプログラミング言語をすでに知っている場合は，すんなり入りやすいかもしれません。
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 についても触れていければと思っています。

Rust のパーサコンビネータライブラリ combine を使う時の tips

Rust コンパイラ

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 of fn expr<I: Stream>(input: State<I>) -> ParseResult<I, &str> )

これは作ったパーサをジェネリックな入力に対して適用することができなくなりますが，ライブラリの利用者側としては，char のストリームといったらだいたい &str だと思うので，ぶっちゃけジェネリックじゃなくてもいいじゃんという感じです．

そしてもう一つが, ジェネリックな構造体を作って，パーサの定義をその中に閉じ込めるという方法です．
ちょっとこちらはコード例を実際に見たほうがわかりやすいと思うので後で説明します．

実験コード

というわけで，

  1. ジェネリックなパーサ
  2. &str のみを受理するパーサ
  3. ジェネリックな構造体の中に定義されたジェネリックでないパーサ

の三種類について，コンパイル時間をはかってみます．

パーサ界のハローワールド，計算機で実験してみます． まずはジェネリックなパーサです．

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 コンパイラ

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

2016/05/01 追記　

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

agatan/coco

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 表現について

コンパイラ Rust LLVM
  • 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++ プログラムのコンパイルエラーが，死ぬほど辛かったので作りました． 型を綺麗に出力するだけです． 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 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
>