式テンプレート(Expression-template)

意図

関数のパラメータとして数学的な式を渡す。

別名

動機

C/C++ において数学的な式を評価するありふれたやり方として、関数中に式をラップし、その関数ポインタを渡して、入力された数値群に対して適用するというものがある。この方法では、関数呼び出しと一時オブジェクト生成のオーバーヘッドが生じる。また、ソース中の式の位置が呼び出し元から非常に離れていることも頻繁であり、可読性と保守性に悪影響を与える。式テンプレート(Expression template)は、式をその場に展開することによって、関数ポインタを不要にし、式と呼び出し元をまとめることで問題を解決する。

解法とサンプルコード

式テンプレートには再帰的な型の合成(Recursive Type Composition)が用いられている。再帰的な型の合成では、少量のコードから複雑な型の階層を生じさせることができる。一方向の再帰的な型の合成では線形な型リスト(Type List)が生成される。二方向の再帰的な型の合成は二項式に対して有用であり、以下の例で用いている。メタプログラミングテクニックはデータのように型を合成することを可能にする。違いは、メタプログラムはコンパイル時に動作すること、またそれゆえデータではなく型に対してはたらくことだけである。

#include <iostream>
#include <vector>

struct Var {
	double operator () (double v) { return v; }
};

struct Constant {
	double c;
	Constant (double d) : c (d) {}
	double operator () (double) { return c; }
};

template <class L, class H, class OP>
struct DBinExp {
	L l_;
	H h_;
	DBinExp (L l, H h) : l_ (l), h_ (h) {}
	double operator () (double d) { return OP::apply (l_ (d), h_(d)); }
};

struct Add {
	static double apply (double l, double h) { return l + h; }
};

template <class E>
struct DExpr {
      E expr_;
      DExpr (E e) : expr_ (e) {}
	  double operator() (double d) { return expr_(d);  }
};

template <class Itr, class Func>
void evaluate (Itr begin, Itr end, Func func) 
{
	for (Itr i = begin; i != end; ++i)
		std::cout << func (*i) << std::endl;
}

int main (void)
{
	typedef DExpr <Var> Variable;
	typedef DExpr <Constant> Literal;
	typedef DBinExp <Variable , Literal, Add> VarLitAdder;
	typedef DExpr <VarLitAdder> MyAdder;

	Variable v ((Var()));
	Literal l (Constant (50.00));
	VarLitAdder vl_adder(v, l);
	MyAdder expr (vl_adder);

	std::vector <double> a;
	a.push_back (10);
	a.push_back (20);

	evaluate (a.begin(), a.end(), expr); // これは (50.00 + x) だがそう見えない。

	return 0;
}

ここでは Composite デザインパターンとの類推が有用である。テンプレート DExpr は Composite パターンにおける抽象基本クラスとみなすことができる。共通点をインタフェースとしてまとめている。式テンプレート中では、共通インタフェースはオーバーロードされた関数呼び出し演算子である。DBinExp は実際の複合物(composite)であり、また Add のインタフェースを DExpr に適合させるアダプタでもある。 Constant と Var は末端の節点を表す二つの異なる型である。これらもまた、DExpr のインタフェースに適合している。DExpr は DBinExp, Constant, Var の複雑さを統一されたインタフェースの裏側に隠蔽し、それらが連携して動くようにしている。任意の二項演算子で Add を置き換えることができる。例えば、Divide や Multiply などである。

上記の例では、どのように再帰的な型がコンパイル時に生成されるかが示されていない。expr も全く数学的な式に見えないが、それは確かに数学的な式なのである。以下のコードで、メタプログラミングを使用することによりどのように型が再帰的に合成されるかを示す。

template<class A, class B>
DExpr<DBinExp<DExpr<A>, DExpr<B>, Add> >
operator + (DExpr<A> a, DExpr<B> b)
{
  typedef DBinExp <DExpr<A>, DExpr<B>, Add> ExprT;
  return DExpr<ExprT>(ExprT(a,b));
}

上のオーバーロードされた + 演算子は二つのことを行う。構文糖を提供し、また(コンパイラの制限範囲内で)再帰的な型の合成を可能とする。これにより、以下のように evaluate の呼び出しを置き換えることが可能である。

evaluate (a.begin(), a.end(), v + l + v); 
/// これは (2*x + 50.00) であり、確かに数学的な式のように見える。

既知の利用

Blitz++ library
boost::uBLAS

References

Expression Templates - Klaus Kreft & Angelika Langer
Expression Templates - Todd Veldhuizen
Faster Vector Math Using Templates - Tomas Arce

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

式テンプレート(Expression-template)

意図

別名

動機

解法とサンプルコード

既知の利用

関連するイディオム

References