Boost C++ Libraries

Getting Proto

You can get Proto by downloading proto.zip from http://www.boost-consulting.com/vault/index.php?directory=Template%20Metaprogramming, 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:

	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:

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 DSEL (domain-specific embedded 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 DSEL is already pretty useful, and for many DSEL 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 DSEL 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 DSEL. 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
	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 DSEL, 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 DSEL's grammar. With Proto grammars, proto::matches<> and BOOST_MPL_ASSERT() it is very easy to give the users of your DSEL short and readable compile-time errors when they accidentally misuse your DSEL.

	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 DSEL'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!

As we saw with the Calculator example from the Introduction, the simplest way to get a DSEL 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
	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 domain-specific embedded languages wouldn't be very expressive. Imagine that we wanted to extend our calculator DSEL 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 DSEL 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

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? To be sure, the default_context wouldn't know what to do with it. The default_context only knows how to evaluate expressions that are sufficiently C++-like. In the case of function call expressions, the left hand side must evaluate to something that can be invoked: a pointer to a function, a reference to a function, or a TR1-style function object. That doesn't stop you from defining your own evaluation context that gives that expression a meaning. But more on that later.

Making Lazy Functions, Continued

Now, what if we wanted to add a pow() function to our calculator DSEL 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++. pow needs to be a real function template. But it must be an unusual function; it must return an expression template.

Before we can write the pow() function, we need a function object that wraps an invocation of std::pow().

// 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);
    }
};

Now, let's try to define a function template that returns an expression template. We'll use the proto::function<> metafunction to calculate the type of a Proto expression that represents a function call. It is analogous to proto::terminal<>. (We'll see a couple of different ways to solve this problem, and each will demonstrate another utility for defining Proto front-ends.)

// Define a lazy pow() function for the calculator DSEL.
// Can be used as: pow< 2 >(_1)
template<int Exp, typename Arg>
typename proto::function<
    typename proto::terminal<pow_fun<Exp> >::type
  , Arg const &
>::type const
pow(Arg const &arg)
{
    typedef
        typename proto::function<
            typename proto::terminal<pow_fun<Exp> >::type
          , Arg const &
        >::type
    result_type;

    result_type result = {{{}}, arg};
    return result;
}

In the code above, notice how the proto::function<> and proto::terminal<> metafunctions are used to calculate the return type: pow() returns an expression template representing a function call where the first child is the function to call and the second is the argument to the function. (Unfortunately, the same type calculation is repeated in the body of the function so that we can initialize a local variable of the correct type. We'll see in a moment how to avoid that.)

	Note
	As with proto::function<>, there are metafunctions corresponding to all of the overloadable C++ operators for calculating expression types.

With the above definition of the pow() function, we can create calculator expressions like the one below and evaluate them using the calculator_context we implemented in the Introduction.

// Initialize a calculator context
calculator_context ctx;
ctx.args.push_back(3); // let _1 be 3

// Create a calculator expression that takes one argument,
// adds one to it, and raises it to the 2nd power; and then
// immediately evaluate it using the calculator_context.
assert( 16 == proto::eval( pow<2>( _1 + 1 ), ctx ) );

Protofying Lazy Function Arguments

Above, we defined a pow() function template that returns an expression template representing a lazy function invocation. But if we tried to call it as below, we'll run into a problem.

// ERROR: pow() as defined above doesn't work when
// called with a non-Proto argument.
pow< 2 >( 4 );

Proto expressions can only have other Proto expressions as children. But if we look at pow()'s function signature, we can see that if we pass it a non-Proto object, it will try to make it a child.

template<int Exp, typename Arg>
typename proto::function<
    typename proto::terminal<pow_fun<Exp> >::type
  , Arg const & // <=== ERROR! This may not be a Proto type!
>::type const
pow(Arg const &arg)

What we want is a way to make Arg into a Proto terminal if it is not a Proto expression already, and leave it alone if it is. For that, we can use proto::as_child(). The following implementation of the pow() function handles all argument types, expression templates or otherwise.

// Define a lazy pow() function for the calculator DSEL. Use
// proto::as_child() to Protofy the argument, but only if it
// is not a Proto expression type to begin with!
template<int Exp, typename Arg>
typename proto::function<
    typename proto::terminal<pow_fun<Exp> >::type
  , typename proto::result_of::as_child<Arg const>::type
>::type const
pow(Arg const &arg)
{
    typedef
        typename proto::function<
            typename proto::terminal<pow_fun<Exp> >::type
          , typename proto::result_of::as_child<Arg const>::type
        >::type
    result_type;

    result_type result = {{{}}, proto::as_child(arg)};
    return result;
}

Notice how we use the proto::result_of::as_child<> metafunction to calculate the return type, and the proto::as_child() function to actually normalize the argument.

Lazy Functions Made Simple With make_expr()

The versions of the pow() function we've seen above are rather verbose. In the return type calculation, you have to be very explicit about wrapping non-Proto types. Worse, you have to restate the return type calculation in the body of pow() itself. Proto provides a helper for building expression templates directly that handles these mundane details for you. It's called proto::make_expr(). We can redefine pow() with it as below.

// Define a lazy pow() function for the calculator DSEL.
// 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, which is the tag type Proto uses for function call expressions.

Subsequent template parameters to proto::result_of::make_expr<> represent children nodes. If a child type is not already a Proto expression, it is 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. Without this extra information, the proto::make_expr() function couldn't know whether to store a child by value or by reference.

In this section, we'll see how to associate Proto expressions with a domain, how to add members to expressions within a domain, and how to control which operators are overloaded in a domain.

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

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

The extends<> Expression Wrapper

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

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 15.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

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.

// 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 > >
{};

// 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 > >
{};

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

// Use the calculator DSEL to square each element ... WORKS! :-)
std::transform( data, data + 4, data, _1 * _1 );

// 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::_ >
    >
{};

// Define the calculator_domain. Expressions in the calculator
// domain are wrapped in the calculator<> wrapper, and they must
// conform to the calculator_grammar:
struct calculator_domain
  : proto::domain< proto::generator< calculator >, calculator_grammar  >
{};

// For expressions in my_domain, disable Proto's
// unary address-of operator.
struct my_domain
  : proto::domain<
        proto::generator< my_wrapper >
        // A simple grammar that matches any expression that
        // is not a unary address-of expression.
      , proto::not_< proto::address_of< _ > >
    >
{};

The preceding discussions of defining Proto front ends have all made a big assumption: that you have the luxury of defining everything from scratch. What happens if you have existing types, say a matrix type and a vector type, that you would like to treat as if they were Proto terminals? Proto usually trades only in its own expression types, but with BOOST_PROTO_DEFINE_OPERATORS(), it can accomodate your custom terminal types, too.

Let's say, for instance, that you have the following types and that you can't modify then to make them “native” Proto terminal types.

namespace math
{
    // A matrix type ...
    struct matrix { /*...*/ };

    // A vector type ...
    struct vector { /*...*/ };
}

You can non-intrusively make objects of these types Proto terminals by defining the proper operator overloads using BOOST_PROTO_DEFINE_OPERATORS(). The basic procedure is as follows:

The following code demonstrates how it works.

namespace math
{
    template<typename T>
    struct is_terminal
      : mpl::false_
    {};

    // OK, "matrix" is a custom terminal type
    template<>
    struct is_terminal<matrix>
      : mpl::true_
    {};

    // OK, "vector" is a custom terminal type
    template<>
    struct is_terminal<vector>
      : mpl::true_
    {};

    // Define all the operator overloads to construct Proto
    // expression templates, treating "matrix" and "vector"
    // objects as if they were Proto terminals.
    BOOST_PROTO_DEFINE_OPERATORS(is_terminal, proto::default_domain)
}

The invocation of the BOOST_PROTO_DEFINE_OPERATORS() macro defines a complete set of operator overloads that treat matrix and vector objects as if they were Proto terminals. And since the operators are defined in the same namespace as the matrix and vector types, the operators will be found by argument-dependent lookup. With the code above, we can now construct expression templates with matrices and vectors, as shown below.

math::matrix m1;
math::vector v1;
proto::literal<int> i(0);

m1 * 1;  // custom terminal and literals are OK
m1 * i;  // custom terminal and Proto expressions are OK
m1 * v1; // two custom terminals are OK, too.

Sometimes as a DSEL designer, to make the lives of your users easy, you have to make your own life hard. Giving your users natural and flexible syntax often involves writing large numbers of repetitive function overloads. It can be enough to give you repetitive stress injury! Before you hurt yourself, check out the macros Proto provides for automating many repetitive code-generation chores.

Imagine that we are writing a lambda DSEL, and we would like to enable syntax for constructing temporary objects of any type using the following syntax:

// A lambda expression that takes two arguments and
// uses them to construct a temporary std::complex<>
construct< std::complex<int> >( _1, _2 )

For the sake of the discussion, imagine that we already have a function object template construct_impl<> that accepts arguments and constructs new objects from them. We would want the above lambda expression to be equivalent to the following:

// The above lambda expression should be roughly equivalent
// to the following:
proto::make_expr<proto::tag::function>(
    construct_impl<std::complex<int> >() // The function to invoke lazily
  , boost::ref(_1)                       // The first argument to the function
  , boost::ref(_2)                       // The second argument to the function
);

We can define our construct() function template as follows:

template<typename T, typename A0, typename A1>
typename proto::result_of::make_expr<
    proto::tag::function
  , construct_impl<T>
  , A0 const &
  , A1 const &
>::type const
construct(A0 const &a0, A1 const &a1)
{
    return proto::make_expr<proto::tag::function>(
        construct_impl<T>()
      , boost::ref(a0)
      , boost::ref(a1)
    );
}

This works for two arguments, but we would like it to work for any number of arguments, up to ( BOOST_PROTO_MAX_ARITY - 1). (Why "- 1"? Because one child is taken up by the construct_impl<T>() terminal leaving room for only ( BOOST_PROTO_MAX_ARITY - 1) other children.)

For cases like this, Proto provides the BOOST_PROTO_REPEAT() and BOOST_PROTO_REPEAT_FROM_TO() macros. To use it, we turn the function definition above into a macro as follows:

#define M0(N, typename_A, A_const_ref, A_const_ref_a, ref_a)  \
template<typename T, typename_A(N)>                           \
typename proto::result_of::make_expr<                         \
    proto::tag::function                                      \
  , construct_impl<T>                                         \
  , A_const_ref(N)                                            \
>::type const                                                 \
construct(A_const_ref_a(N))                                   \
{                                                             \
    return proto::make_expr<proto::tag::function>(            \
        construct_impl<T>()                                   \
      , ref_a(N)                                              \
    );                                                        \
}

Notice that we turned the function into a macro that takes 5 arguments. The first is the current iteration number. The rest are the names of other macros that generate different sequences. For instance, Proto passes as the second parameter the name of a macro that will expand to typename A0, typename A1, ....

Now that we have turned our function into a macro, we can pass the macro to BOOST_PROTO_REPEAT_FROM_TO(). Proto will invoke it iteratively, generating all the function overloads for us.

// Generate overloads of construct() that accept from
// 1 to BOOST_PROTO_MAX_ARITY-1 arguments:
BOOST_PROTO_REPEAT_FROM_TO(1, BOOST_PROTO_MAX_ARITY, M0)
#undef M0

Non-Default Sequences

As mentioned above, Proto passes as the last 4 arguments to your macro the names of other macros that generate various sequences. The macros BOOST_PROTO_REPEAT() and BOOST_PROTO_REPEAT_FROM_TO() select defaults for these parameters. If the defaults do not meet your needs, you can use BOOST_PROTO_REPEAT_EX() and BOOST_PROTO_REPEAT_FROM_TO_EX() and pass different macros that generate different sequences. Proto defines a number of such macros for use as parameters to BOOST_PROTO_REPEAT_EX() and BOOST_PROTO_REPEAT_FROM_TO_EX(). Check the reference section for boost/proto/repeat.hpp for all the details.

Also, check out BOOST_PROTO_LOCAL_ITERATE(). It works similarly to BOOST_PROTO_REPEAT() and friends, but it can be easier to use when you want to change one macro argument and accept defaults for the others.

After assembling an expression into a tree, you'll naturally want to be able to do the reverse, and access a node's children. You may even want to be able to iterate over the children with algorithms from the Boost.Fusion library. This section shows how.

Getting Expression Tags and Arities

Every node in an expression tree has both a tag type that describes the node, and an arity corresponding to the number of child nodes it has. You can use the proto::tag_of<> and proto::arity_of<> metafunctions to fetch them. Consider the following:

template<typename Expr>
void check_plus_node(Expr const &)
{
    // Assert that the tag type is proto::tag::plus
    BOOST_STATIC_ASSERT((
        boost::is_same<
            typename proto::tag_of<Expr>::type
          , proto::tag::plus
        >::value
    ));

    // Assert that the arity is 2
    BOOST_STATIC_ASSERT( proto::arity_of<Expr>::value == 2 );
}

// Create a binary plus node and use check_plus_node()
// to verify its tag type and arity:
check_plus_node( proto::lit(1) + 2 );

For a given type Expr, you could access the tag and arity directly as Expr::proto_tag and Expr::proto_arity, where Expr::proto_arity is an MPL Integral Constant.

Getting Terminal Values

There is no simpler expression than a terminal, and no more basic operation than extracting its value. As we've already seen, that is what proto::value() is for.

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

// Get the value of the cout_ terminal:
std::ostream & sout = proto::value( cout_ );

// Assert that we got back what we put in:
assert( &sout == &std::cout );

To compute the return type of the proto::value() function, you can use proto::result_of::value<>. When the parameter to proto::result_of::value<> is a non-reference type, the result type of the metafunction is the type of the value as suitable for storage by value; that is, top-level reference and qualifiers are stripped from it. But when instantiated with a reference type, the result type has a reference added to it, yielding a type suitable for storage by reference. If you want to know the actual type of the terminal's value including whether it is stored by value or reference, you can use fusion::result_of::value_at<Expr, 0>::type.

The following table summarizes the above paragraph.

typename boost::remove_const<
    typename boost::remove_reference<T>::type
>::type [a]

typename boost::add_reference<T>::type

typename boost::add_reference<
    typename boost::add_const<T>::type
>::type

Getting Child Expressions

Each non-terminal node in an expression tree corresponds to an operator in an expression, and the children correspond to the operands, or arguments of the operator. To access them, you can use the proto::child_c() function template, as demonstrated below:

proto::terminal<int>::type i = {42};

// Get the 0-th operand of an addition operation:
proto::terminal<int>::type &ri = proto::child_c<0>( i + 2 );

// Assert that we got back what we put in:
assert( &i == &ri );

You can use the proto::result_of::child_c<> metafunction to get the type of the Nth child of an expression node. Usually you don't care to know whether a child is stored by value or by reference, so when you ask for the type of the Nth child of an expression Expr (where Expr is not a reference type), you get the child's type after references and cv-qualifiers have been stripped from it.

template<typename Expr>
void test_result_of_child_c(Expr const &expr)
{
    typedef typename proto::result_of::child_c<Expr, 0>::type type;

    // Since Expr is not a reference type,
    // result_of::child_c<Expr, 0>::type is a
    // non-cv qualified, non-reference type:
    BOOST_MPL_ASSERT((
        boost::is_same< type, proto::terminal<int>::type >
    ));
}

// ...
proto::terminal<int>::type i = {42};
test_result_of_child_c( i + 2 );

However, if you ask for the type of the Nth child of Expr & or Expr const & (note the reference), the result type will be a reference, regardless of whether the child is actually stored by reference or not. If you need to know exactly how the child is stored in the node, whether by reference or by value, you can use fusion::result_of::value_at<Expr, N>::type. The following table summarizes the behavior of the proto::result_of::child_c<> metafunction.

typename boost::remove_const<
    typename boost::remove_reference<T>::type
>::type

typename boost::add_reference<T>::type

typename boost::add_reference<
    typename boost::add_const<T>::type
>::type

Common Shortcuts

Most operators in C++ are unary or binary, so accessing the only operand, or the left and right operands, are very common operations. For this reason, Proto provides the proto::child(), proto::left(), and proto::right() functions. proto::child() and proto::left() are synonymous with proto::child_c<0>(), and proto::right() is synonymous with proto::child_c<1>().

There are also proto::result_of::child<>, proto::result_of::left<>, and proto::result_of::right<> metafunctions that merely forward to their proto::result_of::child_c<> counterparts.

When you build an expression template with Proto, all the intermediate child nodes are held by reference. The avoids needless copies, which is crucial if you want your DSEL to perform well at runtime. Naturally, there is a danger if the temporary objects go out of scope before you try to evaluate your expression template. This is especially a problem in C++0x with the new decltype and auto keywords. Consider:

// OOPS: "ex" is left holding dangling references
auto ex = proto::lit(1) + 2;

The problem can happen in today's C++ also if you use BOOST_TYPEOF() or BOOST_AUTO(), or if you try to pass an expression template outside the scope of its constituents.

In these cases, you want to deep-copy your expression template so that all intermediate nodes and the terminals are held by value. That way, you can safely assign the expression template to a local variable or return it from a function without worrying about dangling references. You can do this with proto::deep_copy() as fo llows:

// OK, "ex" has no dangling references
auto ex = proto::deep_copy( proto::lit(1) + 2 );

If you are using Boost.Typeof, it would look like this:

// OK, use BOOST_AUTO() and proto::deep_copy() to
// store an expression template in a local variable 
BOOST_AUTO( ex, proto::deep_copy( proto::lit(1) + 2 ) );

For the above code to work, you must include the boost/proto/proto_typeof.hpp header, which also defines the BOOST_PROTO_AUTO() macro which automatically deep-copies its argument. With BOOST_PROTO_AUTO(), the above code can be writen as:

// OK, BOOST_PROTO_AUTO() automatically deep-copies
// its argument: 
BOOST_PROTO_AUTO( ex, proto::lit(1) + 2 );

When deep-copying an expression tree, all intermediate nodes and all terminals are stored by value. The only exception is terminals that are function references, which are left alone.

	Note
	proto::deep_copy() makes no exception for arrays, which it stores by value. That can potentially cause a large amount of data to be copied.

Proto provides a utility for pretty-printing expression trees that comes in very handy when you're trying to debug your DSEL. It's called proto::display_expr(), and you pass it the expression to print and optionally, an std::ostream to which to send the output. Consider:

// Use display_expr() to pretty-print an expression tree
proto::display_expr(
    proto::lit("hello") + 42
);

The above code writes this to std::cout:

plus(
    terminal(hello)
  , terminal(42)
)

In order to call proto::display_expr(), all the terminals in the expression must be Streamable (that is, they can be written to a std::ostream). In addition, the tag types must all be Streamable as well. Here is an example that includes a custom terminal type and a custom tag:

// A custom tag type that is Streamable
struct MyTag
{
    friend std::ostream &operator<<(std::ostream &s, MyTag)
    {
        return s << "MyTag";
    }
};

// Some other Streamable type
struct MyTerminal
{
    friend std::ostream &operator<<(std::ostream &s, MyTerminal)
    {
        return s << "MyTerminal";
    }
};

int main()
{
    // Display an expression tree that contains a custom
    // tag and a user-defined type in a terminal
    proto::display_expr(
        proto::make_expr<MyTag>(MyTerminal()) + 42
    );
}

The above code prints the following:

plus(
    MyTag(
        terminal(MyTerminal)
    )
  , terminal(42)
)

The following table lists the overloadable C++ operators, the Proto tag types for each, and the name of the metafunctions for generating the corresponding Proto expression types. And as we'll see later, the metafunctions are also usable as grammars for matching such nodes, as well as pass-through transforms.

Boost.Fusion is a library of iterators, algorithms, containers and adaptors for manipulating heterogeneous sequences. In essence, a Proto expression is just a heterogeneous sequence of its child expressions, and so Proto expressions are valid Fusion random-access sequences. That means you can apply Fusion algorithms to them, transform them, apply Fusion filters and views to them, and access their elements using fusion::at(). The things Fusion can do to heterogeneous sequences are beyond the scope of this users' guide, but below is a simple example. It takes a lazy function invocation like fun(1,2,3,4) and uses Fusion to print the function arguments in order.

struct display
{
    template<typename T>
    void operator()(T const &t) const
    {
        std::cout << t << std::endl;
    }
};

struct fun_t {};
proto::terminal<fun_t>::type const fun = {{}};

// ...
fusion::for_each(
    fusion::transform(
        // pop_front() removes the "fun" child
        fusion::pop_front(fun(1,2,3,4))
        // Extract the ints from the terminal nodes
      , proto::functional::value()
    )
  , display()
);

Recall from the Introduction that types in the proto::functional namespace define function objects that correspond to Proto's free functions. So proto::functional::value() creates a function object that is equivalent to the proto::value() function. The above invocation of fusion::for_each() displays the following:

1
2
3
4

Terminals are also valid Fusion sequences. They contain exactly one element: their value.

Flattening Proto Expression Tress

Imagine a slight variation of the above example where, instead of iterating over the arguments of a lazy function invocation, we would like to iterate over the terminals in an addition expression:

proto::terminal<int>::type const _1 = {1};

// ERROR: this doesn't work! Why?
fusion::for_each(
    fusion::transform(
        _1 + 2 + 3 + 4
      , proto::functional::value()
    )
  , display()
);

The reason this doesn't work is because the expression _1 + 2 + 3 + 4 does not describe a flat sequence of terminals --- it describes a binary tree. We can treat it as a flat sequence of terminals, however, using Proto's proto::flatten() function. proto::flatten() returns a view which makes a tree appear as a flat Fusion sequence. If the top-most node has a tag type T, then the elements of the flattened sequence are the child nodes that do not have tag type T. This process is evaluated recursively. So the above can correctly be written as:

proto::terminal<int>::type const _1 = {1};

// OK, iterate over a flattened view
fusion::for_each(
    fusion::transform(
        proto::flatten(_1 + 2 + 3 + 4)
      , proto::functional::value()
    )
  , display()
);

The above invocation of fusion::for_each() displays the following:

1
2
3
4

Expression trees can have a very rich and complicated structure. Often, you need to know some things about an expression's structure before you can process it. This section describes the tools Proto provides for peering inside an expression tree and discovering its structure. And as you'll see in later sections, all the really interesting things you can do with Proto begin right here.

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

struct Input
  : proto::shift_right< proto::terminal< std::istream & >, proto::_ >
{};

struct Output
  : proto::shift_left< proto::terminal< std::ostream & >, proto::_ >
{};

template< typename Expr >
void input_output( Expr const & expr )
{
    if( proto::matches< Expr, Input >::value )
    {
        std::cout << "Input!\n";
    }

    if( proto::matches< Expr, Output >::value )
    {
        std::cout << "Output!\n";
    }
}

int main()
{
    int i = 0;
    input_output( cout_ << 1 );
    input_output( cin_ >> i );

    return 0;
}

Output!
Input!

template< typename Expr >
typename boost::enable_if< proto::matches< Expr, Input > >::type
input_output( Expr const & expr )
{
    std::cout << "Input!\n";
}

template< typename Expr >
typename boost::enable_if< proto::matches< Expr, Output > >::type
input_output( Expr const & expr )
{
    std::cout << "Output!\n";
}

input_output( cout_ << 1 << 2 ); // oops!

struct Input
  : proto::or_<
        proto::shift_right< proto::terminal< std::istream & >, proto::_ >
      , proto::shift_right< Input, proto::_ >
    >
{};

struct Output
  : proto::or_<
        proto::shift_left< proto::terminal< std::ostream & >, proto::_ >
      , proto::shift_left< Output, proto::_ >
    >
{};

struct CharString
  : proto::terminal< char const * >
{};

typedef proto::terminal< char const[6] >::type char_array;

BOOST_MPL_ASSERT(( proto::matches< char_array, CharString > ));

struct CharString
  : proto::terminal< proto::exact< char const * > >
{};

typedef proto::terminal<char const[6]>::type char_array;
typedef proto::terminal<char const *>::type  char_string;

BOOST_MPL_ASSERT(( proto::matches< char_string, CharString > ));
BOOST_MPL_ASSERT_NOT(( proto::matches< char_array, CharString > ));

struct StdComplex
  : proto::terminal< std::complex< proto::_ > >
{};

struct CharString
  : proto::and_<
        proto::terminal< proto::_ >
      , proto::if_< boost::is_same< proto::_value, char const * >() >
    >
{};

Improving Compile Times With switch_<>

When your Proto grammar gets large, you'll start to run into some scalability problems with proto::or_<>, the construct you use to specify alternate sub-grammars. First, due to limitations in C++, proto::or_<> can only accept up to a certain number of sub-grammars, controlled by the BOOST_PROTO_MAX_LOGICAL_ARITY macro. This macro defaults to eight, and you can set it higher, but doing so will aggravate another scalability problem: long compile times. With proto::or_<>, alternate sub-grammars are tried in order -- like a series of cascading if's -- leading to lots of unnecessary template instantiations. What you would prefer instead is something like switch that avoids the expense of cascading if's. That's the purpose of proto::switch_<>; although less convenient than proto::or_<>, it improves compile times for larger grammars and does not have an arbitrary fixed limit on the number of sub-grammars.

Let's illustrate how to use proto::switch_<> by first writing a big grammar with proto::or_<> and then translating it to an equivalent grammar using proto::switch_<>:

// Here is a big, inefficient grammar
struct ABigGrammar
  : proto::or_<
        proto::terminal<int>
      , proto::terminal<double>
      , proto::unary_plus<ABigGrammar>
      , proto::negate<ABigGrammar>
      , proto::complement<ABigGrammar>
      , proto::plus<ABigGrammar, ABigGrammar>
      , proto::minus<ABigGrammar, ABigGrammar>
      , proto::or_<
            proto::multiplies<ABigGrammar, ABigGrammar>
          , proto::divides<ABigGrammar, ABigGrammar>
          , proto::modulus<ABigGrammar, ABigGrammar>
        >
    >
{};

The above might be the grammar to a more elaborate calculator DSEL. Notice that since there are more than eight sub-grammars, we had to chain the sub-grammars with a nested proto::or_<> -- not very nice.

The idea behind proto::switch_<> is to dispatch based on an expression's tag type to a sub-grammar that handles expressions of that type. To use proto::switch_<>, you define a struct with a nested case_<> template, specialized on tag types. The above grammar can be expressed using proto::switch_<> as follows. It is described below.

// Redefine ABigGrammar more efficiently using proto::switch_<>
struct ABigGrammar;

struct ABigGrammarCases
{
    // The primary template matches nothing:
    template<typename Tag>
    struct case_
      : proto::not_<_>
    {};
};

// Terminal expressions are handled here
template<>
struct ABigGrammarCases::case_<proto::tag::terminal>
  : proto::or_<
        proto::terminal<int>
      , proto::terminal<double>
    >
{};

// Non-terminals are handled similarly
template<>
struct ABigGrammarCases::case_<proto::tag::unary_plus>
  : proto::unary_plus<ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::negate>
  : proto::negate<ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::complement>
  : proto::complement<ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::plus>
  : proto::plus<ABigGrammar, ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::minus>
  : proto::minus<ABigGrammar, ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::multiplies>
  : proto::multiplies<ABigGrammar, ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::divides>
  : proto::divides<ABigGrammar, ABigGrammar>
{};

template<>
struct ABigGrammarCases::case_<proto::tag::modulus>
  : proto::modulus<ABigGrammar, ABigGrammar>
{};

// Define ABigGrammar in terms of ABigGrammarCases
// using proto::switch_<>
struct ABigGrammar
  : proto::switch_<ABigGrammarCases>
{};

Matching an expression type E against proto::switch_<C> is equivalent to matching it against C::case_<E::proto_tag>. By dispatching on the expression's tag type, we can jump to the sub-grammar that handles expressions of that type, skipping over all the other sub-grammars that couldn't possibly match. If there is no specialization of case_<> for a particular tag type, we select the primary template. In this case, the primary template inherits from proto::not_<_> which matches no expressions.

Notice the specialization that handles terminals:

// Terminal expressions are handled here
template<>
struct ABigGrammarCases::case_<proto::tag::terminal>
  : proto::or_<
        proto::terminal<int>
      , proto::terminal<double>
    >
{};

The proto::tag::terminal type by itself isn't enough to select an appropriate sub-grammar, so we use proto::or_<> to list the alternate sub-grammars that match terminals.

Note

You might be tempted to define your case_<> specializations in situ as follows: struct ABigGrammarCases { template<typename Tag> struct case_ : proto::not_<_> {}; // ERROR: not legal C++ template<> struct case_<proto::tag::terminal> /* ... */ }; Unfortunately, for arcane reasons, it is not legal to define an explicit nested specialization in situ like this. It is, however, perfectly legal to define partial specializations in situ, so you can add a extra dummy template parameter that has a default, as follows: struct ABigGrammarCases { // Note extra "Dummy" template parameter here: template<typename Tag, int Dummy = 0> struct case_ : proto::not_<_> {}; // OK: "Dummy" makes this a partial specialization // instead of an explicit specialization. template<int Dummy> struct case_<proto::tag::terminal, Dummy> /* ... */ }; You might find this cleaner than defining explicit case_<> specializations outside of their enclosing struct.

struct fun_tag {};
struct FunTag : proto::terminal< fun_tag > {};
FunTag::type const fun = {{}};

// example usage:
fun();
fun('a');
fun('a', 'b');
...

struct FunCall
  : proto::function< FunTag, proto::vararg< proto::terminal< char > > >
{};

struct Foo
  : proto::or_<
        proto::terminal< proto::_ >
      , proto::nary_expr< proto::_, proto::vararg< Foo > >
    >
{};