*Steve Samarov is a principal architect at Foliage Software. Over his career, Steve has held technical leadership and software development positions at
Xerox, Microsoft, and other companies.*

In my .NET development work, I always look for ways to apply lessons and techniques learned as a C++ programmer. There are substantial differences between C++ and C#, making it an interesting challenge to find in C# a conceptual equivalent to a C++ construct or idiom.

Expression templates are one such example. Described by Todd Veldhuizen in 1995, they have been addressed by the likes of Angelika Langer and Klaus Kreft in C++ Expression Templates and Thomas Becker in Expression Templates. Veldhuizen's goal was to create a C++ class library of numeric algorithms with "performance on par with Fortran 77/90." Expression templates are a useful tool in imaging applications that calculate algebraic expressions with bitmaps as input. The focus of this article is finding a C# technique conceptually equivalent to C++ expression templates that could be used by .NET programmers in imaging, numeric calculations, and other areas.

### What are Expression Templates?

In this article, I follow the example in Veldhuizen's original paper -- computation of expressions over vectors of double-precision values. With a user-defined class **Vector** representing a container of doubles, my goal is to calculate algebraic expressions that take **Vector** objects as arguments. For example, given vectors **v1** and **v2**, I can write in C++:

v = Sqrt(v1 + v2)/Log(v1);

The **Vector** class behaves like built-in types, a desired attribute in object-oriented programming. For this to work, I need a complete set of binary and unary operators, as well as mathematical functions that I intend to use in the expressions. With conventional operator overloading, evaluation of such expressions requires creation of temporary objects and multiple loops -- one for each operator and function. In the previous example, four temporary objects and five loops (including the final assignment) are needed to evaluate the expression, making calculations costly in time and space.

Expression templates solve both problems: They eliminate temporary objects and fuse all the loops in the expression into one, resulting in a considerably smaller and faster code. At compile time, the expression is parsed into a tree-like object. The leaf nodes are iterators positioned at the first elements of the input **Vectors**, and the inner nodes represent binary and unary operations, and functions. At runtime, the expression is evaluated in a single loop. In each iteration, the result is calculated for current iterator positions, then all iterators are incremented.

### How Does It Work In C++?

Class **Vector**, the container of double-precision numbers, must have an iterator and functions **begin()** and **end()** that return iterators positioned at both ends of the container. For example, my iterator is:

typedef double* Iter;

Next, I need two classes that represent binary and unary operations in the parse tree of the expression. The binary expression class, **DVBinExpr**, **DV** stands for "double vector", is a template with three parameters: the iterator type of the left operand, the iterator type of the right operand, and the type of the operation. The last parameter is an "applicative" class; it defines a static function **apply()** that takes two iterators as arguments and returns the result. The binary expression class must behave as an iterator and define **operator*()** and **operator++()**. Example 1 is the definition of **DVBinExpr**.

template<class IterA, class IterB, class Op> class DVBinExpr { public: typedef DVBinExpr<IterA, IterB, Op> Iter; DVBinExpr(IterA ia, IterB ib) : _ia(ia), _ib(ib) {} double operator*() const { return Op::apply(_ia, _ib); } void operator++() { ++_ia; ++_ib; } Iter begin() const { return *this; } private: IterA _ia; IterB _ib; };

The unary expression class, **DVUnaryExpr**, is similar, except it has only one operand to work with. The addition applicative class **DVOpAdd** (Example 2), and similar classes are defined for other binary and unary operations, as well as functions, such as **Log()** or **Sin()**.

template<class IterA, class IterB> class DVOpAdd { public: static double apply(const IterA& ia, const IterB& ib) { return *ia + *ib; } };

Finally, Example 3 is the overloaded **operator+()**.

template<class OperandA, class OperandB> DVBinExpr<typename OperandA::Iter, typename OperandB::Iter, DVOpAdd<typename OperandA::Iter, typename OperandB::Iter> > operator+(const OperandA& a, const OperandB& b) { return DVBinExpr<typename OperandA::Iter, typename OperandB::Iter, DVOpAdd<typename OperandA::Iter, typename OperandB::Iter> >(a.begin(), b.begin()); }

The rest of the operators follow the same pattern. As you can see, instead of executing addition of the two operands, I construct a binary expression with the iterators positioned at the beginning of its operands and **DVOpAdd** as its applicative. The operands can be either Vector variables or other expressions. In turn, the constructed expression can be an operand of another expression higher in the parse tree. Figure 1 illustrates the resulting structure.