Expression templates is a C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

 template metaprogramming

Template metaprogramming

Template metaprogramming is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates include compile-time constants, data structures, and...

 technique in which templates

Generic programming

In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters...

 are used to represent part of an expression. Typically, the template itself represents a particular type of operation, while the parameters represent the operands to which the operation applies. The expression template can then be evaluated

Lazy evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...

 at a later time, or passed to a function. The technique was proposed by Todd Veldhuizen in his June 1995 article in the C++ Report

C++ Report

C++ Report was a bi-monthly professional computer magazine published by SIGS Publications Group. It has been edited by Stanley B. Lippman, Douglas C. Schmidt, Brad Appleton and Robert Cecil Martin and aimed to cover various issues related to C++ programming language. It has been widely recognized...

.

For example, consider a library representing vectors with a class Vec. It is natural to want to overload operator- and operator* so you could write Vec x = alpha*(u - v); where alpha is a scalar and u and v are Vecs. A naive implementation would have operator- and operator* return Vecs. However, then the above expression would mean creating a temporary for u-v then another temporary for alpha times that first temporary, then assigning that to x.

Expression templates delay evaluation so the expression Vec x = alpha*(u-v); essentially generates at compile time a new Vec constructor taking a scalar and two Vecs as follows (using the curiously recurring template pattern

Curiously Recurring Template Pattern

The curiously recurring template pattern is a C++ idiom in which a class X derives from a class template instantiation using X itself as template argument...

as is used by Boost.uBLAS):

1. include
2. include

template
// A CRTP base class for Vecs with a size and indexing:
class VecExpression {
public:
typedef std::vector container_type;
typedef container_type::size_type size_type;
typedef container_type::value_type value_type;
typedef container_type::reference reference;

size_type size const { return static_cast(*this).size; }
value_type operator[](size_type i) const { return static_cast(*this)[i]; }

operator E& { return static_cast(*this); }
operator E const& const { return static_cast(*this); }
};

// The actual Vec class:
class Vec : public VecExpression {
container_type _data;
public:
reference operator[](size_type i) { return _data[i]; }
value_type operator[](size_type i) const { return _data[i]; }
size_type size const { return _data.size; }

Vec(size_type n) : _data(n) {} // Construct a given size:

// Construct from any VecExpression:
template
Vec(VecExpression const& vec) {
E const& v = vec;
_data.resize(v.size);
for (size_type i = 0; i != v.size; ++i) {
_data[i] = v[i];
}
}
};

template
class VecDifference : public VecExpression > {
E1 const& _u;
E2 const& _v;
public:
typedef Vec::size_type size_type;
typedef Vec::value_type value_type;
VecDifference(VecExpression const& u, VecExpression const& v) : _u(u), _v(v) {
assert(u.size v.size);
}
size_type size const { return _v.size; }
value_type operator[](Vec::size_type i) const { return _u[i] - _v[i]; }
};

template
class VecScaled : public VecExpression > {
double _alpha;
E const& _v;
public:
VecScaled(double alpha, VecExpression const& v) : _alpha(alpha), _v(v) {}
Vec::size_type size const { return _v.size; }
Vec::value_type operator[](Vec::size_type i) const { return _alpha * _v[i]; }
};

// Now we can overload operators:

template
VecDifference const
operator-(VecExpression const& u, VecExpression const& v) {
return VecDifference(u,v);
}

template
VecScaled const
operator*(double alpha, VecExpression const& v) {
return VecScaled(alpha,v);
}


With the above definitions, the expression alpha*(u-v) is of type
VecScaled >
so calling Vec x = alpha * (u-v) calls the constructor that takes a VecExpression > >. Each line of the for loop then expands from

_data[i] = v[i];

to essentially

_data[i] = alpha * (u[i] - v[i]);

with no temporaries needed and only one pass through each memory block.

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.