A "generic-enough" set of expression templates

• Download demo project - 6.02 Kb
• Download source - 3.69 Kb

Introduction

This article – and the source-code accompanying it – presents a small library of C++ templates for calculating general arithmetic and logical expressions of C++ composite types. The code is an implementation of the "Expression-Template" paradigm described in [Velhuizen] and [AngelicaLanger].

Apart from the usual arithmetic operations of addition, subtraction, multiplication and division, and the logical operations of negation, conjunction and disjunction, the library also provides a small set of trigonometric and exponential and log functions, mainly for showing how it can be extended to accommodate more complex mathematical constructs.

[Velhuizen] and [AngelicaLanger] provide guidelines for evaluating expressions recursively at compile-time. However, these guidelines can only be used with expressions of a certain arithmetic type (e.g., double), therefore lacking the generality necessary for any template library. The generalization step is not obvious as can be seen by comparing the attached example project and the source-code presented in the references.

Background

Templates are way beyond “parameterization of classes on the contained type”. This is common knowledge now in the C++ community. What makes templates a great programming tool is – I think – that they provide a standard interface for performing custom compilations or, more interestingly, to instruct the C++ compiler perform certain calculations from within the source code.

As far as expressions are regarded, it is well known that the compilers evaluate them by generating temporaries that vary in number according to the complexity of the expression being parsed. The temporaries represent internal (non-terminal) nodes in the expression trees created during the evaluation process. E.g., assume that one is given a matrix class with overloaded + and * operators. The evaluation of the expression:

A = d*(B + C)

(E1)

for L to R parsing, compatible A, B and C matrix objects, and a scalar variable d, will implicitly generate two temporaries:

temporary1 = B + C
temporary2 = d*temporary1
A = temporary2

If the dimensions of B and C are large, the evaluation performance of (E1) will be degraded substantially due to the allocation, deallocation and copying of large memory blocks.

Ideally, one expects that (E1) and any expression, in general, no matter how complex it is, would be substituted by the compiler with the following snippet:

Matrix<double> A, B, C;
double d;
...
for(Matrix<double>::iterator it = A.begin(); it != A.end(); it++)
    A[i] = d*(B[i] + C[i]);

This is exactly achieved by expression-templates and proper inlining of the arithmetic operations involved in the expression.

We may further expand the above example, to generators for any analytic operation. For example, using an expression template on a vector with 100 elements:

vector<float> v(100, 1);
for(vector<float>::size_type i = 0; i < v.size(); i++) v[i] = 2*M_PI*i/100;

the statement

Sin(v);

(E2)

is substituted at compile-time by:

for(vector<float>::size_type i = 0; i < v.size(); i++) v[i] = sin(v[i]);

and a complex statement like:

vector<float> u = Sin(v) + 2*w + z;

(E3)

by

for(size_t i = 0; i < v.size(); i++) v[i] = sin(v[i]) + 2.f*w[i] + z[i];

The same programming paradigm is implemented in the lambda-calculus package of Boost library. There, the purpose is to be able to write statements like:

vector<float> v, u, w;
...
boost::for_each(IteratorFirst, IteratorLast, v = 2.f*u + w/2.f);

again eliminating temporaries.

Using the code

Code usage is straightforward as can be seen in the .cpp file I created for testing the library. The following are worth noting:

The CPP file uses the library on a derivative of std::vector template. The derivation is very easy as can be seen in Vector.h header. Eventually, it adds only a public attribute, an expression object pointing to the beginning of the container, and provides a new assignment operator and a Find method that returns the result of arithmetic and logical operations, respectively. Logical operations always return a vector<size_t> object with the indices of vector elements satisfying the logical operation.

Arithmetic and logical operations are performed using the attribute e of type E<I<iterator> > of Vector class. The attribute is simply assigned the begin() return value of the base class vector<...>. I have deliberately chosen to do so for clarity. Then, E2, for example, must be written as:

Sin(v.e);

(E4)

Writing E4 as E2 can be implemented very easily by rewriting Sin to accept as argument a Vector type and constructing the expression object internally. The following fragments from the test project define two vectors of 100 elements each. The values are taken to represent angles in radians equal to 1/100^th of the circumference of a circle.

// Define vectors with 100 elements each and initial value 0 
DoubleVector v1(100, 0), v2(100, 0); 

// assign angle values to 
v1 for(size_t i = 0; i < v1.size(); i++) v1[i] = 2*M_PI*i/100; 

// Arbitrary arithmetic computations on v1 and v2 
v1 = Sin(v1.e) + Cos(v1.e);
v2 = 1. + Exp(-v1.e) + v1.e/2.;

Logical operations return an std::vector<size_t> with the indices of vector elements satisfying the expression. For example:

vector<size_t> idxs = v2.Find(v1.e > 0.);

The library

The gist of the templates contained in "Expressions.h" header are the I and It identity templates – representing terminal nodes in the expression tree, the BE and UE templates – representing non-terminal binary and unary operations in the expression tree, and the E template that acts as a base class in the OO terminology.

The type an expression object actually represents is resolved by the Traits typedef, present in all classes. The expression-evaluation recursion step is implemented by EvaluatesTo and Satisfies methods, defined in the derivatives of I, It, BE and UE templates.

Last but not least: notice that the iterative evaluation of the expression over the elements of the composite Vector template is done by the assignment operator. The mere role of the whole template library is to parse inline the expression being evaluated.