Expression Template

Intent

To create a domain-specific embedded language (DSEL) in C++
To support lazy evaluation of C++ expressions (e.g., mathematical expressions), which can be executed much later in the program from the point of their definition.
To pass an expression -- not the result of the expression -- as a parameter to a function.

Also Known As

Motivation

Domain-specific languages (DSLs) is a way of developing programs where the problem to be solved is expressed using notation that is much closer to the domain of the problem rather than the usual notation (loops, conditionals, etc.) provided by procedural languages. Domain-specific embedded languages (DSELs) is a special case of DSLs where the notation is embedded in a host language (e.g., C++). Two prominent examples of DSELs based on C++ are the Boost Spirit Parser Framework and Blitz++ scientific computing library. Spirit provides a notation to write EBNF grammar directly into a C++ program whereas Blitz++ allows a notation to perform mathematical operations on matrices. Obviously, such notation is not provided in C++ natively. The key benefit of using such notation is that the program captures the intention of the programmer quite intuitively making the program much more readable. It reduces the development as well as maintenance costs dramatically.

So, how do these libraries (Spirit and Blitz++) achieve such a leap in the abstraction-level? The answer is -- you guessed it right -- Expression Templates.

The key idea behind expression templates is lazy evaluation of expressions. C++ does not support lazy evaluation of expressions natively. For example, in the code snippet below, the addition expression (x+x+x) is executed before the function foo is called.

int x;
foo(x + x + x); // The addition expression does not exist beyond this line.

Function foo never really knows how the parameter it receives is computed. The addition expression never really exists after its first and only evaluation. This default behavior of C++ is necessary and sufficient for an overwhelmingly large number of real-world programs. However, some programs need the expression later on to evaluate it again and again. For example, tripling every integer in an array.

int expression (int x)
{
  return x + x + x; // Note the same expression.
}
// .... Lot of other code here
const int N = 5;
double A[N] = { 1, 2, 3, 4, 5};

std::transform(A, A+N, A, std::ptr_fun(expression)); // Triples every integer.

This is the conventional way of supporting lazy evaluation of mathematical expressions in C/C++. The expression is wrapped in a function and the function is passed around as a parameter. There is overhead of function calls and creation of temporaries in this technique, and quite often, the location of the expression in the source code is quite far from the call site, which adversely affects the readability and maintainability. Expression templates solve the problem by inlining the expression, which eliminates the need for a function pointer and brings together the expression and the call site.

Solution and Sample Code

Expression templates use the Recursive Type Composition idiom. Recursive type composition uses instances of class templates that contain other instances of the same template as member variables. Multiple repetitive instantiation of the same template gives rise to an abstract syntax tree (AST) of types. Recursive type composition has been used to create linear Type lists as well as binary expression trees used in the following example.

#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 DBinaryExpression {
  L l_;
  H h_;
  DBinaryExpression (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 DExpression {
  E expr_;
  DExpression (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 DExpression <Var> Variable;
  typedef DExpression <Constant> Literal;
  typedef DBinaryExpression <Variable , Literal, Add> VarLitAdder;
  typedef DExpression <VarLitAdder> MyAdder;

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

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

  // It is (50.00 + x) but does not look like it.
  evaluate (a.begin(), a.end(), expr);

  return 0;
}

An analogy to the Composite design pattern is useful here. The template DExpression can be considered as the abstract base class in the Composite pattern. It captures the commonality in the interface. In expression templates, the common interface is the overloaded function call operator. DBinaryExpression is a real composite as well as an adaptor, which adapts Add's interface to that of DExpression. Constant and Var are two different types of leaf nodes. They also stick to the DExpression's interface. DExpression hides the complexity of DBinaryExpression, Constant and Var behind a unified interface to make them work together. Any binary operator can take place of Add, for example Divide, Multiply etc.

The above example does not show how recursive types are generated at compile-time. Also, expr does not look like a mathematical expression at all, but it is indeed one. The code that follows show how types are recursively composed using repetitive instantiation of the following overloaded + operator.

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

The above overloaded operator+ does two things - it adds syntactic sugar and enables recursive type composition, bounded by the compiler's limits. It can therefore be used to replace the call to evaluate as follows:

evaluate (a.begin(), a.end(), x + l + x); 
/// It is (2*x + 50.00), which does look like a mathematical expression.

More C++ Idioms/Expression-template

Contents

Expression Template

Intent

Also Known As

Motivation

Solution and Sample Code

Known Uses

Related Idioms

References