An Expression Template Primer

What are expression templates anyway? In short, expression templates are templates that you write to capture expressions so that they can be transformed and/or evaluated lazily.

An example of normal C++ expression is:

std::sqrt(3.0) + 8.0f

The compiler sees this and creates some representation of that expression inside the compiler. This is typically an abstract syntax tree (AST). The AST for the expression above might be:

ast

This tree structure captures all the elements of the original C++ code. The expression is a plus operation whose left side is a call to std::sqrt(3.0) and whose right side is 8.0f. The call to std::sqrt(3.0) is its own expression subtree consisting of a call node and its argument node.

A Boost.YAP version of this same tree is:

expr

The operator+() is represented by a Boost.YAP expression whose kind is yap::expr_kind::plus and the call is represented by a Boost.YAP expression whose kind is yap::expr_kind::call. Notice that the call expression has two terminals, one for the callable, and one for its single argument.

The type that holds this expression is:

boost::yap::expression<
    boost::yap::expr_kind::plus,
    boost::hana::tuple<
        boost::yap::expression<
            boost::yap::expr_kind::call,
            boost::hana::tuple<
                boost::yap::expression<
                    boost::yap::expr_kind::terminal,
                    boost::hana::tuple<double (*)(double)>
                >,
                boost::yap::expression<
                    boost::yap::expr_kind::terminal,
                    boost::hana::tuple<double>
                >
            >
        >,
        boost::yap::expression<
            boost::yap::expr_kind::terminal,
            boost::hana::tuple<float>
        >
    >
>

That looks like a big mess; let's unpack it. You might notice that the overall shape is the same as the expression tree diagram above. We have tree-like nesting of boost::yap::expression template instantiations.

Here's the top-level boost::yap::expression again with its noisy guts removed:

boost::yap::expression<
    boost::yap::expr_kind::plus,
    boost::hana::tuple<

// Left and right operand expressions ...

>
>

It has an expr_kind of plus as its first template parameter (it's a non-type parameter); this indicates what kind of "node" it is. In this case, the top level expression is analogous to our operator+() AST node. Its operands are the elements of its boost::hana::tuple<> data member.

The left operand to the top-level plus operation is itself a Boost.YAP expression representing std::sqrt(3.0):

boost::yap::expression<
    boost::yap::expr_kind::call,
    boost::hana::tuple<
        boost::yap::expression<
            boost::yap::expr_kind::terminal,
            boost::hana::tuple<double (*)(double)>
        >,
        boost::yap::expression<
            boost::yap::expr_kind::terminal,
            boost::hana::tuple<double>
        >
    >
>,

This expression is a call expression. The first operand to the call expression is the callable entity, in this case a pointer to std::sqrt. The remaining operands are the arguments to pass to the callable; in this case, there's only one operand after the callable, 3.0.

The children of the std::sqrt(3.0) subexpression are terminals. This means that they are leaf nodes in our notional AST.

The right operand to the top-level plus operation is of course also a Boost.YAP expression. It is also a terminal:

boost::yap::expression<
    boost::yap::expr_kind::terminal,
    boost::hana::tuple<float>
>

Notice a couple of things here: 1) non-terminals (the top-level plus operation and the call opertion in our example) have tuple elements that are all Boost.YAP expressions, and 2) terminals have tuple elements, none of which are Boost.YAP expressions (they're just normal types like float and double (*)(double)).

	Note
	From here on, I'll use the terms "expression" and "node" interchangably, and I'll also use the terms "subexpression" and "child" interchangably. Even though expression templates are not identical to tree-based ASTs, they're close enough that the terminology is interchangable without loss of meaning.

Capturing an Expression

If we want to capture an expression using Boost.YAP we have to do something to let the compiler know not just to eagerly evaulate our expression, as it does when it sees std::sqrt(3.0) + 8.0f.

To do this, we create expr_kind::terminal expressions out of one or more of the terminals in the expression we want to capture and evaluate lazily. Here, I've declared a template alias to make that easier to type:

template <typename T>
using term = boost::yap::terminal<boost::yap::expression, T>;

And here is how I might use that alias to create the terminal containing std::sqrt:

boost::yap::expression<
    boost::yap::expr_kind::plus,
    boost::hana::tuple<
        boost::yap::expression<
            boost::yap::expr_kind::call,
            boost::hana::tuple<
                boost::yap::expression<
                    boost::yap::expr_kind::terminal,
                    boost::hana::tuple<double (*)(double)>
                >,
                boost::yap::expression<
                    boost::yap::expr_kind::terminal,
                    boost::hana::tuple<double>
                >
            >
        >,
        boost::yap::expression<
            boost::yap::expr_kind::terminal,
            boost::hana::tuple<float>
        >
    >
>
yap_expr = term<double (*)(double)>{{std::sqrt}}(3.0) + 8.0f;

The reason I can then just call the terminal with a 3.0 argument and add 8.0f to the result is that I'm taking a great big shortcut in this example by using Boost.YAP's built-in example expression template, expression<>. expression<> is a template with all the operator overloads defined, including the call operator. Each operator overload returns an expression<>, which is why the + in std::sqrt(3.0) + 8.0f also works.

Note

expression<> is great for example code like what you see here, and it's great for small expression template use cases that are essentially implementation details. You should write your own expression templates for anything that is to be used in any other context. The reason for this is that most of the time your expression template system will not want to support all combinations of all possible operators and function calls. For instance, code like this:

(a + b) = c;

is at least unusual, if not outright wrong. Where does c go? Into a, b, or into an expiring a + b temporary? What if a is a std::string and b is a FILE *? expression<> doesn't care. You probably want to design interfaces that are more carefully considered than the "everything goes" style implied by using expression<>.

Boost.YAP comes with a handy print() function. Calling it like this:

print(std::cout, yap_expr);

Gives this output:

expr<+>
    expr<()>
        term<double (*)(double)>[=1]
        term<double>[=3]
    term<float>[=8]

This is a lot more readable. I show this to you here to give you a more concise view of the AST-like structure.

(In case you're wondering why &std::sqrt is printed as the value 1, so was I. Apparently, that's just what GCC prints for that. Weird.)

Doing Something Useful With It

Now we've seen a simple expression both described as a C++ AST and captured as a Boost.YAP expression. This just introduces the expression template mechanism; what do we do with it once we have an expression template? Consider one of the examples from the intro:

std::vector<int> v1 = {/* ... */};
std::vector<int> v2 = sort(v) | unique;

The rest of the tutorial will explain in greater detail how Boost.YAP can be used in situations like this, but the brief version is this:

Use Boost.YAP to capture an expression. In this case, something like auto expr = sort(v) | unique;.
Use the Boost.YAP transform() algorithm to transform the expression into what you want. In this case, something like auto desired_expr = yap::transform(expr, my_transform);, which turns the concise form sort(v) | unique into the more verbose calls required by the standard algorithm APIs. Note that the resulting expression can be transformed repeatedly if this is desirable.
Evauate the final expression, either using evaluate() or a call to transform() that transforms the final expression into an evaluated result.