C++テンプレートイディオム CRTP
C++テンプレートの有名なイディオムとして、CRTPというものがあります。 今回はそれについて。 複雑な部分特殊化みたいな話もないですし、メリットもわかりやすい良いイディオムだと思うので、ちょっとまとめておきます。 (Control キーのことをよく CTRL と書くので、CTRP とタイポしがち)
詳細はこちらを参照してください。 More C++ Idioms/奇妙に再帰したテンプレートパターン(Curiously Recurring Template Pattern) - Wikibooks)
CRTPの利点
細かい実装の話の前に、CRTPを使うと何がうれしいのかを簡単に。
静的 Template Method パターンの実現_ 。これがCRTPの利点です。
Template Method パターンについてはここでは説明しませんが、大枠のアルゴリズムを共有しつつその内部で使用する実装の詳細をクラスごとに切り替えるといった目的に使われるデザインパターンです。
通常 Template Method パターンを C++ で実現しようと思うとどうしても仮想関数を使うことになると思います。これによって実行時のオーバヘッドがかかってしまいます。 Template Method パターンは、いわゆるクラスベースの動的なポリモーフィズムを必要としないクラスであっても、アルゴリズムの共有やボイラープレートコードの削減に非常に有用なパターンです。 これを静的に実現するのが CRTP の目的なのです。
実装
CRTP とは、その名の通り、奇妙に再帰したテンプレートのパターンのことです。 情報量0の文章ですね。実際のコードも見たほうがわかりやすいと思います。
以下に、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++ のテンプレートの実装
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++11〜)
- 変数テンプレート(C++14〜)
- まとめと今後
テンプレートの種類と構文
C++ のテンプレートは,大きく 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 について、2つの引数のうち、大きい方を返す」関数です。
明示的に 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++においてはジェネリックプログラミングに用いられる。
テンプレート (プログラミング) - 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 のパーサコンビネータライブラリの一つである Marwes/combine: A parser combinator library for Rust を使ってみています.
詳しい使い方はきちんとしたドキュメントがあるのでそちらを参照してください.
ざっくりいうと Haskell の parsec: Monadic parser combinators | Hackage の Rust 版という感じです.
(ちなみに私も combine を参考に C++ でパーサコンビネータを作ってみたりしました. ) agtn.hatenablog.com
で、このライブラリ、とてもジェネリックなコードで書かれているので、かなりコンパイル時間が増加します… (Boost.Spirit 系に近いです. コンパイルエラーなどは遥かに読みやすいのであまり困ることはないですが)
パーサを書いている時にはテストは頻繁に行いたいので,ちょっとコンパイルがおそいのはつらい.
なにか解決策はないかなぁと思っていたら本家に issue がたっていました.
Extremely long compile times · Issue #21 · Marwes/combine
今回この issue にかかれていた内容を検証してみたので,ここでまとめておこうと思います.
結論
パーサの定義を,ジェネリックな構造体のメソッドとして定義するとコンパイル時間が大幅に短くなる
方法
まずはじめに言われているのは,入力ストリーム型をI: Stream<Item=char>
から &str
にしてしまうという方法です.
(It might be possible to specialize the parsers directly as well, say
fn expr(input: State<&str>) -> ParseResult<Expr, &str>
instead offn expr<I: Stream>(input: State<I>) -> ParseResult<I, &str>
)
これは作ったパーサをジェネリックな入力に対して適用することができなくなりますが,ライブラリの利用者側としては,char
のストリームといったらだいたい &str
だと思うので,ぶっちゃけジェネリックじゃなくてもいいじゃんという感じです.
そしてもう一つが, ジェネリックな構造体を作って,パーサの定義をその中に閉じ込めるという方法です.
ちょっとこちらはコード例を実際に見たほうがわかりやすいと思うので後で説明します.
実験コード
というわけで,
の三種類について,コンパイル時間をはかってみます.
パーサ界のハローワールド,計算機で実験してみます. まずはジェネリックなパーサです.
use combine::*; use combine::primitives::Stream; pub fn integer<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { many1::<Vec<_>, _>(digit()) .map(|is| is.into_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64))) .parse_state(input) } pub fn factor<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { between(char('('), char(')'), parser(expr)).or(parser(integer)).parse_state(input) } pub fn term<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { let op = char('*').or(char('/')).map(|c| { move |lhs, rhs| match c { '*' => lhs * rhs, '/' => lhs / rhs, _ => unreachable!(), } }); chainl1(parser(factor), op).parse_state(input) } pub fn expr<I>(input: State<I>) -> ParseResult<i64, I> where I: Stream<Item = char> { let op = char('+').or(char('-')).map(|c| { move |lhs, rhs| match c { '+' => lhs + rhs, '-' => lhs - rhs, _ => unreachable!(), } }); chainl1(parser(term), op).parse_state(input) } pub fn parse<I>(input: I) -> Result<(i64, I), ParseError<I>> where I: Stream<Item = char> { parser(expr).parse(input) }
それぞれの関数が一つのパーサの役割を担います.それぞれのパーサが独立していて,それぞれ別々に型変数を導入しています.
次に &str
だけを受け取るパーサです.これは上記のジェネリックなパーサの,型変数を &str
に置き換えるだけなのでとても簡単です.
一部だけ掲載します.
pub fn expr(input: State<&str>) -> ParseResult<i64, &str> { let op = char('+').or(char('-')).map(|c| { move |lhs, rhs| match c { '+' => lhs + rhs, '-' => lhs - rhs, _ => unreachable!(), } }); chainl1(parser(term), op).parse_state(input) } pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> { parser(expr).parse(input) }
最後が,ジェネリックな構造体のメソッド中に,ジェネリックでないパーサを定義して閉じ込める方法です.
use combine::*; use combine::primitives::Stream; use std::marker::PhantomData; truct P<I>(PhantomData<fn(I) -> I>); impl<I> P<I> where I: Stream<Item = char> { pub fn integer(input: State<I>) -> ParseResult<i64, I> { many1::<Vec<_>, _>(digit()) .map(|is| is.into_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64))) .parse_state(input) } pub fn factor(input: State<I>) -> ParseResult<i64, I> { between(char('('), char(')'), parser(P::<I>::expr)) .or(parser(P::<I>::integer)) .parse_state(input) } pub fn term(input: State<I>) -> ParseResult<i64, I> { let op = char('*').or(char('/')).map(|c| { move |lhs, rhs| match c { '*' => lhs * rhs, '/' => lhs / rhs, _ => unreachable!(), } }); chainl1(parser(P::<I>::factor), op).parse_state(input) } pub fn expr(input: State<I>) -> ParseResult<i64, I> { let op = char('+').or(char('-')).map(|c| { move |lhs, rhs| match c { '+' => lhs + rhs, '-' => lhs - rhs, _ => unreachable!(), } }); chainl1(parser(P::<I>::term), op).parse_state(input) } } pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> { parser(P::expr).parse(input) }
言葉で説明すると難しいのですが,型変数を導入する部分を構造体の定義部分だけにしてあげることで,型変数をそれぞれのパーサが別々に導入する必要がなくなっています.
コードも割りとすっきりしますね.
結果
上記をコードを cfg
を使ってコンパイル時に切り替えながらコンパイルしてみました.
本当はきちんと繰り返し計測すべきですが,ちょっとサボっています.まぁ何度実行してもだいたい同じくらいになったので許してください.
実装方法 | コンパイル時間 |
---|---|
ジェネリック | 2.666s |
&str |
1.70s |
構造体内で定義 | 1.55s |
このような結果になりました.
つまり,先ほどの issue で述べられているコンパイル時間の短縮方法はかなり効き目があるということですね.
構造体の中に閉じ込める方法が,&str
しか受理しないようにする方法よりもはやくコンパイルできるのは意外でした… 参照を引数にとると暗黙に lifetime 変数が導入されたと記憶しているので,その関係なのかな?
構造体内で定義する方法では,&str
以外の入力ストリーム型を受けつけることを可能にしつつもコンパイル時間を短縮できるということで,積極的にこの方式でパーサを定義するべきということがわかりました.
注意点として,構造体内で別のパーサを呼ぶときには,必ず P::term
という形ではなく,P::<I>::term
という形で呼び出すようにする必要があるようです.
きちんと明示的に指定しないと,結局型推論するはめになって意味がないということのようです.
C++ でパーサコンビネータを書きました
C++ で構文解析といえば,Boost.Spirit や yacc系などが有名ですが,どうにも使うの辛かったので作りました.
2016/05/01 追記
いろいろ更新しました.肯定先読み以外はプリミティブも実装し終わっているかと思います.
ドキュメントはまだ無いのですが,すべての機能についてテストは書いてあるので,それを見てもらえればなんとか使い方もわかるかと思います.
coco::combix
がパーサコンビネータライブラリの namespace です.
Boost.Spirit は高機能かつ高性能なんですが,かなり変態的な構文で記述する必要があり(まぁ C++ なんですけど),さらにその性能や便利さ,構文のために異常なまでにテンプレートを多用しています.私は構文解析後の構文木の構築に Boost.Variant を使ってみているのですが,Boost.Spirit と Boost.Variant の両面から,ジェネリックすぎるがゆえのコンパイルエラー爆発攻撃を食らって本当に辛いです.
そこで,Haskell の parsec や Rust の combine を参考にしつつ,C++ でパーサコンビネータを書いてみました.(実際これを使ってもコンパイルエラーは割りと発狂しますが)
例
例となるコードは agatan/coco-combix-demo においてあります.
ドキュメントもないので,なんとなく雰囲気だけコードから読み取る必要があります.(例に出ていない機能もちょいちょい実装されてしまっています.)
以下にちょっと簡略版のコードを載せてみます.ありがちな電卓です.AST を作らず直接計算しています.
#include <string> #include <iostream> #include <functional> #include <coco/combix.hpp> namespace cbx = coco::combix; using stream_type = cbx::iterator_stream<std::string::const_iterator>; cbx::parser<int, stream_type> expression(); cbx::parser<int, stream_type> number() { return cbx::expected(cbx::map(cbx::many1(cbx::digit()), [](auto&& is) { int acc = 0; for (auto i : is) { acc = acc * 10 + i; } return acc; }), "integer number"); } cbx::parser<int, stream_type> factor() { return cbx::choice( number(), cbx::between(cbx::skip(cbx::token('('), cbx::spaces()), cbx::skip(cbx::token(')'), cbx::spaces()), cbx::skip(cbx::lazy_fun(expression), cbx::spaces()))); } cbx::parser<int, stream_type> term() { auto op = cbx::map( cbx::skip(cbx::choice(cbx::token('*'), cbx::token('/')), cbx::spaces()), [](auto c) -> std::function<int(int, int)> { if (c == '*') { return std::multiplies<int>(); } else { return std::divides<int>(); } }); return cbx::chainl1(cbx::skip(factor(), cbx::spaces()), op); } cbx::parser<int, stream_type> expression() { auto op = cbx::map( cbx::skip(cbx::choice(cbx::token('+'), cbx::token('-')), cbx::spaces()), [](auto c) -> std::function<int(int, int)> { if (c == '+') { return std::plus<int>(); } else { return std::minus<int>(); } }); return cbx::chainl1(cbx::skip(term(), cbx::spaces()), op); } int main() { std::string src; std::getline(std::cin, src); auto n = number(); auto stream = cbx::range_stream(src); auto const parser = expression(); if (auto res = cbx::parse(parser, stream)) { std::cout << res.unwrap() << std::endl; } else { std::cout << cbx::to_string(res.unwrap_error()) << std::endl; } }
特徴
parsec を知っている方であれば読めるはずです...
特徴としては,多くのパーサは入力ストリームの型に依存せずに作れるようになっていることです.例えば,あらゆる入力一つを受け付け消費する any
というパーサは,入力が char
のストリームであろうと int
のストリームであろうとパースを実行できるようになっています.
本来はエラーメッセージの爆発や読みづらさを防ぐために,すべてのパーサ自体にストリームの型をひも付けたかったのですが,そうすると,any
を使うたびに,any<cbx::iterator_stream<typename std::vector<int>::const_iterator>>()
とか any<cbx::iterator_stream<std::string::const_iterator>>()
とかしなくてはなりません.これは Haskell や Rust と違って C++ の型推論が限定的であるためです.(Haskell や Rust では後でその値がどう使われているかも推論の根拠として使われます.)
そこで,パーサ自体には入力ストリームの型を指定させずに,実際にパースする部分で初めて入力ストリームの型を検査することにしました.
で,cbx::parser<int, stream_type>
はパーサを type erasure を使ってラップします.普通に使っていると簡単に cbx::expected<cbx::map_parser<cbx::many1_parser<cbx::digit_parser>, (lambda at ...)>>
型とかが出てきます(cbx::expected(cbx::map(cbx::many1(cbx::digit()), [](auto&&) {...}), "integer number")
の型です)
これを関数定義のたびに書くとか発狂してしまうので,type erasure を使って型をラップし短絡します.
ただしパフォーマンスの観点から行くとおそらく型をラップするために仮想関数を使ってしまうので,インライン展開等がきかなくなると思われます.まぁ仕方ないです.
ただ,型を膨らませすぎずに適度にラップしてやると,コンパイルエラーの内容がかなり読みやすくなるはずです.なのでなんかわからんけどエラーになるっていうときは細かくパーサを分割してラップしてやると良いかもしれません.
まとめ
あまりにもドキュメントやコメント書かなすぎてひどいですが,ちょっと構文解析したいとかっていうときに便利だと思います.
Boost.Spirit と違って普通に C++ のプログラムとして書けます.(Boost.Spirit も C++ プログラムとして書けてはいるんですが,なんかあれはあれで別の言語を覚えているような気分になってしまったので...)
あと PEG のプリミティブをまだ完全に実装していないと思います.先読みや否定先読みが出来ません.(実装します…)
Rust における return文の LLVM IR 表現について
if
文が値を返すreturn
文を持つ
以上のような特徴を持つ言語はどういう感じでコンパイルされるのか知りたくて,Rust について調べてみました.
Rust では以下の様なことが出来ます.
fn f() { let x = if cond { return None; } else { 1 }; ... }
Scala とかもできると思います.cond
が真だった場合は,x
の値を返すのではなく,関数から抜けてしまうという意味です.
これを Rust ではどんな LLVM IR に落とし込んでいるのか.
return
文がない場合
fn noreturn(x: isize) -> isize { x }
最も単純な場合です.この場合,生成される LLVM IR は,
define internal i64 @_ZN4hoge8noreturn17h811bf1a871f85432E(i64) unnamed_addr #0 { entry-block: %x = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x ret i64 %1 }
となります.
名前がマングルされていますが,上記の noreturn
関数です.
やっていることは単純で,第一引数を読み込んで返すだけです.
return
に相当する文が一つのみの場合
fn onereturn(x: isize) -> isize { let y = if x == 0 { 1 } else { x }; return x; }
実際に値を返す部分が一箇所しかない場合です.途中に分岐があっても最終的に一箇所になっていれば多分同じ結果になります.
define internal i64 @_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed_addr #0 { entry-block: %x = alloca i64 %y = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-18-, label %else-block then-block-18-: ; preds = %entry-block store i64 1, i64* %y br label %join else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %y br label %join join: ; preds = %else-block, %then-block-18- %4 = load i64, i64* %x br label %clean_ast_10_ return: ; preds = %clean_ast_10_ ret i64 %4 clean_ast_10_: ; preds = %join br label %return }
return
という BasicBlock ができています.これは return
文が現れると作られるよう?です.
で,その中では単純に x
に該当する値を返しています.
最後の return x;
文を 単純に x
に置き換えてみると,
define internal i64 @_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed_addr #0 { entry-block: %x = alloca i64 %y = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-18-, label %else-block then-block-18-: ; preds = %entry-block store i64 1, i64* %y br label %join else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %y br label %join join: ; preds = %else-block, %then-block-18- %4 = load i64, i64* %x ret i64 %4 }
となります. return
ブロックが消えていますね.なので return
文があると return
ブロックが作られる、で良さそう?
複数のパスから値を返す
fn multireturn(x: isize) -> isize { let y = if x == 0 { return -1; } else { x }; y }
さて,では最初に述べた,if
の分岐内にある return
についてです.
これは,
define internal i64 @_ZN4hoge11multireturn17had379e8ce5a18f08E(i64) unnamed_addr #0 { entry-block: %sret_slot = alloca i64 %x = alloca i64 %y = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-18-, label %else-block then-block-18-: ; preds = %entry-block store i64 -1, i64* %sret_slot br label %return else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %y br label %join join: ; preds = %else-block %4 = load i64, i64* %y store i64 %4, i64* %sret_slot br label %return return: ; preds = %join, %then-block-18- %5 = load i64, i64* %sret_slot ret i64 %5 }
こうなりました.
まず,return
文があるため?,return
ブロックが作られています.
しかし今回は,パスによって返すものが違います.(値が違うという意味ではなく,同じ変数ですらないという意味です...)
よく IR を読むと,関数の頭で %sret_slot
という名前でスタック領域を確保していることがわかります.
そして,return
ブロック内では,これを読んできて返しています.
さらに,if
文の then 節にあたる,then-block-18-
というブロックでは,%sret_slot
に値を格納して return
ブロックへジャンプしています.
else 節のあとの部分 (join
ブロック) でも同様に, %sret_slot
に値を格納して return
ブロックへジャンプしています.
まとめ
というわけで,様々な Rust コードを LLVM IR に変換して見てみた結果,複数のパスから値を返す場合は,「ローカル変数として返り値を定義し,そこに返したい値を格納してから return
に goto」という形になっていることがわかりました.
(ほとんど LLVM IR を乗っけるだけになってしまった...)
ちなみに ...
if
文の返す値をそのまま返す
fn ifreturn(x: isize) -> isize { if x == 0 { 1 } else { x } }
Rust に慣れていないとちょっとわかりにくいですが,x == 0
の場合は 1 を返し,そうでない場合は x
を返す関数です.
これは,
define internal i64 @_ZN4hoge8ifreturn17hcdaab6e376d6c95cE(i64) unnamed_addr #0 { entry-block: %sret_slot = alloca i64 %x = alloca i64 store i64 %0, i64* %x %1 = load i64, i64* %x %2 = icmp eq i64 %1, 0 br i1 %2, label %then-block-15-, label %else-block then-block-15-: ; preds = %entry-block store i64 1, i64* %sret_slot br label %join else-block: ; preds = %entry-block %3 = load i64, i64* %x store i64 %3, i64* %sret_slot br label %join join: ; preds = %else-block, %then-block-15- %4 = load i64, i64* %sret_slot ret i64 %4 }
こうなります.やっていることは上記の例たちとあまり変わりません.
しかし,return
文がないので?,return
ブロックが作られていません.が, %sret_slot
は定義されていますね...
これはどういうことなんでしょう.rustc
のコードを読むべきなのかもしれませんが,イマイチ内部処理が想像しにくいです...
普通に翻訳していったら,
let x = if x == 0 { 1 } else { x }; x
と同じ感じになる気がするので,%sret_slot
という名前が出てくる余地は無い気がするのですが...(実質同じ処理ではあります)
分岐が直接返戻値になる場合は特別扱いしているのかな?