Channels ▼
RSS

Design

Expression Generics


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;
};

Example 1: Class DVBinExpr in C++

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; }
};

Example 2: The addition applicative in C++

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());
}

Example 3: Overloaded operator+() in C++

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.

[Click image to view at full size]
Figure 1: Expression tree


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video