【C++ Advent Calendar 2016 13日目】C++ で楽しく Expression Templates しよう

C++ Advent Calendar 2016 13日目の記事です。
13日目が空いてるようなのでちょっと Expression Templates というマニアックなネタでも。
まあ C++ プロの方なら Expression Templates なんて余裕ですよね。

[注意]

本記事のコードは基本的には C++14 に準じているので、自環境で試したい場合は注意してください。

[Expression Templates とは]

Expression Templates とは wikibooks から引用すると

C/C++ において数学的な式を評価するありふれたやり方として、関数中に式をラップし、その関数ポインタを渡して、入力された数値群に対して適用するというものがある。この方法では、関数呼び出しと一時オブジェクト生成のオーバーヘッドが生じる。また、ソース中の式の位置が呼び出し元から非常に離れていることも頻繁であり、可読性と保守性に悪影響を与える。式テンプレート(Expression template)は、式をその場に展開することによって、関数ポインタを不要にし、式と呼び出し元をまとめることで問題を解決する。
式テンプレートには再帰的な型の合成(Recursive Type Composition)が用いられている。再帰的な型の合成では、少量のコードから複雑な型の階層を生じさせることができる。一方向の再帰的な型の合成では線形な型リスト(Type List)が生成される。二方向の再帰的な型の合成は二項式に対して有用であり、以下の例で用いている。メタプログラミングテクニックはデータのように型を合成することを可能にする。違いは、メタプログラムはコンパイル時に動作すること、またそれゆえデータではなく型に対してはたらくことだけである。

参照：More C++ Idioms/式テンプレート(Expression-template) - Wikibooks)

なるほどよくわからん。
と、言うことでこういう概念はすっ飛ばして、実際にコードを書いていってみます。
ちなみにこの記事は『Expression Templates とはなんぞやを解説する記事』ではなくて『C++14 でオレオレ Boost.Lambda を実装する』という記事になります。

[Boost.Lambda/Phoenix]

実際にコードを書いていく前に少し Boost.Lambda と Boost.Phoenix を解説します。
Boost.Lambda と Boost.Phoenix はまさに Expression Templates を利用して『ラムダ式(のようなもの)を定義するため』につくられたライブラリです。
ちなみに Boost.Lambda と Boost.Phoenix の2種類のライブラリが存在するがここでは Boost.Phoenix について説明します。
Boost.Phoenix は『プレースホルダ』と呼ばれるものを利用して式を定義していきます。

// この argN というのがプレースホルダになる
// このプレースホルダはあとから評価した時の引数に着替えられる
auto plus = arg1 + arg2 * arg3;

// この時に arg1 は第一引数、arg2 は第二引数…という感じに置き換えられ
// 最終的には 1 + 2 * 3 という式が評価される
plus(1, 2, 3);   // 7

このプレースホルダは何かというと単なる関数オブジェクトになり

arg1(1, 2, 3); // 1
arg2(1, 2, 3); // 2
arg3(1, 2, 3); // 3

という風に『第n番目の引数を返す』という挙動になります。
また、この他にも

// 値を返すだけの関数オブジェクトを返す
auto _42 = val(42);
// 引数の値を返すだけ
_42();     // 42

という関数オブジェクトを返す val() という関数も存在します。
この関数オブジェクトも先ほどのプレースホルダと組み合わせて使用できます。

// 関数オブジェクトから演算子を使って式を組み立てていく
auto expr = arg1 + arg2 * val(42)
expr(1, 2);   // 85

こんな感じで Boost.Phoenix にはいろいろな関数オブジェクトが用意されており、それを組み合わせて式を定義していく感じになります。
ここで注意するのはすべて『関数オブジェクト』として扱うということです。
この点はかなり重要なので覚えておくとよいです。
それでは実際にこのような関数オブジェクトを実装してみます。

[val() 定義する]

まずは比較的な簡単な val() の定義から。
まあこれは単に値を保持して返すだけのオブジェクトになります。

template<typename T>
struct holder{
    auto
    operator ()(...) const{
        return value;
    }

    T value;
};

template<typename T>
holder<T>
val(T t){
    return {t};
}

auto result = val(42)();

まあ値を保持する holder クラスを用意して、それを生成するための val() 関数をヘルパ関数として定義してるだけですね。
この実装のキモとしては『実際の関数オブジェクトとして定義するクラス』と『その関数オブジェクトを返す関数』をわけて考えてることです。
これにより使用する側はクラステンプレートを意識する必要がありません。
あ、あと operator () が『可変長引数』を受け取っているのもポイントです。
これはあとから説明します。
ちなみに本筋とは関係ないところでコード量が増えてしまうので rvalue reference は省略して書いていきます。
まあ本物の C++ なら rvalue reference に対応するなど容易いはず

[プレースホルダオブジェクトを定義する]

次はプレースホルダです。
val() と比較してちょっと複雑ですが、そこまで難しくはないです。

template<std::size_t Index>
struct placeholder{
    template<typename... Args>
    auto
    operator ()(Args... args) const{
        // n番目の引数を受け取る実装に tuple を利用する
        return std::get<Index>(std::make_tuple(args...));
    }
};

const auto arg1 = placeholder<0>{};
const auto arg2 = placeholder<1>{};
const auto arg3 = placeholder<2>{};

arg1(1, 2, 3);    // 1
arg2(1, 2, 3);    // 2
arg3(1, 2, 3);    // 3

こちらは operator () の引数を可変長テンプレート引数で受け取って std::tuple と std::get を利用して『任意の引数値を返す』という関数オブジェクトになっています。
また、これも『placeholder クラス』と『arg1, arg2... オブジェクト』と切り分けて実装しています。
テンプレートを使用することでこういう『連番』のオブジェクトも比較的簡単に定義することが出来ますね。

[operator+ を定義]

さて、最後に関数オブジェクトを演算するための operator + を定義します。

template<typename L, typename R>
struct plus{
    template<typename... Args>
    auto
    operator ()(Args... args) const{
        return left(args...) + right(args...);
    }

    L left;
    R right;
};

template<typename L, typename R>
plus<L, R>
operator +(L left, R right){
    return {left, right};
}

まず、operator + を定義し、その左辺値と右辺値を保持するクラスを定義します。
そして operator () ではその『左辺値と右辺値を評価』します。
ここがポイントですね。
つまり

関数オブジェクト + 関数オブジェクト

という式は

関数オブジェクト(引数) + 関数オブジェクト(引数)

という風に評価されます。
このように関数オブジェクトが再帰的に評価されることで arg1 や val などの結果が最終的には『+ 演算子として』処理されます。
はい、ここがポイントですね。
これにより

arg1 + arg2 + val(42) + arg1;

みたいな連続した式も問題なく展開されます。
この時にクラスが保持してる値が『関数オブジェクト』か『そうでない』かがキモになってきます。
今回定義した operator + は左辺値と右辺値が『関数オブジェクトを受け取ること』を想定しているので『operator ()』で評価します。
しかし、先ほど定義した val() の holder クラスは関数オブジェクトではなくて『値』を保持しているため『評価しないで』そのままの値を返します。
基本的にはこれの応用で他の演算子も定義すればおっけーです。

[完成]

以下が完成形になります。

#include <tuple>
#include <iostream>

namespace lambda{

template<typename T>
struct holder{
    auto
    operator ()(...) const{
        return value;
    }

    T value;
};

template<typename T>
holder<T>
val(T t){
    return {t};
}


template<std::size_t Index>
struct placeholder{
    template<typename... Args>
    auto
    operator ()(Args... args) const{
        return std::get<Index>(std::make_tuple(args...));
    }
};

const auto arg1 = placeholder<0>{};
const auto arg2 = placeholder<1>{};
const auto arg3 = placeholder<2>{};


template<typename L, typename R>
struct plus{
    template<typename... Args>
    auto
    operator ()(Args... args) const{
        return left(args...) + right(args...);
    }

    L left;
    R right;
};

template<typename L, typename R>
plus<L, R>
operator +(L left, R right){
    return {left, right};
}

}

int
main(){
    auto expr = lambda::arg1 + lambda::arg2;
    std::cout << expr(4, 2) << std::endl;

    auto plus3 = lambda::arg1 + lambda::val(3);
    std::cout << plus3(4) << std::endl;

    return 0;
}

演算子は ADL で呼び出してるので namespace を追加してます。
とりあえず、これで完成ですね！
Expression Templates という概念はわかりづらいと思いますが、実際はこんな感じにパーツを組み合わせて式をつくっていくと考えればわかりやすいと思います。
C++11/14 でかなり実装も簡単になりましたしね。
また C++11 で言語レベルでラムダ式は追加されましたが、

filter(list, [](auto n){ return n < 0; });

よりも

filter(list, arg1 < val(0));

みたいに今回つくったラムダ式を使ったほうがコードがすっきりすると思います。
これは便利ですね。
ではみなさん、良いお年をー。

[これで終わりと思った？]

残念！まだ終わりではありません！！！
ここからが本番になります。

[C++14 で実装されたと多相ラムダと戻り値型の型推論]

さて、C++14 では新たに引数型を推論する多相ラムダと戻り値型を推論する強力な機能が追加されました。

[多相ラムダ]

ラムダ式の引数型を auto にすることで関数テンプレートのように型推論を行ないます。

// 引数型に依存することなくラムダ式を定義することができる
auto plus = [](auto a, auto b){
    return a + b;
};

plus(1, 2);           // 3
plus(3.14f, 53.24f);  // 56.38
plus(3.14f, 42);      // 45.14
plus(3.14f, 42);      // "homumami"

このように引数型に依存することなくラムダ式を定義することが出来ます。
多相ラムダを受け取ることができる型がほしいよね

[戻り値型の型推論]

C++14 では戻り値型を auto とすることでコンパイラが式から型推論を行ってくれます。

template<typename T, typename U>
auto
plus(T a, U b){
    // a + b の結果の型を推論してくれる
    return a + b;
}

plus(1, 2);           // 3
plus(3.14f, 53.24f);  // 56.38
plus(3.14f, 42);      // 45.14
plus(3.14f, 42);      // "homumami"

C++14 以前では戻り値型 decltype() などを使用する必要がありましたが、C++14 ではそれすら必要なくなりました。

// C++11 時代は decltype() で戻り値型を定義する必要があった
template<typename T, typename U>
auto
plus(T a, U b)
->decltype(a + b){
    // a + b の結果の型を推論してくれる
    return a + b;
}

decltype() を使用した場合は『関数を定義するときに型が決定されてる必要』があったんですが、これにより『関数内で定義された型』も返すことができるようになりました。

// 関数内で定義したローカルクラスを返すこともできる
auto
make_homu(){
    struct person{
        std::string name;
        int age;
    };
    return person{ "homu", 14 };
}

auto data = make_homu();
data.name;     // "homu"
data.age;      // 14

ただし、次のように『実行時によって異なる型を返す』ことは出来ないので注意してください。

auto
func(int flag){
    // Error: 同じ型を返さなければならない
    if( flag ){
        return 0;
    }
    else {
        return "Error";
    }
}

[つまり]

もうお気づきの方もいると思いますが、これにより『ラムダ式』をそのまま返すことができるようになりました。

// C++ でクロージャっぽいものを定義
auto
counter(){
    int value = 0;
    // キャプチャした変数を書き換える場合は mutable を付属させる
    return [=]() mutable{
        value += 1;
        return value;
    };
}

count();    // 1
count();    // 2
count();    // 3

と、いうことで先ほどつくったプレースホルダなどをラムダ式を使って書き換えていきましょう

[val() 定義する 2]

まずは val から。
これは引数をそのまま返すラムダ式を定義するだけなので簡単ですね。

template<typename T>
auto
val(T t){
    return [=](...){
        return t;
    };
}

はい、先ほど定義した holder クラスは綺麗サッパリなくなって関数1つだけになりました。
すごいすっきりしましたね。

[プレースホルダオブジェクトを定義する 2]

続けてプレースホルダも定義してみます。

template<std::size_t Index>
auto
placeholder(){
    return [](auto... args){
        return std::get<Index>(std::make_tuple(args...));
    };
}

const auto arg1 = placeholder<0>();
const auto arg2 = placeholder<1>();
const auto arg3 = placeholder<2>();

はい、この通り placeholder クラスではなくて placeholder 関数になりました。
また、多相ラムダを使用することで template も省略出来ます。
こちらも実装がすっきりしましたね。

[operator+ を定義 2]

最後に operator + ですね。
これも簡単に定義できます。

template<typename Left, typename Right>
auto
operator +(Left left, Right right){
    return [=](auto... args){
        return left(args...) + right(args...);
    };
}

完璧ですね…。

[まとめ]

と、言うことでまとめるとこんなコードになります。

#include <tuple>

namespace lambda{

template<typename T>
auto
val(T t){
    return [=](...){
        return t;
    };
}

template<std::size_t Index>
auto
placeholder(){
    return [](auto... args){
        return std::get<Index>(std::make_tuple(args...));
    };
}

const auto arg1 = placeholder<0>();
const auto arg2 = placeholder<1>();
const auto arg3 = placeholder<2>();

template<typename Left, typename Right>
auto
operator +(Left left, Right right){
    return [=](auto... args){
        return left(args...) + right(args...);
    };
}

}   // namespace lambda

#include <iostream>

int
main(){
    auto expr = lambda::arg1 + lambda::arg2;
    std::cout << expr(4, 2) << std::endl;

    auto plus3 = lambda::arg1 + lambda::val(3);
    std::cout << plus3(4) << std::endl;
    return 0;
}

どうでしょう。
最初にクラスを使って実装したコードに比べてだいぶすっきりしたと思いませんか？
Expression Templates の話どこに行ったんだって感じですよね。
まあでも結果的に C++14 だとこんなコードが書けるようになるんですよ。
面白いですよね。
ちなみに C++14 + ラムダ式で実装した場合の欠点としては『constexpr』として定義できないことです。
最初にクラスを使って実装した場合は戻り値型に constexpr をつければコンパイル時に評価することが出来ます。
これは大変強力なのでどっちで実装するべきなのかは悩みどころですね…。
ただ、C++17 ではラムダ式が constexpr が定義できるらしいのでそこもカバーできるようになると思います。
と、言うことで本記事は『Expression Templates を解説する』記事でもなく『オレオレ Boost.Lambda/Phoenix を実装する』記事でもなく『C++14 の多相ラムダと戻り値型の auto が素晴らしい』という記事になります。
それではメリークリスマス。