Chapter 48. Boost.YAP

Zach Laine

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Introduction

"I like to start documentation with a quote. A nice, pithy one."

— Eric Niebler (paraphrased)

Motivation

Expression templates are rad. They are used in lots of libraries; here are just three of the most impressive:

Boost.Spirit allows you to write an EBNF-style grammar that gets transformed into a PEG parser.
Eigen allows you to do linear algebra using a very natural and mathematical expression syntax that Eigen uses to heavily optimize your expressions.
NT2 takes slightly modified MatLab code and allows it to be parsed and run as highly optimized C++ code.

However, this can come at a high cost. Expression templates are costly to implement and maintain. Each of Eigen and Boost.Ublas has a large volume of complex expression template code that cannot be reused elsewhere.

With the language facilities available in the C++14 and C++17 standards, an expression template library is now straightforward to write and use, and has very reasonable compile times.

As a quick example, let's say we are doing a bit of matrix math, and we write this statement:

D=A\*B+C;

in which all the variables are matrices. It turns out that making a temporary for A * B and then another temporary for the resulting product plus C is very inefficient. Most matrix math libraries will have a single function that does it in one go:

mul\_add\_assign(D,A,B,C);

If you use a matrix library that offers both kinds of syntax, you have to notice when some bit of operator-using code should be replaced with some more efficient function; this is tedious and error-prone. If the library does not provide the operator syntax at all, only providing the more-efficient function calls, code using the library is a lot less writable and readable.

Using Boost.YAP, you can write some library code that enables expressions like D = A * B + C to be automatically transformed into expressions like mul_add_assign(D, A, B, C).

Consider another example. Many of us have used Unix command line tools to remove duplicate lines in a file:

sortfile\_with\_duplicates|uniq\>file\_without\_duplicates

We can do something very similar with the standard algorithms, of course:

std::vector\<int\>v1={0,2,2,7,1,3,8};std::sort(v1.begin(),v1.end());autoit=std::unique(v1.begin(),v1.end());std::vector\<int\>constv2(v1.begin(),it);assert(v2==std::vector\<int\>({0,1,2,3,7,8}));

However, it would be much better if our code did exactly that, but with a more concise syntax:

std::vector\<int\>v1={0,2,2,7,1,3,8};std::vector\<int\>constv2=sort(v1)|unique;assert(v2==std::vector\<int\>({0,1,2,3,7,8}));

This looks much more similar to the Unix command line above. (Let's pretend that Range-v3 doesn't already do almost exactly this.)

Boost.YAP can be used to do both of these things, in a pretty small amount of code. In fact, you can jump right into the Pipable Algorithms example if you want to see how the second one can be implemented.

Features

Simple ExpressionTemplate and Expression concepts easily modeled by user code. Member and non-member functions on ExpressionTemplates and Expressions can be added with compact macros, and a reference template that models ExpressionTemplate exists for prototyping or experimentation.
Evaluation of Boost.YAP expressions matches the semantics of builtin C++ expressions as closely as possible. This leads to clearer understanding of the semantics of expression evaluation, because the definitions are local to the types involved.
Expressions may be transformed explicitly in a user-defined way. This is accomplished with overloaded call operators in a transform class, which are matched against subexpressions in the overall expression. While these member functions may transform a subexpression into anything, a common pattern is to transform only some subexpressions into either new subexpressions or appropriate values and to leave other subexpressions unchanged. This evaluate(transform(expr)) idiom is expected to be one of the most common ways of using Yap to manipulate and evaluate expressions.
Functions that operate on or create expressions. Functions are provided (and used within Boost.YAP) that manipulate expressions or their subexpressions. These simplify the process of writing user-defined transforms, for example.

Last revised: August 05, 2021 at 09:53:06 GMT