Expression Template

A mechanism in CeePlusPlus for turning expressions involving containers into FunctorObjects that can evaluate an equivalent expression for a single member from each of the containers. The resulting functor object can then evaluate the expression for all of the containers in a single loop and with no containers created to hold intermediate results.

When a program evaluates a complex expression, it must keep track of the intermediate results of the expression in a temporary variable. Typically, when containers (often matrices) are used in such expressions each step of the evaluation is carried out for the entire contents of the container before the next step is started. One side-effect of this is that the temporary variables that store the intermediate results are themselves containers. That means that a great deal of time and memory is wasted creating, destroying, and iterating through temporary containers. A better solution would be to evaluate the entire expression for the first item in each collection, store the result in the result collection and repeat the process for every remaining item in the input collections. Unfortunately, a naive implementation of this strategy would result in code that is difficult to read, write and maintain. What we would like is a way to create composable building blocks that can work together to implement this strategy transparently.

C++ ExpressionTemplates do exactly this by using LazyObjects to represent each step of the expression evaluation and hiding the single loop needed to drive the evaluation of those objects in the implementation of operator=().

An early paper on ExpressionTemplates can be found at: http://www.extreme.indiana.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html

More recent information can be found at:

It seems to me that ExpressionTemplates are an implementation of the TransfoldPattern. Take an expression that operates on a bunch of different collections to generate a final collection of results: that expression can be seen as a function that takes a collection of collections. The purpose of the TransfoldPattern is to allow simultaneous iteration of multiple collections along with parallel processing of their elements. The first step in the TransfoldPattern is the TransposeFunction which causes the collection of collections to be processed in row order rather than column order (i.e. one element from each collection is processed per iteration rather than one collection being processed per iteration). ExpressionTemplates do this by keeping the collections separate and processing each one with a separate LazyObject. The next step is to use a MapFunction to apply the same function to each row created by the transposition step. In the case of ExpressionTemplates that function is the expression itself and the MapFunction is implemented by the operator=() method. The TransfoldPattern goes on to use a FoldFunction to reduce the collection gained from the MapFunction to a single result, in the case of ExpressionTemplates there isn't generally a need for that reduction although it could certainly be done. If ExpressionTemplates aren't an implementation of the TransfoldPattern then they are certainly an instructive relative to it. -- PhilGoodwin

I think it is much the other way around. One could implement Transfold using ExpressionTemplates. For example, the following uses ExpressionTemplates.

 newCollection = collection * 5 / 4;

You aren't always transposing one or more collections into streams that can then be mapped and folded. However, you definitely can sometimes. It's been a lot of years since I studied the Blitz style of expression templates (after reading an old CppReport article on the subject) but you can create many different types of expression objects. They are JUST for binary matrix operations. -- RobertDiFalco

For an attempt to implement the TransfoldPattern in C++, see ObjectFunctionalImplementation.

Do you mean stuff like:

  expr = std::bind1st( std::equals< std::string >, string_value );

Or something else. If the above, I almost think of this as just simpler currying or aggregation instead of something as complicated as Transpose, Map, Fold. Then, the creation acts like a FunctorObject that can be used with for_each, accumulate, etc...

The intent is to write natural-looking expressions, and have the compiler do something sensible with them. So for example we might apply an arbitrary unary function to a range, specifying the unary function in place:

  ContainerType a;
  LambdaType x;
  Transform( a.begin( ), a.end( ), sin( x ) * cos( x ) - 2 * x * x );

Or we can compute matrix expressions without unnecessary temporaries, using a natural syntax:

  Matrix< double > a( 10, 10 );
  Matrix< double > b( 10, 10 );
  double x = ( a * b )( 5, 3 ); // only computes ab_{5,3}, not all of ab

One canonical example of ExpressionTemplates is the Blitz++ library (http://oonumerics.org/blitz/index.html).

Sure, but to me Blitz++ just has a different (more elegant) syntax for the same thing. The underlying concepts are the same as the approach taken by the STL and broadened to take lazy object, sparse matrices, and such into account. Either way, I don't consider the concept of expression as closely related to the TransfoldPattern. However, I can see how one couple implement a transfold using expression templates in the Blitz++ or STL.

Sure, ExpressionTemplates are a CplusPlusIdiom?, not a pattern in and of themselves.

ExpressionTemplate support will soon(ish) be available in CeeSharpLanguage (CeeSharpVersionThree?) and VisualBasicLanguage? (VisualBasicVersionNine?), along with anonymous (tuple) types, extension methods (see AspectOrientedProgramming), (limited) static TypeInference and improved lambda support. This is part of the changes being introduced to support LINQ -- see e.g. http://lambda-the-ultimate.org/node/967. What next -- homoiconic metaprogramming macros for VB?

CategoryCpp CategoryCppTemplates