Expression Templates Demystified: Part 2

In this article, we would see how the use of templates can simplify and generalize the Expression Functors code, and improve performance by eliminating virtual functions.

In the example from the previous segment of this article, the Expression abstract base class represented the family of all types that could be used to represent different kinds of expressions. Two specific classes, Variable and Constant, represented the leafs of an expression tree - numeric literals and single variable names. These could be combined to form other expressions - generally represented by the ComplexExpression class. All these classes implemented the interface defined by the Expression abstract base class.

We now plan to switch from dynamic polymorphism to template driven static polymorphism. For example, given classes with a common interface but without a common base class, like the ones below:

Hide line numbersShow line numbers

    1 struct Foo {
    2     void bar() {
    3         // implementation
    4     }
    5 };
    6 
    7 struct Foo2 {
    8     void bar() {
    9         // implementation
   10     }
   11 };

we can wrap them using a class template that has a similar interface as these:

Hide line numbersShow line numbers

    1 template<class F>
    2 struct AllFoo {
    3     AllFoo(F& f) : f_(f) {}
    4 
    5     void bar() {
    6         f_.bar();
    7     }
    8 };

This enforces that AllFoo can only be instantiated with such classes which have the bar() method in their public interface. Thus we write the following alternate definitions:

Hide line numbersShow line numbers

    1 template<class E>
    2 struct Expr {
    3     Expr(E& e) : e_(e) {
    4     }
    5 
    6     double operator() (double d) {
    7         return e_(d);
    8     }
    9 
   10     E e_;
   11 };

Here Expr is a class that can encapsulate all expression objects, like the ones of type Constant or Variable below.

Hide line numbersShow line numbers

    1 struct Constant {
    2     Constant(double d) : d_(d) { }
    3     Constant(int d) : d_(d) { }
    4     double operator() (double) {
    5         return d_;
    6     }
    7 
    8     double d_;
    9 };
   10 
   11 
   12 struct Variable {
   13     double operator() (double d) {
   14         return d;
   15     }
   16 };

Finally, a class to represent non-terminal, complex expressions:

Hide line numbersShow line numbers

    1 template<class E1, class E2, class Op>
    2 struct ComplexExpr {
    3     ComplexExpr(Expr<E1> l, Expr<E2> r) : l_(l), r_(r) {
    4     }
    5 
    6     double operator() (double d) {
    7         return Op::apply(l_(d), r_(d));
    8     }
    9 
   10     Expr<E1> l_;
   11     Expr<E2> r_;
   12 };

We have just carried over the definition of the ComplexExpression class from the previous article and made it into a template class. The operator classes like Add, Subtract, Multiply and Divide should continue to work unchanged. Guess what, we just have to define the operator overloads (for +, -, * and /) and we will be done with defining our framework of algebraic expression.

Now, we would want to write expressions such as:

Variable x;
cout << (x+3)(2); // prints 5
cout << ((x*x+3)*(x+3))(2); // prints 35

In the above, x is a Variable, 3 should generate a Constant, x + 3 should result in a ComplexExpr<Variable, Constant>. Further, x*x is a ComplexExpr<Variable, Variable> and (x*x+3)*(x+3) is a ComplexExpr<ComplexExpr< ComplexExpr<Variable, Variable>, Constant>, ComplexExpr<Variable, Constant> >. One can trace the template parameter types as sub-trees of the class template ComplexExpression.

Clearly, to write an expression like x+3, we need an overload of operator+ between a Variable and an integer. To write an expression like (x*x+3)*(x+3) - we need an operator* between two ComplexExpressions. To write something like, x+Constant(3), we need an overload of operator+ between Variable and Constant. Now, just as we defined the basic operators on Expression in the previous article, we could do the same on the Expr class template here, instead of overloading each operator for different combinations of types. For example:

Hide line numbersShow line numbers

    1 template<class E1, class E2>
    2 Expr<ComplexExpr<Expr<E1>, Expr<E2>, Add> > operator+ (E1 e1, E2 e2) {
    3     typedef ComplexExpr<Expr<E1>, Expr<E2>, Add> ExprType;
    4     return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<E2>(e2)) );
    5 }

The other operators are not very difficult to write, following the above code. However, turns out that while these do take care of operators between complex expressions as well as Variables and Constants, they cannot handle real number or integer literals. To handle real number literals, we define the following overload pairs for each operator.

Hide line numbersShow line numbers

    1 template<class E1>
    2 Expr<ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> > operator* (E1 e1, double d) {
    3     typedef ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> ExprType;
    4     return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<Constant>(Constant(d))) );
    5 }
    6 
    7 template<class E1>
    8 Expr<ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> > operator* (double d, E1 e1) {
    9     typedef ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> ExprType;
   10     return Expr<ExprType>( ExprType(Expr<Constant>(Constant(d)), Expr<E1>(e1)) );
   11 }

These take care of all cases - except for a small glitch which we can pepare to live with. We can write such expressions as:

Variable x;
cout << (x+3.0)(2); // prints 5
cout << ((x*x+3.0)*(x+3.0))(2); // prints 35

but not ones like:

Variable x;
cout << (x+3)(2); // prints 5
cout << ((x*x+3)*(x+3))(2); // prints 35

If you have to be able to do this, add additional overloads like:

Hide line numbersShow line numbers

    1 template<class E1>
    2 Expr<ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> > operator* (E1 e1, int d) {
    3     typedef ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> ExprType;
    4     return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<Constant>(Constant(d))) );
    5 }
    6 
    7 template<class E1>
    8 Expr<ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> > operator* (int d, E1 e1) {
    9     typedef ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> ExprType;
   10     return Expr<ExprType>( ExprType(Expr<Constant>(Constant(d)), Expr<E1>(e1)) );
   11 }

As it should be already apparent - there are no objects allocated on free store, no reference counted proxy wrappers, and a fair bit of compile-time type computation and call dispatching - this results in significant savings in the runtime costs of the program, apart from the obvious cut in the number of lines of code. The basic philosophy of the template based program has not changed from the non-template version - it uses functional composition involving the function call operator, and operator overloading to support naturally combining simple expressions into arbitrarily complex expressions. However, the use of templates allows a fair bit of this work to be done at compile time. This is all that is there to Expression templates. You can put together the expression framework using code given here and use the following function to test your code.

Hide line numbersShow line numbers

    1 int main()
    2 {
    3     Variable x;
    4 
    5     cout << ((2.0*x*x + 3.0*x + 3.0)*(2.0*x*x + 3.0*x + 3.0))(2) << endl;
    6     cout << integrate((2.0*x*x + 3.0*x + 3.0), 0, 1) << endl;
    7     cout << integrate((2.0*x*x + 3.0*x + 3.0)*(2.0*x*x + 3.0*x + 3.0), 0, 1) << endl;
    8     cout << integrate((x/(1.0+x)), 0, 1) << endl;
    9     cout << integrate(x*x, 0, 7) << endl;
   10 
   11     return 0;
   12 }
   13 

If you have any trouble understanding and compiling the code, drop me a message.

References

1. Todd Veldhuizen: Expression Templates
   http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.html
   
2. Expression Templates synopsis on More C++ Idioms
   http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Expression-template
   
3. Angelika Langer: Expression Templates - Introduction
   http://www.angelikalanger.com/Articles/Cuj/ExpressionTemplates/ExpressionTemplates.htm