C++ Expression Templates

Posted by & filed under c++, programming.

C++ expression templates encode all the information about an expression in its type. Or, in compiler parlance, it encodes the parse tree of an expression in its type. Let’s explore this concise definition in detail. First of all, what are expressions, and what are types? The following snippets are all expressions :

a
a+b
(c=a+b, d=x-y)

The following is also an expression, just a complicated one.

if_(a<b) [
  c = d+e,
  r = s+t
].else_[
  x = y+f,
  z = d-e
]

In the following code

int a,x; float b; double d;
struct foo { ... };
foo bar;
a-x
b+a;

the type of a and x are int, the type of bar is foo, the type of the expression a-x is int, and the type of the expression b+a is float. We have template classes in C++, which can lead to some fancy types. For example,

template<class T>
struct foo { ... };
template<class T>
struct bar { ... };
/* The following are all types */
foo<int>
bar<double>
foo<bar<int> >
bar<std::vector<float> >
bar<foo<bar<foo<int> > > >

The mechanism used in C++ expression templates is a combination of these fancy types and some clever operator overloading. Let’s start by defining some simple classes.

struct var {};
struct plus {};
struct minus {};
struct multiplies {};
struct divides {};

Don’t be surprised by the empty classes. I am defining them this way to just illustrate expression templates. To make the expression templates do useful work, these classes should probably contain some methods and member variables. But that’s another post. Now let’s define the “expression” class.

template<class Op, class LHS, class RHS>
struct expr {};

There are many ways to define this class, different tutorials on expression templates on the web do it differently. But the way I have it, is a straightforward way to think about it. The expr class is has three template arguments. The Op argument represents the operation being performed, the LHS and RHS arguments represent the operands of that operation. The intention is to represent and expression a+b, where a and b are of type var, using the following instantiation of expr :

expr<plus, var, var>

So, how do we do that? Well, we are free to overload the ‘+’ operator, and are free to choose what the return type of the operator. We can go ahead and do this :

expr<plus, var, var>
operator +(const var &, const var &)
{
  return expr<plus, var, var>();
}

Now, whenever we do a+b, where a and b are of type var, the above function is invoked and a new object of type expr<plus, var, var> is constructed. The promise of expression templates is met, i.e., the type of the expression encodes the parse tree of the expression.

We are not done yet. What about the expression a+b+c? The compiler evaluates a+b first, so it would call the above function. But that function returns an object of the type expr<plus, var, var>. Then the compiler has to evaluate (a+b) + c, which means it would look for an operator overload that takes expr<plus, var, var> and var. So, we have to make one for that. As the expressions get bigger, the type of operands to the ‘+’ operator get more and more fancy. But the good news is, we can make the C++ compiler do the work for us, by templating the operator ‘+’ overload function itself. Let’s make the type of the two operands to ‘+’ as the template parameters as follows :

template<class LHS, class RHS>
expr<plus, LHS, RHS>
operator +(const LHS &, const RHS &)
{
  return expr<plus, LHS, RHS>();
}

Ponder the above function for a while. The return type is expr<plus, LHS, RHS>. Its operands are of type LHS and RHS. Let’s go back to a+b+c. First, the compiler tries to evaluate a+b. It looks for an operator overload. There is a match above, with LHS=var, RHS=var. It instantiates such a function, calls it and returns expr<plus, var, var>. Now it tries to evaluate (a+b) + c. Again, it looks for an operator overload. There is a match, with LHS=expr<plus, var, var> and RHS=var. It goes through the drill again, and returns an object of the following type :

expr<plus, expr<plus, var, var>, var>

Let’s complete the picture by defining the overloads for -, *, and / operators.

template<class LHS, class RHS>
expr<plus, LHS, RHS>
operator +(const LHS &, const RHS &)
{
  return expr<plus, LHS, RHS>();
}
template<class LHS, class RHS>
expr<minus, LHS, RHS>
operator -(const LHS &, const RHS &)
{
  return expr<minus, LHS, RHS>();
}
template<class LHS, class RHS>
expr<multiplies, LHS, RHS>
operator *(const LHS &, const RHS &)
{
  return expr<multiplies, LHS, RHS>();
}
template<class LHS, class RHS>
expr<divides, LHS, RHS>
operator /(const LHS &, const RHS &)
{
  return expr<divides, LHS, RHS>();
}

Imagine now, what happens when the compiler encounters an expression like a+b-c*d/e. Every time it needs to evaluate an operator, it would create an instance of one of the above functions (if not already created), and return the relevant type. That’s a lot of instantiations, and a lot of new types. But ultimately, the type of the expression contains all the information about the expression.

Leave a Reply

  • (will not be published)

XHTML: You can use these tags: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*