Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Users' Guide

Getting Started
Fronts Ends: Defining Terminals and Non-Terminals of Your EDSL
Intermediate Form: Understanding and Introspecting Expressions
Back Ends: Making Expression Templates Do Useful Work
Examples
Background and Resources
Glossary

Compilers, Compiler Construction Toolkits, and Proto

Most compilers have front ends and back ends. The front end parses the text of an input program into some intermediate form like an abstract syntax tree, and the back end takes the intermediate form and generates an executable from it.

A library built with Proto is essentially a compiler for an embedded domain-specific language (EDSL). It also has a front end, an intermediate form, and a back end. The front end is comprised of the symbols (a.k.a., terminals), members, operators and functions that make up the user-visible aspects of the EDSL. The back end is made of evaluation contexts and transforms that give meaning and behavior to the expression templates generated by the front end. In between is the intermediate form: the expression template itself, which is an abstract syntax tree in a very real sense.

To build a library with Proto, you will first decide what your interface will be; that is, you'll design a programming language for your domain and build the front end with tools provided by Proto. Then you'll design the back end by writing evaluation contexts and/or transforms that accept expression templates and do interesting things with them.

This users' guide is organized as follows. After a Getting Started guide, we'll cover the tools Proto provides for defining and manipulating the three major parts of a compiler:

Front Ends

How to define the aspects of your EDSL with which your users will interact directly.

Intermediate Form

What Proto expression templates look like, how to discover their structure and access their constituents.

Back Ends

How to define evaluation contexts and transforms that make expression templates do interesting things.

After that, you may be interested in seeing some Examples to get a better idea of how the pieces all fit together.

Getting Proto

You can get Proto by downloading Boost (Proto is in version 1.37 and later), or by accessing Boost's SVN repository on SourceForge.net. Just go to http://svn.boost.org/trac/boost/wiki/BoostSubversion and follow the instructions there for anonymous SVN access.

Building with Proto

Proto is a header-only template library, which means you don't need to alter your build scripts or link to any separate lib file to use it. All you need to do is #include <boost/proto/proto.hpp>. Or, you might decide to just include the core of Proto (#include <boost/proto/core.hpp>) and whichever contexts and transforms you happen to use.

Requirements

Proto depends on Boost. You must use either Boost version 1.34.1 or higher, or the version in SVN trunk.

Supported Compilers

Currently, Boost.Proto is known to work on the following compilers:

  • Visual C++ 8 and higher
  • GNU C++ 3.4 and higher
  • Intel on Linux 8.1 and higher
  • Intel on Windows 9.1 and higher
[Note] Note

Please send any questions, comments and bug reports to eric <at> boostpro <dot> com.

Proto is a large library and probably quite unlike any library you've used before. Proto uses some consistent naming conventions to make it easier to navigate, and they're described below.

Functions

All of Proto's functions are defined in the boost::proto namespace. For example, there is a function called value() defined in boost::proto that accepts a terminal expression and returns the terminal's value.

Metafunctions

Proto defines metafunctions that correspond to each of Proto's free functions. The metafunctions are used to compute the functions' return types. All of Proto's metafunctions live in the boost::proto::result_of namespace and have the same name as the functions to which they correspond. For instance, there is a class template boost::proto::result_of::value<> that you can use to compute the return type of the boost::proto::value() function.

Function Objects

Proto defines function object equivalents of all of its free functions. (A function object is an instance of a class type that defines an operator() member function.) All of Proto's function object types are defined in the boost::proto::functional namespace and have the same name as their corresponding free functions. For example, boost::proto::functional::value is a class that defines a function object that does the same thing as the boost::proto::value() free function.

Primitive Transforms

Proto also defines primitive transforms -- class types that can be used to compose larger transforms for manipulating expression trees. Many of Proto's free functions have corresponding primitive transforms. These live in the boost::proto namespace and their names have a leading underscore. For instance, the transform corresponding to the value() function is called boost::proto::_value.

The following table summarizes the discussion above:

Table 30.1. Proto Naming Conventions

Entity

Example

Free Function

boost::proto::value()

Metafunction

boost::proto::result_of::value<>

Function Object

boost::proto::functional::value

Transform

boost::proto::_value


Below is a very simple program that uses Proto to build an expression template and then execute it.

#include <iostream>
#include <boost/proto/proto.hpp>
#include <boost/typeof/std/ostream.hpp>
using namespace boost;

proto::terminal< std::ostream & >::type cout_ = { std::cout };

template< typename Expr >
void evaluate( Expr const & expr )
{
    proto::default_context ctx;
    proto::eval(expr, ctx);
}

int main()
{
    evaluate( cout_ << "hello" << ',' << " world" );
    return 0;
}

This program outputs the following:

hello, world

This program builds an object representing the output operation and passes it to an evaluate() function, which then executes it.

The basic idea of expression templates is to overload all the operators so that, rather than evaluating the expression immediately, they build a tree-like representation of the expression so that it can be evaluated later. For each operator in an expression, at least one operand must be Protofied in order for Proto's operator overloads to be found. In the expression ...

cout_ << "hello" << ',' << " world"

... the Protofied sub-expression is cout_, which is the Proto-ification of std::cout. The presence of cout_ "infects" the expression, and brings Proto's tree-building operator overloads into consideration. Any literals in the expression are then Protofied by wrapping them in a Proto terminal before they are combined into larger Proto expressions.

Once Proto's operator overloads have built the expression tree, the expression can be lazily evaluated later by walking the tree. That is what proto::eval() does. It is a general tree-walking expression evaluator, whose behavior is customizable via a context parameter. The use of proto::default_context assigns the standard meanings to the operators in the expression. (By using a different context, you could give the operators in your expressions different semantics. By default, Proto makes no assumptions about what operators actually mean.)

Proto Design Philosophy

Before we continue, let's use the above example to illustrate an important design principle of Proto's. The expression template created in the hello world example is totally general and abstract. It is not tied in any way to any particular domain or application, nor does it have any particular meaning or behavior on its own, until it is evaluated in a context. Expression templates are really just heterogeneous trees, which might mean something in one domain, and something else entirely in a different one.

As we'll see later, there is a way to create Proto expression trees that are not purely abstract, and that have meaning and behaviors independent of any context. There is also a way to control which operators are overloaded for your particular domain. But that is not the default behavior. We'll see later why the default is often a good thing.

"Hello, world" is nice, but it doesn't get you very far. Let's use Proto to build a EDSL (embedded domain-specific language) for a lazily-evaluated calculator. We'll see how to define the terminals in your mini-language, how to compose them into larger expressions, and how to define an evaluation context so that your expressions can do useful work. When we're done, we'll have a mini-language that will allow us to declare a lazily-evaluated arithmetic expression, such as (_2 - _1) / _2 * 100, where _1 and _2 are placeholders for values to be passed in when the expression is evaluated.

Defining Terminals

The first order of business is to define the placeholders _1 and _2. For that, we'll use the proto::terminal<> metafunction.

// Define a placeholder type
template<int I>
struct placeholder
{};

// Define the Protofied placeholder terminals
proto::terminal<placeholder<0> >::type const _1 = {{}};
proto::terminal<placeholder<1> >::type const _2 = {{}};

The initialization may look a little odd at first, but there is a good reason for doing things this way. The objects _1 and _2 above do not require run-time construction -- they are statically initialized, which means they are essentially initialized at compile time. See the Static Initialization section in the Rationale appendix for more information.

Constructing Expression Trees

Now that we have terminals, we can use Proto's operator overloads to combine these terminals into larger expressions. So, for instance, we can immediately say things like:

// This builds an expression template
(_2 - _1) / _2 * 100;

This creates an expression tree with a node for each operator. The type of the resulting object is large and complex, but we are not terribly interested in it right now.

So far, the object is just a tree representing the expression. It has no behavior. In particular, it is not yet a calculator. Below we'll see how to make it a calculator by defining an evaluation context.

Evaluating Expression Trees

No doubt you want your expression templates to actually do something. One approach is to define an evaluation context. The context is like a function object that associates behaviors with the node types in your expression tree. The following example should make it clear. It is explained below.

struct calculator_context
  : proto::callable_context< calculator_context const >
{
    // Values to replace the placeholders
    std::vector<double> args;

    // Define the result type of the calculator.
    // (This makes the calculator_context "callable".)
    typedef double result_type;

    // Handle the placeholders:
    template<int I>
    double operator()(proto::tag::terminal, placeholder<I>) const
    {
        return this->args[I];
    }
};

In calculator_context, we specify how Proto should evaluate the placeholder terminals by defining the appropriate overloads of the function call operator. For any other nodes in the expression tree (e.g., arithmetic operations or non-placeholder terminals), Proto will evaluate the expression in the "default" way. For example, a binary plus node is evaluated by first evaluating the left and right operands and adding the results. Proto's default evaluator uses the Boost.Typeof library to compute return types.

Now that we have an evaluation context for our calculator, we can use it to evaluate our arithmetic expressions, as below:

calculator_context ctx;
ctx.args.push_back(45); // the value of _1 is 45
ctx.args.push_back(50); // the value of _2 is 50

// Create an arithmetic expression and immediately evaluate it
double d = proto::eval( (_2 - _1) / _2 * 100, ctx );

// This prints "10"
std::cout << d << std::endl;

Later, we'll see how to define more interesting evaluation contexts and expression transforms that give you total control over how your expressions are evaluated.

Customizing Expression Trees

Our calculator EDSL is already pretty useful, and for many EDSL scenarios, no more would be needed. But let's keep going. Imagine how much nicer it would be if all calculator expressions overloaded operator() so that they could be used as function objects. We can do that by creating a calculator domain and telling Proto that all expressions in the calculator domain have extra members. Here is how to define a calculator domain:

// Forward-declare an expression wrapper
template<typename Expr>
struct calculator;

// Define a calculator domain. Expression within
// the calculator domain will be wrapped in the
// calculator<> expression wrapper.
struct calculator_domain
  : proto::domain< proto::generator<calculator> >
{};

The calculator<> type will be an expression wrapper. It will behave just like the expression that it wraps, but it will have extra member functions that we will define. The calculator_domain is what informs Proto about our wrapper. It is used below in the definition of calculator<>. Read on for a description.

// Define a calculator expression wrapper. It behaves just like
// the expression it wraps, but with an extra operator() member
// function that evaluates the expression.    
template<typename Expr>
struct calculator
  : proto::extends<Expr, calculator<Expr>, calculator_domain>
{
    typedef
        proto::extends<Expr, calculator<Expr>, calculator_domain>
    base_type;

    calculator(Expr const &expr = Expr())
      : base_type(expr)
    {}

    typedef double result_type;

    // Overload operator() to invoke proto::eval() with
    // our calculator_context.
    double operator()(double a1 = 0, double a2 = 0) const
    {
        calculator_context ctx;
        ctx.args.push_back(a1);
        ctx.args.push_back(a2);

        return proto::eval(*this, ctx);
    }
};

The calculator<> struct is an expression extension. It uses proto::extends<> to effectively add additional members to an expression type. When composing larger expressions from smaller ones, Proto notes what domain the smaller expressions are in. The larger expression is in the same domain and is automatically wrapped in the domain's extension wrapper.

All that remains to be done is to put our placeholders in the calculator domain. We do that by wrapping them in our calculator<> wrapper, as below:

// Define the Protofied placeholder terminals, in the
// calculator domain.
calculator<proto::terminal<placeholder<0> >::type> const _1;
calculator<proto::terminal<placeholder<1> >::type> const _2;

Any larger expression that contain these placeholders will automatically be wrapped in the calculator<> wrapper and have our operator() overload. That means we can use them as function objects as follows.

double result = ((_2 - _1) / _2 * 100)(45.0, 50.0);
assert(result == (50.0 - 45.0) / 50.0 * 100));

Since calculator expressions are now valid function objects, we can use them with standard algorithms, as shown below:

double a1[4] = { 56, 84, 37, 69 };
double a2[4] = { 65, 120, 60, 70 };
double a3[4] = { 0 };

// Use std::transform() and a calculator expression
// to calculate percentages given two input sequences:
std::transform(a1, a1+4, a2, a3, (_2 - _1) / _2 * 100);

Now, let's use the calculator example to explore some other useful features of Proto.

Detecting Invalid Expressions

You may have noticed that you didn't have to define an overloaded operator-() or operator/() -- Proto defined them for you. In fact, Proto overloads all the operators for you, even though they may not mean anything in your domain-specific language. That means it may be possible to create expressions that are invalid in your domain. You can detect invalid expressions with Proto by defining the grammar of your domain-specific language.

For simplicity, assume that our calculator EDSL should only allow addition, subtraction, multiplication and division. Any expression involving any other operator is invalid. Using Proto, we can state this requirement by defining the grammar of the calculator EDSL. It looks as follows:

// Define the grammar of calculator expressions
struct calculator_grammar
  : proto::or_<
        proto::plus< calculator_grammar, calculator_grammar >
      , proto::minus< calculator_grammar, calculator_grammar >
      , proto::multiplies< calculator_grammar, calculator_grammar >
      , proto::divides< calculator_grammar, calculator_grammar >
      , proto::terminal< proto::_ >
    >
{};

You can read the above grammar as follows: an expression tree conforms to the calculator grammar if it is a binary plus, minus, multiplies or divides node, where both child nodes also conform to the calculator grammar; or if it is a terminal. In a Proto grammar, proto::_ is a wildcard that matches any type, so proto::terminal< proto::_ > matches any terminal, whether it is a placeholder or a literal.

[Note] Note

This grammar is actually a little looser than we would like. Only placeholders and literals that are convertible to doubles are valid terminals. Later on we'll see how to express things like that in Proto grammars.

Once you have defined the grammar of your EDSL, you can use the proto::matches<> metafunction to check whether a given expression type conforms to the grammar. For instance, we might add the following to our calculator::operator() overload:

template<typename Expr>
struct calculator
  : proto::extends< /* ... as before ... */ >
{
    /* ... */
    double operator()(double a1 = 0, double a2 = 0) const
    {
        // Check here that the expression we are about to
        // evaluate actually conforms to the calculator grammar.
        BOOST_MPL_ASSERT((proto::matches<Expr, calculator_grammar>));
        /* ... */
    }
};

The addition of the BOOST_MPL_ASSERT() line enforces at compile time that we only evaluate expressions that conform to the calculator EDSL's grammar. With Proto grammars, proto::matches<> and BOOST_MPL_ASSERT() it is very easy to give the users of your EDSL short and readable compile-time errors when they accidentally misuse your EDSL.

[Note] Note

BOOST_MPL_ASSERT() is part of the Boost Metaprogramming Library. To use it, just #include <boost/mpl/assert.hpp>.

Controlling Operator Overloads

Grammars and proto::matches<> make it possible to detect when a user has created an invalid expression and issue a compile-time error. But what if you want to prevent users from creating invalid expressions in the first place? By using grammars and domains together, you can disable any of Proto's operator overloads that would create an invalid expression. It is as simple as specifying the EDSL's grammar when you define the domain, as shown below:

// Define a calculator domain. Expression within
// the calculator domain will be wrapped in the
// calculator<> expression wrapper.
// NEW: Any operator overloads that would create an
//      expression that does not conform to the
//      calculator grammar is automatically disabled.
struct calculator_domain
  : proto::domain< proto::generator<calculator>, calculator_grammar >
{};

The only thing we changed is we added calculator_grammar as the second template parameter to the proto::domain<> template when defining calculator_domain. With this simple addition, we disable any of Proto's operator overloads that would create an invalid calculator expression.

... And Much More

Hopefully, this gives you an idea of what sorts of things Proto can do for you. But this only scratches the surface. The rest of this users' guide will describe all these features and others in more detail.

Happy metaprogramming!

Here is the fun part: designing your own mini-programming language. In this section we'll talk about the nuts and bolts of designing an EDSL interface using Proto. We'll cover the definition of terminals and lazy functions that the users of your EDSL will get to program with. We'll also talk about Proto's expression template-building operator overloads, and about ways to add additional members to expressions within your domain.

As we saw with the Calculator example from the Introduction, the simplest way to get an EDSL up and running is simply to define some terminals, as follows.

// Define a literal integer Proto expression.
proto::terminal<int>::type i = {0};

// This creates an expression template.
i + 1;

With some terminals and Proto's operator overloads, you can immediately start creating expression templates.

Defining terminals -- with aggregate initialization -- can be a little awkward at times. Proto provides an easier-to-use wrapper for literals that can be used to construct Protofied terminal expressions. It's called proto::literal<>.

// Define a literal integer Proto expression.
proto::literal<int> i = 0;

// Proto literals are really just Proto terminal expressions.
// For example, this builds a Proto expression template:
i + 1;

There is also a proto::lit() function for constructing a proto::literal<> in-place. The above expression can simply be written as:

// proto::lit(0) creates an integer terminal expression
proto::lit(0) + 1;

Once we have some Proto terminals, expressions involving those terminals build expression trees for us. Proto defines overloads for each of C++'s overloadable operators in the boost::proto namespace. As long as one operand is a Proto expression, the result of the operation is a tree node representing that operation.

[Note] Note

Proto's operator overloads live in the boost::proto namespace and are found via ADL (argument-dependent lookup). That is why expressions must be "tainted" with Proto-ness for Proto to be able to build trees out of expressions.

As a result of Proto's operator overloads, we can say:

-_1;        // OK, build a unary-negate tree node
_1 + 42;    // OK, build a binary-plus tree node

For the most part, this Just Works and you don't need to think about it, but a few operators are special and it can be helpful to know how Proto handles them.

Assignment, Subscript, and Function Call Operators

Proto also overloads operator=, operator[], and operator(), but these operators are member functions of the expression template rather than free functions in Proto's namespace. The following are valid Proto expressions:

_1 = 5;     // OK, builds a binary assign tree node
_1[6];      // OK, builds a binary subscript tree node
_1();       // OK, builds a unary function tree node
_1(7);      // OK, builds a binary function tree node
_1(8,9);    // OK, builds a ternary function tree node
// ... etc.

For the first two lines, assignment and subscript, it should be fairly unsurprising that the resulting expression node should be binary. After all, there are two operands in each expression. It may be surprising at first that what appears to be a function call with no arguments, _1(), actually creates an expression node with one child. The child is _1 itself. Likewise, the expression _1(7) has two children: _1 and 7.

Because these operators can only be defined as member functions, the following expressions are invalid:

int i;
i = _1;         // ERROR: cannot assign _1 to an int

int *p;
p[_1];          // ERROR: cannot use _1 as an index

std::sin(_1);   // ERROR: cannot call std::sin() with _1

Also, C++ has special rules for overloads of operator-> that make it useless for building expression templates, so Proto does not overload it.

The Address-Of Operator

Proto overloads the address-of operator for expression types, so that the following code creates a new unary address-of tree node:

&_1;    // OK, creates a unary address-of tree node

It does not return the address of the _1 object. However, there is special code in Proto such that a unary address-of node is implicitly convertible to a pointer to its child. In other words, the following code works and does what you might expect, but not in the obvious way:

typedef
    proto::terminal< placeholder<0> >::type
_1_type;

_1_type const _1 = {{}};
_1_type const * p = &_1; // OK, &_1 implicitly converted

If we limited ourselves to nothing but terminals and operator overloads, our embedded domain-specific languages wouldn't be very expressive. Imagine that we wanted to extend our calculator EDSL with a full suite of math functions like sin() and pow() that we could invoke lazily as follows.

// A calculator expression that takes one argument
// and takes the sine of it.
sin(_1);

We would like the above to create an expression template representing a function invocation. When that expression is evaluated, it should cause the function to be invoked. (At least, that's the meaning of function invocation we'd like the calculator EDSL to have.) You can define sin quite simply as follows.

// "sin" is a Proto terminal containing a function pointer
proto::terminal< double(*)(double) >::type const sin = {&std::sin};

In the above, we define sin as a Proto terminal containing a pointer to the std::sin() function. Now we can use sin as a lazy function. The default_context that we saw in the Introduction knows how to evaluate lazy functions. Consider the following:

double pi = 3.1415926535;
proto::default_context ctx;
// Create a lazy "sin" invocation and immediately evaluate it
std::cout << proto::eval( sin(pi/2), ctx ) << std::endl;

The above code prints out:

1

I'm no expert at trigonometry, but that looks right to me.

We can write sin(pi/2) because the sin object, which is a Proto terminal, has an overloaded operator()() that builds a node representing a function call invocation. The actual type of sin(pi/2) is actually something like this:

// The type of the expression sin(pi/2):
proto::function<
    proto::terminal< double(*)(double) >::type const &
    proto::result_of::as_child< double const >::type
>::type

This type further expands to an unsightly node type with a tag type of proto::tag::function and two children: the first representing the function to be invoked, and the second representing the argument to the function. (Node tag types describe the operation that created the node. The difference between a + b and a - b is that the former has tag type proto::tag::plus and the latter has tag type proto::tag::minus. Tag types are pure compile-time information.)

[Note] Note

In the type computation above, proto::result_of::as_child<> is a metafunction that ensures its argument is a Proto expression type. If it isn't one already, it becomes a Proto terminal. We'll learn more about this metafunction, along with proto::as_child(), its runtime counterpart, later. For now, you can forget about it.

It is important to note that there is nothing special about terminals that contain function pointers. Any Proto expression has an overloaded function call operator. Consider:

// This compiles!
proto::lit(1)(2)(3,4)(5,6,7,8);

That may look strange at first. It creates an integer terminal with proto::lit(), and then invokes it like a function again and again. What does it mean? Who knows?! You get to decide when you define an evaluation context or a transform. But more on that later.

Making Lazy Functions, Continued

Now, what if we wanted to add a pow() function to our calculator EDSL that users could invoke as follows?

// A calculator expression that takes one argument
// and raises it to the 2nd power
pow< 2 >(_1);

The simple technique described above of making pow a terminal containing a function pointer doesn't work here. If pow is an object, then the expression pow< 2 >(_1) is not valid C++. (Well, technically it is; it means, pow less than 2, greater than (_1), which is nothing at all like what we want.) pow should be a real function template. But it must be an unusual function: one that returns an expression template.

With sin, we relied on Proto to provide an overloaded operator()() to build an expression node with tag type proto::tag::function for us. Now we'll need to do so ourselves. As before, the node will have two children: the function to invoke and the function's argument.

With sin, the function to invoke was a raw function pointer wrapped in a Proto terminal. In the case of pow, we want it to be a terminal containing TR1-style function object. This will allow us to parameterize the function on the exponent. Below is the implementation of a simple TR1-style wrapper for the std::pow function:

// Define a pow_fun function object
template< int Exp >
struct pow_fun
{
    typedef double result_type;

    double operator()(double d) const
    {
        return std::pow(d, Exp);
    }
};

Following the sin example, we want pow< 1 >( pi/2 ) to have a type like this:

// The type of the expression pow<1>(pi/2):
proto::function<
    proto::terminal< pow_fun<1> >::type
    proto::result_of::as_child< double const >::type
>::type

We could write a pow() function using code like this, but it's verbose and error prone; it's too easy to introduce subtle bugs by forgetting to call proto::as_child() where necessary, resulting in code that seems to work but sometimes doesn't. Proto provides a better way to construct expression nodes: proto::make_expr().

Lazy Functions Made Simple With make_expr()

Proto provides a helper for building expression templates called proto::make_expr(). We can concisely define the pow() function with it as below.

// Define a lazy pow() function for the calculator EDSL.
// Can be used as: pow< 2 >(_1)
template< int Exp, typename Arg >
typename proto::result_of::make_expr<
    proto::tag::function  // Tag type
  , pow_fun< Exp >        // First child (by value)
  , Arg const &           // Second child (by reference)
>::type const
pow(Arg const &arg)
{
    return proto::make_expr<proto::tag::function>(
        pow_fun<Exp>()    // First child (by value)
      , boost::ref(arg)   // Second child (by reference)
    );
}

There are some things to notice about the above code. We use proto::result_of::make_expr<> to calculate the return type. The first template parameter is the tag type for the expression node we're building -- in this case, proto::tag::function.

Subsequent template parameters to proto::result_of::make_expr<> represent child nodes. If a child type is not already a Proto expression, it is automatically made into a terminal with proto::as_child(). A type such as pow_fun<Exp> results in terminal that is held by value, whereas a type like Arg const & (note the reference) indicates that the result should be held by reference.

In the function body is the runtime invocation of proto::make_expr(). It closely mirrors the return type calculation. proto::make_expr() requires you to specify the node's tag type as a template parameter. The arguments to the function become the node's children. When a child should be stored by value, nothing special needs to be done. When a child should be stored by reference, you must use the boost::ref() function to wrap the argument.

And that's it! proto::make_expr() is the lazy person's way to make a lazy funtion.

In this section, we'll learn all about domains. In particular, we'll learn:

  • How to associate Proto expressions with a domain,
  • How to add members to expressions within a domain,
  • How to use a generator to post-process all new expressions created in your domain,
  • How to control which operators are overloaded in a domain,
  • How to specify capturing policies for child expressions and non-Proto objects, and
  • How to make expressions from separate domains interoperate.

In the Hello Calculator section, we looked into making calculator expressions directly usable as lambda expressions in calls to STL algorithms, as below:

double data[] = {1., 2., 3., 4.};

// Use the calculator EDSL to square each element ... HOW?
std::transform( data, data + 4, data, _1 * _1 );

The difficulty, if you recall, was that by default Proto expressions don't have interesting behaviors of their own. They're just trees. In particular, the expression _1 * _1 won't have an operator() that takes a double and returns a double like std::transform() expects -- unless we give it one. To make this work, we needed to define an expression wrapper type that defined the operator() member function, and we needed to associate the wrapper with the calculator domain.

In Proto, the term domain refers to a type that associates expressions in that domain to an expression generator. The generator is just a function object that accepts an expression and does something to it, like wrapping it in an expression wrapper.

You can also use a domain to associate expressions with a grammar. When you specify a domain's grammar, Proto ensures that all the expressions it generates in that domain conform to the domain's grammar. It does that by disabling any operator overloads that would create invalid expressions.

The first step to giving your calculator expressions extra behaviors is to define a calculator domain. All expressions within the calculator domain will be imbued with calculator-ness, as we'll see.

// A type to be used as a domain tag (to be defined below)
struct calculator_domain;

We use this domain type when extending the proto::expr<> type, which we do with the proto::extends<> class template. Here is our expression wrapper, which imbues an expression with calculator-ness. It is described below.

// The calculator<> expression wrapper makes expressions
// function objects.
template< typename Expr >
struct calculator
  : proto::extends< Expr, calculator< Expr >, calculator_domain >
{
    typedef
        proto::extends< Expr, calculator< Expr >, calculator_domain >
    base_type;

    calculator( Expr const &expr = Expr() )
      : base_type( expr )
    {}

    // This is usually needed because by default, the compiler-
    // generated assignment operator hides extends<>::operator=
    BOOST_PROTO_EXTENDS_USING_ASSIGN(calculator)

    typedef double result_type;

    // Hide base_type::operator() by defining our own which
    // evaluates the calculator expression with a calculator context.
    result_type operator()( double d1 = 0.0, double d2 = 0.0 ) const
    {
        // As defined in the Hello Calculator section.
        calculator_context ctx;

        // ctx.args is a vector<double> that holds the values
        // with which we replace the placeholders (e.g., _1 and _2)
        // in the expression.
        ctx.args.push_back( d1 ); // _1 gets the value of d1
        ctx.args.push_back( d2 ); // _2 gets the value of d2

        return proto::eval(*this, ctx ); // evaluate the expression
    }
};

We want calculator expressions to be function objects, so we have to define an operator() that takes and returns doubles. The calculator<> wrapper above does that with the help of the proto::extends<> template. The first template to proto::extends<> parameter is the expression type we are extending. The second is the type of the wrapped expression. The third parameter is the domain that this wrapper is associated with. A wrapper type like calculator<> that inherits from proto::extends<> behaves just like the expression type it has extended, with any additional behaviors you choose to give it.

[Note] Note

Why not just inherit from proto::expr<>?

You might be thinking that this expression extension business is unnecessarily complicated. After all, isn't this why C++ supports inheritance? Why can't calculator<Expr> just inherit from Expr directly? The reason is because Expr, which presumably is an instantiation of proto::expr<>, has expression template-building operator overloads that will be incorrect for derived types. They will store *this by reference to proto::expr<>, effectively slicing off any derived parts. proto::extends<> gives your derived types operator overloads that don't slice off your additional members.

Although not strictly necessary in this case, we bring extends<>::operator= into scope with the BOOST_PROTO_EXTENDS_USING_ASSIGN() macro. This is really only necessary if you want expressions like _1 = 3 to create a lazily evaluated assignment. proto::extends<> defines the appropriate operator= for you, but the compiler-generated calculator<>::operator= will hide it unless you make it available with the macro.

Note that in the implementation of calculator<>::operator(), we evaluate the expression with the calculator_context we defined earlier. As we saw before, the context is what gives the operators their meaning. In the case of the calculator, the context is also what defines the meaning of the placeholder terminals.

Now that we have defined the calculator<> expression wrapper, we need to wrap the placeholders to imbue them with calculator-ness:

calculator< proto::terminal< placeholder<0> >::type > const _1;
calculator< proto::terminal< placeholder<1> >::type > const _2;
Retaining POD-ness with BOOST_PROTO_EXTENDS()

To use proto::extends<>, your extension type must derive from proto::extends<>. Unfortunately, that means that your extension type is no longer POD and its instances cannot be statically initialized. (See the Static Initialization section in the Rationale appendix for why this matters.) In particular, as defined above, the global placeholder objects _1 and _2 will need to be initialized at runtime, which could lead to subtle order of initialization bugs.

There is another way to make an expression extension that doesn't sacrifice POD-ness : the BOOST_PROTO_EXTENDS() macro. You can use it much like you use proto::extends<>. We can use BOOST_PROTO_EXTENDS() to keep calculator<> a POD and our placeholders statically initialized.

// The calculator<> expression wrapper makes expressions
// function objects.
template< typename Expr >
struct calculator
{
    // Use BOOST_PROTO_EXTENDS() instead of proto::extends<> to
    // make this type a Proto expression extension.
    BOOST_PROTO_EXTENDS(Expr, calculator<Expr>, calculator_domain)

    typedef double result_type;

    result_type operator()( double d1 = 0.0, double d2 = 0.0 ) const
    {
        /* ... as before ... */
    }
};

With the new calculator<> type, we can redefine our placeholders to be statically initialized:

calculator< proto::terminal< placeholder<0> >::type > const _1 = {{{}}};
calculator< proto::terminal< placeholder<1> >::type > const _2 = {{{}}};

We need to make one additional small change to accommodate the POD-ness of our expression extension, which we'll describe below in the section on expression generators.

What does BOOST_PROTO_EXTENDS() do? It defines a data member of the expression type being extended; some nested typedefs that Proto requires; operator=, operator[] and operator() overloads for building expression templates; and a nested result<> template for calculating the return type of operator(). In this case, however, the operator() overloads and the result<> template are not needed because we are defining our own operator() in the calculator<> type. Proto provides additional macros for finer control over which member functions are defined. We could improve our calculator<> type as follows:

// The calculator<> expression wrapper makes expressions
// function objects.
template< typename Expr >
struct calculator
{
    // Use BOOST_PROTO_BASIC_EXTENDS() instead of proto::extends<> to
    // make this type a Proto expression extension:
    BOOST_PROTO_BASIC_EXTENDS(Expr, calculator<Expr>, calculator_domain)

    // Define operator[] to build expression templates:
    BOOST_PROTO_EXTENDS_SUBSCRIPT()

    // Define operator= to build expression templates:
    BOOST_PROTO_EXTENDS_ASSIGN()

    typedef double result_type;

    result_type operator()( double d1 = 0.0, double d2 = 0.0 ) const
    {
        /* ... as before ... */
    }
};

Notice that we are now using BOOST_PROTO_BASIC_EXTENDS() instead of BOOST_PROTO_EXTENDS(). This just adds the data member and the nested typedefs but not any of the overloaded operators. Those are added separately with BOOST_PROTO_EXTENDS_ASSIGN() and BOOST_PROTO_EXTENDS_SUBSCRIPT(). We are leaving out the function call operator and the nested result<> template that could have been defined with Proto's BOOST_PROTO_EXTENDS_FUNCTION() macro.

In summary, here are the macros you can use to define expression extensions, and a brief description of each.

Table 30.2. Expression Extension Macros

Macro

Purpose

BOOST_PROTO_BASIC_EXTENDS(
    expression
  , extension
  , domain
)

Defines a data member of type expression and some nested typedefs that Proto requires.

BOOST_PROTO_EXTENDS_ASSIGN()

Defines operator=. Only valid when preceded by BOOST_PROTO_BASIC_EXTENDS().

BOOST_PROTO_EXTENDS_SUBSCRIPT()

Defines operator[]. Only valid when preceded by BOOST_PROTO_BASIC_EXTENDS().

BOOST_PROTO_EXTENDS_FUNCTION()

Defines operator() and a nested result<> template for return type calculation. Only valid when preceded by BOOST_PROTO_BASIC_EXTENDS().

BOOST_PROTO_EXTENDS(
    expression
  , extension
  , domain
)

Equivalent to:

BOOST_PROTO_BASIC_EXTENDS(expression, extension, domain)

  BOOST_PROTO_EXTENDS_ASSIGN()

  BOOST_PROTO_EXTENDS_SUBSCRIPT()

  BOOST_PROTO_EXTENDS_FUNCTION()


[Warning] Warning

Argument-Dependent Lookup and BOOST_PROTO_EXTENDS()

Proto's operator overloads are defined in the boost::proto namespace and are found by argument-dependent lookup (ADL). This usually just works because expressions are made up of types that live in the boost::proto namespace. However, sometimes when you use BOOST_PROTO_EXTENDS() that is not the case. Consider:

template<class T>
struct my_complex
{
    BOOST_PROTO_EXTENDS(
        typename proto::terminal<std::complex<T> >::type
      , my_complex<T>
      , proto::default_domain
    )
};

int main()
{
    my_complex<int> c0, c1;

    c0 + c1; // ERROR: operator+ not found
}

The problem has to do with how argument-dependent lookup works. The type my_complex<int> is not associated in any way with the boost::proto namespace, so the operators defined there are not considered. (Had we inherited from proto::extends<> instead of used BOOST_PROTO_EXTENDS(), we would have avoided the problem because inheriting from a type in boost::proto namespace is enough to get ADL to kick in.)

So what can we do? By adding an extra dummy template parameter that defaults to a type in the boost::proto namespace, we can trick ADL into finding the right operator overloads. The solution looks like this:

template<class T, class Dummy = proto::is_proto_expr>
struct my_complex
{
    BOOST_PROTO_EXTENDS(
        typename proto::terminal<std::complex<T> >::type
      , my_complex<T>
      , proto::default_domain
    )
};

int main()
{
    my_complex<int> c0, c1;

    c0 + c1; // OK, operator+ found now!
}

The type proto::is_proto_expr is nothing but an empty struct, but by making it a template parameter we make boost::proto an associated namespace of my_complex<int>. Now ADL can successfully find Proto's operator overloads.

The last thing that remains to be done is to tell Proto that it needs to wrap all of our calculator expressions in our calculator<> wrapper. We have already wrapped the placeholders, but we want all expressions that involve the calculator placeholders to be calculators. We can do that by specifying an expression generator when we define our calculator_domain, as follows:

// Define the calculator_domain we forward-declared above.
// Specify that all expression in this domain should be wrapped
// in the calculator<> expression wrapper.
struct calculator_domain
  : proto::domain< proto::generator< calculator > >
{};

The first template parameter to proto::domain<> is the generator. "Generator" is just a fancy name for a function object that accepts an expression and does something to it. proto::generator<> is a very simple one --- it wraps an expression in the wrapper you specify. proto::domain<> inherits from its generator parameter, so all domains are themselves function objects.

If we used BOOST_PROTO_EXTENDS() to keep our expression extension type POD, then we need to use proto::pod_generator<> instead of proto::generator<>, as follows:

// If calculator<> uses BOOST_PROTO_EXTENDS() instead of 
// use proto::extends<>, use proto::pod_generator<> instead
// of proto::generator<>.
struct calculator_domain
  : proto::domain< proto::pod_generator< calculator > >
{};

After Proto has calculated a new expression type, it checks the domains of the child expressions. They must match. Assuming they do, Proto creates the new expression and passes it to Domain::operator() for any additional processing. If we don't specify a generator, the new expression gets passed through unchanged.