| Home | Libraries | People | FAQ | More

## Users' Guide

#### 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 Started

#### Installing Proto

###### 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
Please send any questions, comments and bug reports to eric <at> boostpro <dot> com.

#### Naming Conventions

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 20.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`

#### Hello World

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 Calculator

"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
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
`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!

### Fronts Ends: Defining Terminals and Non-Terminals of Your EDSL

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.

#### Making Terminals

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;

#### Proto's Operator Overloads

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

#### Making Lazy Functions

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

#### Customizing Expressions in Your Domain

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.

##### Domains

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 `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 20.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.

##### Expression Generators

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. But since we've specified a generator above, `calculator_domain::operator()` returns `calculator<>` objects.

Now we can use calculator expressions as function objects to STL algorithms, as follows:

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

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

##### Controlling Operator Overloads

By default, Proto defines every possible operator overload for Protofied expressions. This makes it simple to bang together an EDSL. In some cases, however, the presence of Proto's promiscuous overloads can lead to confusion or worse. When that happens, you'll have to disable some of Proto's overloaded operators. That is done by defining the grammar for your domain and specifying it as the second parameter of the `proto::domain<>` template.

In the Hello Calculator section, we saw an example of a Proto grammar, which is repeated here:

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

We'll have much more to say about grammars in subsequent sections, but for now, we'll just say that the `calculator_grammar` struct describes a subset of all expression types -- the subset that comprise valid calculator expressions. We would like to prohibit Proto from creating a calculator expression that does not conform to this grammar. We do that by changing the definition of the `calculator_domain` struct.

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

The only new addition is `calculator_grammar` as the second template parameter to the `proto::domain<>` template. That has the effect of disabling any of Proto's operator overloads that would create an invalid calculator expression.

Another common use for this feature would be to disable Proto's unary `operator&` overload. It may be surprising for users of your EDSL that they cannot take the address of their expressions! You can very easily disable Proto's unary `operator&` overload for your domain with a very simple grammar, as below:

    // 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 type `proto::not_< proto::address_of< _ > >` is a very simple grammar that matches all expressions except unary address-of expressions. In the section describing Proto's intermediate form, we'll have much more to say about grammars.

##### Controlling How Child Expressions Are Captured

| Note
This is an advanced topic. Feel free to skip this if you're just getting started with Proto.

Proto's operator overloads build expressions from sub-expressions. The sub-expressions become children of the new expression. By default, the children are stored in the parent by reference. This section describes how to change that default.

###### Primer: `as_child` vs. `as_expr`

Proto lets you independently customize the behavior of `proto::as_child()` and `proto::as_expr()`. Both accept an object `x` and return a Proto expression by turning `x` it into a Proto terminal if necessary. Although similar, the two functions are used in different situations and have subtly different behavior by default. It's important to understand the difference so that you know which to customize to achieve the behavior you want.

To wit: `proto::as_expr()` is typically used by you to turn an object into a Proto expression that is to be held in a local variable, as so:

    auto l = proto::as_expr(x); // Turn x into a Proto expression, hold the result in a local

The above works regardless of whether `x` is already a Proto expression or not. The object `l` is guaranteed to be a valid Proto expression. If `x` is a non-Proto object, it is turned into a terminal expression that holds `x` by value.[5] If `x` is a Proto object already, `proto::as_expr()` returns it by value unmodified.

In contrast, `proto::as_child()` is used internally by Proto to pre-process objects before making them children of another expression. Since it's internal to Proto, you don't see it explicitly, but it's there behind the scenes in expressions like this:

    x + y; // Consider that y is a Proto expression, but x may or may not be.

In this case, Proto builds a plus node from the two children. Both are pre-processed by passing them to `proto::as_child()` before making them children of the new node. If `x` is not a Proto expression, it becomes one by being wrapped in a Proto terminal that holds it by reference. If `x` is already a Proto expression, `proto::as_child()` returns it by reference unmodified. Contrast this with the above description for `proto::as_expr()`.

The table below summarizes the above description.

Table 20.3. proto::as_expr() vs. proto::as_child()

Function | When `t` is not a Proto expr... | When `t` is a Proto expr...
--- | --- | ---
`proto::as_expr(t)` | Return (by value) a new Proto terminal holding `t` by value. | Return `t` by value unmodified.
`proto::as_child(t)` | Return (by value) a new Proto terminal holding `t` by reference. | Return `t` by reference unmodified.

| Note
There is one important place where Proto uses both `as_expr` and `as_child`: `proto::make_expr()`. The `proto::make_expr()` function requires you to specify for each child whether it should be held by value or by reference. Proto uses `proto::as_expr()` to pre-process the children to be held by value, and `proto::as_child()` for the ones to be held by reference.

Now that you know what `proto::as_child()` and `proto::as_expr()` are, where they are used, and what they do by default, you may decide that one or both of these functions should have different behavior for your domain. For instance, given the above description of `proto::as_child()`, the following code is always wrong:

    proto::literal<int> i(0);
    auto l = i + 42; // This is WRONG! Don't do this.

Why is this wrong? Because `proto::as_child()` will turn the integer literal 42 into a Proto terminal that holds a reference to a temporary integer initialized with 42. The lifetime of that temporary ends at the semicolon, guaranteeing that the local `l` is left holding a dangling reference to a deceased integer. What to do? One answer is to use `proto::deep_copy()`. Another is to customize the behavior of `proto::as_child()` for your domain. Read on for the details.

###### Per-Domain `as_child`

To control how Proto builds expressions out of sub-expressions in your domain, define your domain as usual, and then define a nested `as_child<>` class template within it, as follows:

    class my_domain
      : proto::domain< my_generator, my_grammar >
    {
        // Here is where you define how Proto should handle
        // sub-expressions that are about to be glommed into
        // a larger expression.
        template< typename T >
        struct as_child
        {
            typedef unspecified-Proto-expr-type result_type;

            result_type operator()( T & t ) const
            {
                return unspecified-Proto-expr-object;
            }
        };
    };

There's one important thing to note: in the above code, the template parameter `T` may or may not be a Proto expression type, but the result must be a Proto expression type, or a reference to one. That means that most user-defined `as_child<>` templates will need to check whether `T` is an expression or not (using `proto::is_expr<>`), and then turn non-expressions into Proto terminals by wrapping them as `proto::terminal< /* ... */ >::type` or equivalent.

###### Per-Domain `as_expr`

Although less common, Proto also lets you customize the behavior of `proto::as_expr()` on a per-domain basis. The technique is identical to that for `as_child`. See below:

    class my_domain
      : proto::domain< my_generator, my_grammar >
    {
        // Here is where you define how Proto should handle
        // objects that are to be turned into expressions
        // fit for storage in local variables.
        template< typename T >
        struct as_expr
        {
            typedef unspecified-Proto-expr-type result_type;

            result_type operator()( T & t ) const
            {
                return unspecified-Proto-expr-object;
            }
        };
    };

###### Making Proto Expressions `auto`-safe

Let's look again at the problem described above involving the C++11 `auto` keyword and the default behavior of `proto::as_child()`.

    proto::literal<int> i(0);
    auto l = i + 42; // This is WRONG! Don't do this.

Recall that the problem is the lifetime of the temporary integer created to hold the value 42. The local `l` will be left holding a dangling reference to it after its lifetime is over. What if we want Proto to make expressions safe to store this way in local variables? We can do so very easily by making `proto::as_child()` behave just like `proto::as_expr()`. The following code achieves this:

    template< typename E >
    struct my_expr;

    struct my_generator
      : proto::pod_generator< my_expr >
    {};

    struct my_domain
      : proto::domain< my_generator >
    {
         // Make as_child() behave like as_expr() in my_domain.
         // (proto_base_domain is a typedef for proto::domain< my_generator >
         // that is defined in proto::domain<>.)
         template< typename T >
         struct as_child
           : proto_base_domain::as_expr< T >
         {};
    };

    template< typename E >
    struct my_expr
    {
        BOOST_PROTO_EXTENDS( E, my_expr< E >, my_domain )
    };

    /* ... */

    proto::literal< int, my_domain > i(0);
    auto l = i + 42; // OK! Everything is stored by value here.

Notice that `my_domain::as_child<>` simply defers to the default implementation of `as_expr<>` found in `proto::domain<>`. By simply cross-wiring our domain's `as_child<>` to `as_expr<>`, we guarantee that all terminals that can be held by value are, and that all child expressions are also held by value. This increases copying and may incur a runtime performance cost, but it eliminates any spector of lifetime management issues.

For another example, see the definition of `lldomain` in `libs/proto/example/lambda.hpp`. That example is a complete reimplementation of the Boost Lambda Library (BLL) on top of Boost.Proto. The function objects the BLL generates are safe to be stored in local variables. To emulate this with Proto, the `lldomain` cross-wires `as_child<>` to `as_expr<>` as above, but with one extra twist: objects with array type are also stored by reference. Check it out.

##### EDSL Interoperatability: Sub-Domains

| Note
This is an advanced topic. Feel free to skip this if you're just getting started with Proto.

The ability to compose different EDSLs is one of their most exciting features. Consider how you build a parser using yacc. You write your grammar rules in yacc's domain-specific language. Then you embed semantic actions written in C within your grammar. Boost's Spirit parser generator gives you the same ability. You write grammar rules using Spirit.Qi and embed semantic actions using the Phoenix library. Phoenix and Spirit are both Proto-based domain-specific languages with their own distinct syntax and semantics. But you can freely embed Phoenix expressions within Spirit expressions. This section describes Proto's sub-domain feature that lets you define families of interoperable domains.

###### Dueling Domains

When you try to create an expression from two sub-expressions in different domains, what is the domain of the resulting expression? This is the fundamental problem that is addressed by sub-domains. Consider the following code:

    #include <boost/proto/proto.hpp>
    namespace proto = boost::proto;

    // Forward-declare two expression wrappers
    template<typename E> struct spirit_expr;
    template<typename E> struct phoenix_expr;

    // Define two domains
    struct spirit_domain  : proto::domain<proto::generator<spirit_expr> > {};
    struct phoenix_domain : proto::domain<proto::generator<phoenix_expr> > {};

    // Implement the two expression wrappers
    template<typename E>
    struct spirit_expr
      : proto::extends<E, spirit_expr<E>, spirit_domain>
    {
        spirit_expr(E const &e = E()) : spirit_expr::proto_extends(e) {}
    };

    template<typename E>
    struct phoenix_expr
      : proto::extends<E, phoenix_expr<E>, phoenix_domain>
    {
        phoenix_expr(E const &e = E()) : phoenix_expr::proto_extends(e) {}
    };

    int main()
    {
        proto::literal<int, spirit_domain> sp(0);
        proto::literal<int, phoenix_domain> phx(0);

        // Whoops! What does it mean to add two expressions in different domains?
        sp + phx; // ERROR
    }

Above, we define two domains called `spirit_domain` and `phoenix_domain` and declare two int literals in each. Then we try to compose them into a larger expression using Proto's binary plus operator, and it fails. Proto can't figure out whether the resulting expression should be in the Spirit domain or the Phoenix domain, and thus whether it should be an instance of `spirit_expr<>` or `phoenix_expr<>`. We have to tell Proto how to resolve the conflict. We can do that by declaring that Phoenix is a sub-domain of Spirit as in the following definition of `phoenix_domain`:

    // Declare that phoenix_domain is a sub-domain of spirit_domain
    struct phoenix_domain
      : proto::domain<proto::generator<phoenix_expr>, proto::_, spirit_domain>
    {};

The third template parameter to `proto::domain<>` is the super-domain. By defining `phoenix_domain` as above, we are saying that Phoenix expressions can be combined with Spirit expressions, and that when that happens, the resulting expression should be a Spirit expression.

| Note
If you are wondering what the purpose of `proto::_` is in the definition of `phoenix_domain` above, recall that the second template parameter to `proto::domain<>` is the domain's grammar. “`proto::_`” is the default and signifies that the domain places no restrictions on the expressions that are valid within it.

###### Domain Resolution

When there are multiple domains in play within a given expression, Proto uses some rules to figure out which domain "wins". The rules are loosely modeled on the rules for C++ inheritance. `Phoenix_domain` is a sub-domain of `spirit_domain`. You can liken that to a derived/base relationship that gives Phoenix expressions a kind of implicit conversion to Spirit expressions. And since Phoenix expressions can be "converted" to Spirit expressions, they can be freely combined with Spirit expressions and the result is a Spirit expression.

| Note
Super- and sub-domains are not actually implemented using inheritance. This is only a helpful mental model.

The analogy with inheritance holds even in the case of three domains when two are sub-domains of the third. Imagine another domain called `foobar_domain` that was also a sub-domain of `spirit_domain`. Expressions in the `foobar_domain` could be combined with expressions in the `phoenix_domain` and the resulting expression would be in the `spirit_domain`. That's because expressions in the two sub-domains both have "conversions" to the super-domain, so the operation is allowed and the super-domain wins.

###### The Default Domain

When you don't assign a Proto expression to a particular domain, Proto considers it a member of the so-called default domain, `proto::default_domain`. Even non-Proto objects are treated as terminals in the default domain. Consider:

    int main()
    {
        proto::literal<int, spirit_domain> sp(0);

        // Add 1 to a spirit expression. Result is a spirit expression.
        sp + 1;
    }

Expressions in the default domain (or non-expressions like `1`) have a kind of implicit conversion to expressions every other domain type. What's more, you can define your domain to be a sub-domain of the default domain. In so doing, you give expressions in your domain conversions to expressions in every other domain. This is like a “free love” domain, because it will freely mix with all other domains.

Let's think again about the Phoenix EDSL. Since it provides generally useful lambda functionality, it's reasonable to assume that lots of other EDSLs besides Spirit might want the ability to embed Phoenix expressions. In other words, `phoenix_domain` should be a sub-domain of `proto::default_domain`, not `spirit_domain`:

    // Declare that phoenix_domain is a sub-domain of proto::default_domain
    struct phoenix_domain
      : proto::domain<proto::generator<phoenix_expr>, proto::_, proto::default_domain>
    {};

That's much better. Phoenix expressions can now be put anywhere.

###### Sub-Domain Summary

Use Proto sub-domains to make it possible to mix expressions from multiple domains. And when you want expressions in your domain to freely combine with all expressions, make it a sub-domain of `proto::default_domain`.

#### Adapting Existing Types to Proto

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:

1. Define a trait that returns true for your types and false for all others.
2. Reopen the namespace of your types and use ``BOOST_PROTO_DEFINE_OPERATORS`()` to define a set of operator overloads, passing the name of the trait as the first macro parameter, and the name of a Proto domain (e.g., `proto::default_domain`) as the second.

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.

#### Generating Repetitive Code with the Preprocessor

Sometimes as an EDSL 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 EDSL, 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.

### Intermediate Form: Understanding and Introspecting Expressions

By now, you know a bit about how to build a front-end for your EDSL "compiler" -- you can define terminals and functions that generate expression templates. But we haven't said anything about the expression templates themselves. What do they look like? What can you do with them? In this section we'll see.

##### The `expr<>` Type

All Proto expressions are an instantiation of a template called `proto::expr<>` (or a wrapper around such an instantiation). When we define a terminal as below, we are really initializing an instance of the `proto::expr<>` template.

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

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

The actual type of `_1` looks like this:

    proto::expr< proto::tag::terminal, proto::term< placeholder<0> >, 0 >

The `proto::expr<>` template is the most important type in Proto. Although you will rarely need to deal with it directly, it's always there behind the scenes holding your expression trees together. In fact, `proto::expr<>` is the expression tree -- branches, leaves and all.

The `proto::expr<>` template makes up the nodes in expression trees. The first template parameter is the node type; in this case, `proto::tag::terminal`. That means that `_1` is a leaf-node in the expression tree. The second template parameter is a list of child types, or in the case of terminals, the terminal's value type. Terminals will always have only one type in the type list. The last parameter is the arity of the expression. Terminals have arity 0, unary expressions have arity 1, etc.

The `proto::expr<>` struct is defined as follows:

    template< typename Tag, typename Args, long Arity = Args::arity >
    struct expr;

    template< typename Tag, typename Args >
    struct expr< Tag, Args, 1 >
    {
        typedef typename Args::child0 proto_child0;
        proto_child0 child0;
        // ...
    };

The `proto::expr<>` struct does not define a constructor, or anything else that would prevent static initialization. All `proto::expr<>` objects are initialized using aggregate initialization, with curly braces. In our example, `_1` is initialized with the initializer `{{}}`. The outer braces are the initializer for the `proto::expr<>` struct, and the inner braces are for the member `_1.child0` which is of type `placeholder<0>`. Note that we use braces to initialize `_1.child0` because `placeholder<0>` is also an aggregate.

##### Building Expression Trees

The `_1` node is an instantiation of `proto::expr<>`, and expressions containing `_1` are also instantiations of `proto::expr<>`. To use Proto effectively, you won't have to bother yourself with the actual types that Proto generates. These are details, but you're likely to encounter these types in compiler error messages, so it's helpful to be familiar with them. The types look like this:

    // The type of the expression -_1
    typedef
        proto::expr<
            proto::tag::negate
          , proto::list1<
                proto::expr<
                    proto::tag::terminal
                  , proto::term< placeholder<0> >
                  , 0
                > const &
            >
          , 1
        >
    negate_placeholder_type;

    negate_placeholder_type x = -_1;

    // The type of the expression _1 + 42
    typedef
        proto::expr<
            proto::tag::plus
          , proto::list2<
                proto::expr<
                    proto::tag::terminal
                  , proto::term< placeholder<0> >
                  , 0
                > const &
              , proto::expr<
                    proto::tag::terminal
                  , proto::term< int const & >
                  , 0
                >
            >
          , 2
        >
    placeholder_plus_int_type;

    placeholder_plus_int_type y = _1 + 42;

There are a few things to note about these types:

- Terminals have arity zero, unary expressions have arity one and binary expressions have arity two.
- When one Proto expression is made a child node of another Proto expression, it is held by reference, even if it is a temporary object. This last point becomes important later.
- Non-Proto expressions, such as the integer literal, are turned into Proto expressions by wrapping them in new `expr<>` terminal objects. These new wrappers are not themselves held by reference, but the object wrapped is. Notice that the type of the Protofied `42` literal is `int const &` -- held by reference.

The types make it clear: everything in a Proto expression tree is held by reference. That means that building an expression tree is exceptionally cheap. It involves no copying at all.

| Note
An astute reader will notice that the object `y` defined above will be left holding a dangling reference to a temporary int. In the sorts of high-performance applications Proto addresses, it is typical to build and evaluate an expression tree before any temporary objects go out of scope, so this dangling reference situation often doesn't arise, but it is certainly something to be aware of. Proto provides utilities for deep-copying expression trees so they can be passed around as value types without concern for dangling references.

#### Accessing Parts of an Expression

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.

Table 20.4. Accessing Value Types

Metafunction Invocation | When the Value Type Is ... | The Result Is ...
--- | --- | ---
`proto::result_of::value<Expr>::type` | `T` |
    typename boost::remove_const<
        typename boost::remove_reference<T>::type
    >::type [a]
`proto::result_of::value<Expr &>::type` | `T` |
    typename boost::add_reference<T>::type
`proto::result_of::value<Expr const &>::type` | `T` |
    typename boost::add_reference<
        typename boost::add_const<T>::type
    >::type
`fusion::result_of::value_at<Expr, 0>::type` | `T` | `T`
[a] If `T` is a reference-to-function type, then the result type is simply `T`.

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

Table 20.5. Accessing Child Types

Metafunction Invocation | When the Child Is ... | The Result Is ...
--- | --- | ---
`proto::result_of::child_c<Expr, N>::type` | `T` |
    typename boost::remove_const<
        typename boost::remove_reference<T>::type
    >::type
`proto::result_of::child_c<Expr &, N>::type` | `T` |
    typename boost::add_reference<T>::type
`proto::result_of::child_c<Expr const &, N>::type` | `T` |
    typename boost::add_reference<
        typename boost::add_const<T>::type
    >::type
`fusion::result_of::value_at<Expr, N>::type` | `T` | `T`

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

#### Deep-copying Expressions

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

#### Debugging Expressions

Proto provides a utility for pretty-printing expression trees that comes in very handy when you're trying to debug your EDSL. 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)
    )

#### Operator Tags and Metafunctions

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.

Table 20.6. Operators, Tags and Metafunctions

Operator | Proto Tag | Proto Metafunction
--- | --- | ---
unary `+` | `proto::tag::unary_plus` | `proto::unary_plus<>`
unary `-` | `proto::tag::negate` | `proto::negate<>`
unary `*` | `proto::tag::dereference` | `proto::dereference<>`
unary `~` | `proto::tag::complement` | `proto::complement<>`
unary `&` | `proto::tag::address_of` | `proto::address_of<>`
unary `!` | `proto::tag::logical_not` | `proto::logical_not<>`
unary prefix `++` | `proto::tag::pre_inc` | `proto::pre_inc<>`
unary prefix `--` | `proto::tag::pre_dec` | `proto::pre_dec<>`
unary postfix `++` | `proto::tag::post_inc` | `proto::post_inc<>`
unary postfix `--` | `proto::tag::post_dec` | `proto::post_dec<>`
binary `<<` | `proto::tag::shift_left` | `proto::shift_left<>`
binary `>>` | `proto::tag::shift_right` | `proto::shift_right<>`
binary `*` | `proto::tag::multiplies` | `proto::multiplies<>`
binary `/` | `proto::tag::divides` | `proto::divides<>`
binary `%` | `proto::tag::modulus` | `proto::modulus<>`
binary `+` | `proto::tag::plus` | `proto::plus<>`
binary `-` | `proto::tag::minus` | `proto::minus<>`
binary `<` | `proto::tag::less` | `proto::less<>`
binary `>` | `proto::tag::greater` | `proto::greater<>`
binary `<=` | `proto::tag::less_equal` | `proto::less_equal<>`
binary `>=` | `proto::tag::greater_equal` | `proto::greater_equal<>`
binary `==` | `proto::tag::equal_to` | `proto::equal_to<>`
binary `!=` | `proto::tag::not_equal_to` | `proto::not_equal_to<>`
binary `||` | `proto::tag::logical_or` | `proto::logical_or<>`
binary `&&` | `proto::tag::logical_and` | `proto::logical_and<>`
binary `&` | `proto::tag::bitwise_and` | `proto::bitwise_and<>`
binary `|` | `proto::tag::bitwise_or` | `proto::bitwise_or<>`
binary `^` | `proto::tag::bitwise_xor` | `proto::bitwise_xor<>`
binary `,` | `proto::tag::comma` | `proto::comma<>`
binary `->*` | `proto::tag::mem_ptr` | `proto::mem_ptr<>`
binary `=` | `proto::tag::assign` | `proto::assign<>`
binary `<<=` | `proto::tag::shift_left_assign` | `proto::shift_left_assign<>`
binary `>>=` | `proto::tag::shift_right_assign` | `proto::shift_right_assign<>`
binary `*=` | `proto::tag::multiplies_assign` | `proto::multiplies_assign<>`
binary `/=` | `proto::tag::divides_assign` | `proto::divides_assign<>`
binary `%=` | `proto::tag::modulus_assign` | `proto::modulus_assign<>`
binary `+=` | `proto::tag::plus_assign` | `proto::plus_assign<>`
binary `-=` | `proto::tag::minus_assign` | `proto::minus_assign<>`
binary `&=` | `proto::tag::bitwise_and_assign` | `proto::bitwise_and_assign<>`
binary `|=` | `proto::tag::bitwise_or_assign` | `proto::bitwise_or_assign<>`
binary `^=` | `proto::tag::bitwise_xor_assign` | `proto::bitwise_xor_assign<>`
binary subscript | `proto::tag::subscript` | `proto::subscript<>`
ternary `?:` | `proto::tag::if_else_` | `proto::if_else_<>`
n-ary function call | `proto::tag::function` | `proto::function<>`

#### Expressions as Fusion Sequences

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 Introspection: Defining a Grammar

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.

##### Finding Patterns in Expressions

Imagine your EDSL is a miniature I/O facility, with iostream operations that execute lazily. You might want expressions representing input operations to be processed by one function, and output operations to be processed by a different function. How would you do that?

The answer is to write patterns (a.k.a, grammars) that match the structure of input and output expressions. Proto provides utilities for defining the grammars, and the `proto::matches<>` template for checking whether a given expression type matches the grammar.

First, let's define some terminals we can use in our lazy I/O expressions:

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

Now, we can use `cout_` instead of `std::cout`, and get I/O expression trees that we can execute later. To define grammars that match input and output expressions of the form `cin_ >> i` and `cout_ << 1` we do this:

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

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

We've seen the template `proto::terminal<>` before, but here we're using it without accessing the nested `::type`. When used like this, it is a very simple grammar, as are `proto::shift_right<>` and `proto::shift_left<>`. The newcomer here is `_` in the `proto` namespace. It is a wildcard that matches anything. The `Input` struct is a grammar that matches any right-shift expression that has a `std::istream` terminal as its left operand.

We can use these grammars together with the `proto::matches<>` template to query at compile time whether a given I/O expression type is an input or output operation. Consider the following:

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

This program prints the following:

    Output!
    Input!

If we wanted to break the `input_output()` function into two functions, one that handles input expressions and one for output expressions, we can use `boost::enable_if<>`, as follows:

    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";
    }

This works as the previous version did. However, the following does not compile at all:

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

What's wrong? The problem is that this expression does not match our grammar. The expression groups as if it were written like `(cout_ << 1) << 2`. It will not match the `Output` grammar, which expects the left operand to be a terminal, not another left-shift operation. We need to fix the grammar.

We notice that in order to verify an expression as input or output, we'll need to recurse down to the bottom-left-most leaf and check that it is a `std::istream` or `std::ostream`. When we get to the terminal, we must stop recursing. We can express this in our grammar using `proto::or_<>`. Here are the correct `Input` and `Output` grammars:

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

This may look a little odd at first. We seem to be defining the `Input` and `Output` types in terms of themselves. This is perfectly OK, actually. At the point in the grammar that the `Input` and `Output` types are being used, they are incomplete, but by the time we actually evaluate the grammar with `proto::matches<>`, the types will be complete. These are recursive grammars, and rightly so because they must match a recursive data structure!

Matching an expression such as `cout_ << 1 << 2` against the `Output` grammar procedes as follows:

1. The first alternate of the `proto::or_<>` is tried first. It will fail, because the expression `cout_ << 1 << 2` does not match the grammar `proto::shift_left< proto::terminal< std::ostream & >, proto::_ >`.
2. Then the second alternate is tried next. We match the expression against `proto::shift_left< Output, proto::_ >`. The expression is a left-shift, so we next try to match the operands.
3. The right operand `2` matches `proto::_` trivially.
4. To see if the left operand `cout_ << 1` matches `Output`, we must recursively evaluate the `Output` grammar. This time we succeed, because `cout_ << 1` will match the first alternate of the `proto::or_<>`.

We're done -- the grammar matches successfully.

##### Fuzzy and Exact Matches of Terminals

The terminals in an expression tree could be const or non-const references, or they might not be references at all. When writing grammars, you usually don't have to worry about it because `proto::matches<>` gives you a little wiggle room when matching terminals. A grammar such as `proto::terminal<int>` will match a terminal of type `int`, `int &`, or `int const &`.

You can explicitly specify that you want to match a reference type. If you do, the type must match exactly. For instance, a grammar such as `proto::terminal<int &>` will only match an `int &`. It will not match an `int` or an `int const &`.

The table below shows how Proto matches terminals. The simple rule is: if you want to match only reference types, you must specify the reference in your grammar. Otherwise, leave it off and Proto will ignore const and references.

Table 20.7. proto::matches<> and Reference / CV-Qualification of Terminals

Terminal | Grammar | Matches?
--- | --- | ---
T | T | yes
T & | T | yes
T const & | T | yes
T | T & | no
T & | T & | yes
T const & | T & | no
T | T const & | no
T & | T const & | no
T const & | T const & | yes

This begs the question: What if you want to match an `int`, but not an `int &` or an `int const &`? For forcing exact matches, Proto provides the `proto::exact<>` template. For instance, `proto::terminal< proto::exact<int> >` would only match an `int` held by value.

Proto gives you extra wiggle room when matching array types. Array types match themselves or the pointer types they decay to. This is especially useful with character arrays. The type returned by `proto::as_expr("hello")` is `proto::terminal<char const[6]>::type`. That's a terminal containing a 6-element character array. Naturally, you can match this terminal with the grammar `proto::terminal<char const[6]>`, but the grammar `proto::terminal<char const *>` will match it as well, as the following code fragment illustrates.

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

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

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

What if we only wanted `CharString` to match terminals of exactly the type `char const *`? You can use `proto::exact<>` here to turn off the fuzzy matching of terminals, as follows:

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

Now, `CharString` does not match array types, only character string pointers.

The inverse problem is a little trickier: what if you wanted to match all character arrays, but not character pointers? As mentioned above, the expression `as_expr("hello")` has the type `proto::terminal< char const[ 6 ] >::type`. If you wanted to match character arrays of arbitrary size, you could use `proto::N`, which is an array-size wildcard. The following grammar would match any string literal: `proto::terminal< char const[ proto::N ] >`.

Sometimes you need even more wiggle room when matching terminals. For example, maybe you're building a calculator EDSL and you want to allow any terminals that are convertible to `double`. For that, Proto provides the `proto::convertible_to<>` template. You can use it as: `proto::terminal< proto::convertible_to< double > >`.

There is one more way you can perform a fuzzy match on terminals. Consider the problem of trying to match a `std::complex<>` terminal. You can easily match a `std::complex<float>` or a `std::complex<double>`, but how would you match any instantiation of `std::complex<>`? You can use `proto::_` here to solve this problem. Here is the grammar to match any `std::complex<>` instantiation:

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

When given a grammar like this, Proto will deconstruct the grammar and the terminal it is being matched against and see if it can match all the constituents.

##### `if_<>`, `and_<>`, and `not_<>`

We've already seen how to use expression generators like `proto::terminal<>` and `proto::shift_right<>` as grammars. We've also seen `proto::or_<>`, which we can use to express a set of alternate grammars. There are a few others of interest; in particular, `proto::if_<>`, `proto::and_<>` and `proto::not_<>`.

The `proto::not_<>` template is the simplest. It takes a grammar as a template parameter and logically negates it; `not_<Grammar>` will match any expression that `Grammar` does not match.

The `proto::if_<>` template is used together with a Proto transform that is evaluated against expression types to find matches. (Proto transforms will be described later.)

The `proto::and_<>` template is like `proto::or_<>`, except that each argument of the `proto::and_<>` must match in order for the `proto::and_<>` to match. As an example, consider the definition of `CharString` above that uses `proto::exact<>`. It could have been written without `proto::exact<>` as follows:

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

This says that a `CharString` must be a terminal, and its value type must be the same as `char const *`. Notice the template argument of `proto::if_<>`: `boost::is_same< proto::_value, char const * >()`. This is Proto transform that compares the value type of a terminal to `char const *`.

The `proto::if_<>` template has a couple of variants. In addition to `if_<Condition>` you can also say `if_<Condition, ThenGrammar>` and `if_<Condition, ThenGrammar, ElseGrammar>`. These let you select one sub-grammar or another based on the `Condition`.

##### 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 EDSL. 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.

##### Matching Vararg Expressions

Not all of C++'s overloadable operators are unary or binary. There is the oddball `operator()` -- the function call operator -- which can have any number of arguments. Likewise, with Proto you may define your own "operators" that could also take more that two arguments. As a result, there may be nodes in your Proto expression tree that have an arbitrary number of children (up to ``BOOST_PROTO_MAX_ARITY``, which is configurable). How do you write a grammar to match such a node?

For such cases, Proto provides the `proto::vararg<>` class template. Its template argument is a grammar, and the `proto::vararg<>` will match the grammar zero or more times. Consider a Proto lazy function called `fun()` that can take zero or more characters as arguments, as follows:

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

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

Below is the grammar that matches all the allowable invocations of `fun()`:

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

The `FunCall` grammar uses `proto::vararg<>` to match zero or more character literals as arguments of the `fun()` function.

As another example, can you guess what the following grammar matches?

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

Here's a hint: the first template parameter to `proto::nary_expr<>` represents the node type, and any additional template parameters represent child nodes. The answer is that this is a degenerate grammar that matches every possible expression tree, from root to leaves.

##### Defining EDSL Grammars

In this section we'll see how to use Proto to define a grammar for your EDSL and use it to validate expression templates, giving short, readable compile-time errors for invalid expressions.

| Tip
You might think that this is a backwards way of doing things. “If Proto let me select which operators to overload, my users wouldn't be able to create invalid expressions in the first place, and I wouldn't need a grammar at all!” That may be true, but there are reasons for preferring to do things this way. First, it lets you develop your EDSL rapidly -- all the operators are there for you already! -- and worry about invalid syntax later. Second, it might be the case that some operators are only allowed in certain contexts within your EDSL. This is easy to express with a grammar, and hard to do with straight operator overloading. Third, using an EDSL grammar to flag invalid expressions can often yield better errors than manually selecting the overloaded operators. Fourth, the grammar can be used for more than just validation. You can use your grammar to define tree transformations that convert expression templates into other more useful objects. If none of the above convinces you, you actually can use Proto to control which operators are overloaded within your domain. And to do it, you need to define a grammar!

In a previous section, we used Proto to define an EDSL for a lazily evaluated calculator that allowed any combination of placeholders, floating-point literals, addition, subtraction, multiplication, division and grouping. If we were to write the grammar for this EDSL in EBNF, it might look like this:

    group       ::= '(' expression ')'
    factor      ::= double | '_1' | '_2' | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

This captures the syntax, associativity and precedence rules of a calculator. Writing the grammar for our calculator EDSL using Proto is even simpler. Since we are using C++ as the host language, we are bound to the associativity and precedence rules for the C++ operators. Our grammar can assume them. Also, in C++ grouping is already handled for us with the use of parenthesis, so we don't have to code that into our grammar.

Let's begin our grammar for forward-declaring it:

    struct CalculatorGrammar;

It's an incomplete type at this point, but we'll still be able to use it to define the rules of our grammar. Let's define grammar rules for the terminals:

    struct Double
      : proto::terminal< proto::convertible_to< double > >
    {};

    struct Placeholder1
      : proto::terminal< placeholder<0> >
    {};

    struct Placeholder2
      : proto::terminal< placeholder<1> >
    {};

    struct Terminal
      : proto::or_< Double, Placeholder1, Placeholder2 >
    {};

Now let's define the rules for addition, subtraction, multiplication and division. Here, we can ignore issues of associativity and precedence -- the C++ compiler will enforce that for us. We only must enforce that the arguments to the operators must themselves conform to the `CalculatorGrammar` that we forward-declared above.

    struct Plus
      : proto::plus< CalculatorGrammar, CalculatorGrammar >
    {};

    struct Minus
      : proto::minus< CalculatorGrammar, CalculatorGrammar >
    {};

    struct Multiplies
      : proto::multiplies< CalculatorGrammar, CalculatorGrammar >
    {};

    struct Divides
      : proto::divides< CalculatorGrammar, CalculatorGrammar >
    {};

Now that we've defined all the parts of the grammar, we can define `CalculatorGrammar`:

    struct CalculatorGrammar
      : proto::or_<
            Terminal
          , Plus
          , Minus
          , Multiplies
          , Divides
        >
    {};

That's it! Now we can use `CalculatorGrammar` to enforce that an expression template conforms to our grammar. We can use `proto::matches<>` and `BOOST_MPL_ASSERT()` to issue readable compile-time errors for invalid expressions, as below:

    template< typename Expr >
    void evaluate( Expr const & expr )
    {
        BOOST_MPL_ASSERT(( proto::matches< Expr, CalculatorGrammar > ));
        // ...
    }

### Back Ends: Making Expression Templates Do Useful Work

Now that you've written the front end for your EDSL compiler, and you've learned a bit about the intermediate form it produces, it's time to think about what to do with the intermediate form. This is where you put your domain-specific algorithms and optimizations. Proto gives you two ways to evaluate and manipulate expression templates: contexts and transforms.

- A context is like a function object that you pass along with an expression to the `proto::eval()` function. It associates behaviors with node types. `proto::eval()` walks the expression and invokes your context at each node.
- A transform is a way to associate behaviors, not with node types in an expression, but with rules in a Proto grammar. In this way, they are like semantic actions in other compiler-construction toolkits.

Two ways to evaluate expressions! How to choose? Since contexts are largely procedural, they are a bit simpler to understand and debug so they are a good place to start. But although transforms are more advanced, they are also more powerful; since they are associated with rules in your grammar, you can select the proper transform based on the entire structure of a sub-expression rather than simply on the type of its top-most node.

Also, transforms have a concise and declarative syntax that can be confusing at first, but highly expressive and fungible once you become accustomed to it. And -- this is admittedly very subjective -- the author finds programming with Proto transforms to be an inordinate amount of fun! Your mileage may vary.

#### Expression Evaluation: Imparting Behaviors with a Context

Once you have constructed a Proto expression tree, either by using Proto's operator overloads or with `proto::make_expr()` and friends, you probably want to actually do something with it. The simplest option is to use `proto::eval()`, a generic expression evaluator. To use `proto::eval()`, you'll need to define a context that tells `proto::eval()` how each node should be evaluated. This section goes through the nuts and bolts of using `proto::eval()`, defining evaluation contexts, and using the contexts that Proto provides.

| Note
`proto::eval()` is a less powerful but easier-to-use evaluation technique than Proto transforms, which are covered later. Although very powerful, transforms have a steep learning curve and can be more difficult to debug. `proto::eval()` is a rather weak tree traversal algorithm. Dan Marsden has been working on a more general and powerful tree traversal library. When it is ready, I anticipate that it will eliminate the need for `proto::eval()`.

##### Evaluating an Expression with `proto::eval()`

> Synopsis:

    namespace proto
    {
        namespace result_of
        {
            // A metafunction for calculating the return
            // type of proto::eval() given certain Expr
            // and Context types.
            template<typename Expr, typename Context>
            struct eval
            {
                typedef
                    typename Context::template eval<Expr>::result_type
                type;
            };
        }

        namespace functional
        {
            // A callable function object type for evaluating
            // a Proto expression with a certain context.
            struct eval : callable
            {
                template<typename Sig>
                struct result;

                template<typename Expr, typename Context>
                typename proto::result_of::eval<Expr, Context>::type
                operator ()(Expr &expr, Context &context) const;

                template<typename Expr, typename Context>
                typename proto::result_of::eval<Expr, Context>::type
                operator ()(Expr &expr, Context const &context) const;
            };
        }

        template<typename Expr, typename Context>
        typename proto::result_of::eval<Expr, Context>::type
        eval(Expr &expr, Context &context);

        template<typename Expr, typename Context>
        typename proto::result_of::eval<Expr, Context>::type
        eval(Expr &expr, Context const &context);
    }

Given an expression and an evaluation context, using `proto::eval()` is quite simple. Simply pass the expression and the context to `proto::eval()` and it does the rest and returns the result. You can use the `eval<>` metafunction in the `proto::result_of` namespace to compute the return type of `proto::eval()`. The following demonstrates a use of `proto::eval()`:

    template<typename Expr>
    typename proto::result_of::eval<Expr const, MyContext>::type
    MyEvaluate(Expr const &expr)
    {
        // Some user-defined context type
        MyContext ctx;

        // Evaluate an expression with the context
        return proto::eval(expr, ctx);
    }

What `proto::eval()` does is also very simple. It defers most of the work to the context itself. Here essentially is the implementation of `proto::eval()`:

    // eval() dispatches to a nested "eval<>" function
    // object within the Context:
    template<typename Expr, typename Context>
    typename Context::template eval<Expr>::result_type
    eval(Expr &expr, Context &ctx)
    {
        typename Context::template eval<Expr> eval_fun;
        return eval_fun(expr, ctx);
    }

Really, `proto::eval()` is nothing more than a thin wrapper that dispatches to the appropriate handler within the context class. In the next section, we'll see how to implement a context class from scratch.

##### Defining an Evaluation Context

As we saw in the previous section, there is really not much to the `proto::eval()` function. Rather, all the interesting expression evaluation goes on within a context class. This section shows how to implement one from scratch.

All context classes have roughly the following form:

    // A prototypical user-defined context.
    struct MyContext
    {
        // A nested eval<> class template
        template<
            typename Expr
          , typename Tag = typename proto::tag_of<Expr>::type
        >
        struct eval;

        // Handle terminal nodes here...
        template<typename Expr>
        struct eval<Expr, proto::tag::terminal>
        {
            // Must have a nested result_type typedef.
            typedef ... result_type;

            // Must have a function call operator that takes
            // an expression and the context.
            result_type operator()(Expr &expr, MyContext &ctx) const
            {
                return ...;
            }
        };

        // ... other specializations of struct eval<> ...
    };

Context classes are nothing more than a collection of specializations of a nested `eval<>` class template. Each specialization handles a different expression type.

In the Hello Calculator section, we saw an example of a user-defined context class for evaluating calculator expressions. That context class was implemented with the help of Proto's `proto::callable_context<>`. If we were to implement it from scratch, it would look something like this:

    // The calculator_context from the "Hello Calculator" section,
    // implemented from scratch.
    struct calculator_context
    {
        // The values with which we'll replace the placeholders
        std::vector<double> args;

        template<
            typename Expr
            // defaulted template parameters, so we can
            // specialize on the expressions that need
            // special handling.
          , typename Tag = typename proto::tag_of<Expr>::type
          , typename Arg0 = typename proto::child_c<Expr, 0>::type
        >
        struct eval;

        // Handle placeholder terminals here...
        template<typename Expr, int I>
        struct eval<Expr, proto::tag::terminal, placeholder<I> >
        {
            typedef double result_type;

            result_type operator()(Expr &, MyContext &ctx) const
            {
                return ctx.args[I];
            }
        };

        // Handle other terminals here...
        template<typename Expr, typename Arg0>
        struct eval<Expr, proto::tag::terminal, Arg0>
        {
            typedef double result_type;

            result_type operator()(Expr &expr, MyContext &) const
            {
                return proto::child(expr);
            }
        };

        // Handle addition here...
        template<typename Expr, typename Arg0>
        struct eval<Expr, proto::tag::plus, Arg0>
        {
            typedef double result_type;

            result_type operator()(Expr &expr, MyContext &ctx) const
            {
                return proto::eval(proto::left(expr), ctx)
                     + proto::eval(proto::right(expr), ctx);
            }
        };

        // ... other eval<> specializations for other node types ...
    };

Now we can use `proto::eval()` with the context class above to evaluate calculator expressions as follows:

    // Evaluate an expression with a calculator_context
    calculator_context ctx;
    ctx.args.push_back(5);
    ctx.args.push_back(6);
    double d = proto::eval(_1 + _2, ctx);
    assert(11 == d);

Defining a context from scratch this way is tedious and verbose, but it gives you complete control over how the expression is evaluated. The context class in the Hello Calculator example was much simpler. In the next section we'll see the helper class Proto provides to ease the job of implementing context classes.

##### Proto's Built-In Contexts

Proto provides some ready-made context classes that you can use as-is, or that you can use to help while implementing your own contexts. They are:

`default_context`

  An evaluation context that assigns the usual C++ meanings to all the operators. For example, addition nodes are handled by evaluating the left and right children and then adding the results. The `proto::default_context` uses Boost.Typeof to deduce the types of the expressions it evaluates.

`null_context`

  A simple context that recursively evaluates children but does not combine the results in any way and returns void.

`callable_context<>`

  A helper that simplifies the job of writing context classes. Rather than writing template specializations, with `proto::callable_context<>` you write a function object with an overloaded function call operator. Any expressions not handled by an overload are automatically dispatched to a default evaluation context that you can specify.

###### `default_context`

The `proto::default_context` is an evaluation context that assigns the usual C++ meanings to all the operators. For example, addition nodes are handled by evaluating the left and right children and then adding the results. The `proto::default_context` uses Boost.Typeof to deduce the types of the expressions it evaluates.

For example, consider the following "Hello World" example:

    #include <iostream>
    #include <boost/proto/proto.hpp>
    #include <boost/proto/context.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 )
    {
        // Evaluate the expression with default_context,
        // to give the operators their C++ meanings:
        proto::default_context ctx;
        proto::eval(expr, ctx);
    }

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

This program outputs the following:

    hello, world

`proto::default_context` is trivially defined in terms of a `default_eval<>` template, as follows:

    // Definition of default_context
    struct default_context
    {
        template<typename Expr>
        struct eval
          : default_eval<
                Expr
              , default_context const
              , typename tag_of<Expr>::type
            >
        {};
    };

There are a bunch of `default_eval<>` specializations, each of which handles a different C++ operator. Here, for instance, is the specialization for binary addition:

    // A default expression evaluator for binary addition
    template<typename Expr, typename Context>
    struct default_eval<Expr, Context, proto::tag::plus>
    {
    private:
        static Expr    & s_expr;
        static Context & s_ctx;

    public:
        typedef
            decltype(
                proto::eval(proto::child_c<0>(s_expr), s_ctx)
              + proto::eval(proto::child_c<1>(s_expr), s_ctx)
            )
        result_type;

        result_type operator ()(Expr &expr, Context &ctx) const
        {
            return proto::eval(proto::child_c<0>(expr), ctx)
                 + proto::eval(proto::child_c<1>(expr), ctx);
        }
    };

The above code uses `decltype` to calculate the return type of the function call operator. `decltype` is a new keyword in the next version of C++ that gets the type of any expression. Most compilers do not yet support `decltype` directly, so `default_eval<>` uses the Boost.Typeof library to emulate it. On some compilers, that may mean that `default_context` either doesn't work or that it requires you to register your types with the Boost.Typeof library. Check the documentation for Boost.Typeof to see.

###### `null_context`

The `proto::null_context<>` is a simple context that recursively evaluates children but does not combine the results in any way and returns void. It is useful in conjunction with `callable_context<>`, or when defining your own contexts which mutate an expression tree in-place rather than accumulate a result, as we'll see below.

`proto::null_context<>` is trivially implemented in terms of `null_eval<>` as follows:

    // Definition of null_context
    struct null_context
    {
        template<typename Expr>
        struct eval
          : null_eval<Expr, null_context const, Expr::proto_arity::value>
        {};
    };

And `null_eval<>` is also trivially implemented. Here, for instance is a binary `null_eval<>`:

    // Binary null_eval<>
    template<typename Expr, typename Context>
    struct null_eval<Expr, Context, 2>
    {
        typedef void result_type;

        void operator()(Expr &expr, Context &ctx) const
        {
            proto::eval(proto::child_c<0>(expr), ctx);
            proto::eval(proto::child_c<1>(expr), ctx);
        }
    };

When would such classes be useful? Imagine you have an expression tree with integer terminals, and you would like to increment each integer in-place. You might define an evaluation context as follows:

    struct increment_ints
    {
        // By default, just evaluate all children by delegating
        // to the null_eval<>
        template<typename Expr, typename Arg = proto::result_of::child<Expr>::type>
        struct eval
          : null_eval<Expr, increment_ints const>
        {};

        // Increment integer terminals
        template<typename Expr>
        struct eval<Expr, int>
        {
            typedef void result_type;

            void operator()(Expr &expr, increment_ints const &) const
            {
                ++proto::child(expr);
            }
        };
    };

In the next section on `proto::callable_context<>`, we'll see an even simpler way to achieve the same thing.

###### `callable_context<>`

The `proto::callable_context<>` is a helper that simplifies the job of writing context classes. Rather than writing template specializations, with `proto::callable_context<>` you write a function object with an overloaded function call operator. Any expressions not handled by an overload are automatically dispatched to a default evaluation context that you can specify.

Rather than an evaluation context in its own right, `proto::callable_context<>` is more properly thought of as a context adaptor. To use it, you must define your own context that inherits from `proto::callable_context<>`.

In the `null_context` section, we saw how to implement an evaluation context that increments all the integers within an expression tree. Here is how to do the same thing with the `proto::callable_context<>`:

    // An evaluation context that increments all
    // integer terminals in-place.
    struct increment_ints
      : callable_context<
            increment_ints const // derived context
          , null_context const  // fall-back context
        >
    {
        typedef void result_type;

        // Handle int terminals here:
        void operator()(proto::tag::terminal, int &i) const
        {
            ++i;
        }
    };

With such a context, we can do the following:

    literal<int> i = 0, j = 10;
    proto::eval( i - j * 3.14, increment_ints() );

    std::cout << "i = " << i.get() << std::endl;
    std::cout << "j = " << j.get() << std::endl;

This program outputs the following, which shows that the integers `i` and `j` have been incremented by `1`:

    i = 1
    j = 11

In the `increment_ints` context, we didn't have to define any nested `eval<>` templates. That's because `proto::callable_context<>` implements them for us. `proto::callable_context<>` takes two template parameters: the derived context and a fall-back context. For each node in the expression tree being evaluated, `proto::callable_context<>` checks to see if there is an overloaded `operator()` in the derived context that accepts it. Given some expression `expr` of type `Expr`, and a context `ctx`, it attempts to call:

    ctx(
        typename Expr::proto_tag()
      , proto::child_c<0>(expr)
      , proto::child_c<1>(expr)
        ...
    );

Using function overloading and metaprogramming tricks, `proto::callable_context<>` can detect at compile-time whether such a function exists or not. If so, that function is called. If not, the current expression is passed to the fall-back evaluation context to be processed.

We saw another example of the `proto::callable_context<>` when we looked at the simple calculator expression evaluator. There, we wanted to customize the evaluation of placeholder terminals, and delegate the handling of all other nodes to the `proto::default_context`. We did that as follows:

    // An evaluation context for calculator expressions that
    // explicitly handles placeholder terminals, but defers the
    // processing of all other nodes to the default_context.
    struct calculator_context
      : proto::callable_context< calculator_context const >
    {
        std::vector<double> args;

        // Define the result type of the calculator.
        typedef double result_type;

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

In this case, we didn't specify a fall-back context. In that case, `proto::callable_context<>` uses the `proto::default_context`. With the above `calculator_context` and a couple of appropriately defined placeholder terminals, we can evaluate calculator expressions, as demonstrated below:

    template<int I>
    struct placeholder
    {};

    terminal<placeholder<0> >::type const _1 = {{}};
    terminal<placeholder<1> >::type const _2 = {{}};
    // ...

    calculator_context ctx;
    ctx.args.push_back(4);
    ctx.args.push_back(5);

    double j = proto::eval( (_2 - _1) / _2 * 100, ctx );
    std::cout << "j = " << j << std::endl;

The above code displays the following:

    j = 20

#### Expression Transformation: Semantic Actions

If you have ever built a parser with the help of a tool like Antlr, yacc or Boost.Spirit, you might be familiar with semantic actions. In addition to allowing you to define the grammar of the language recognized by the parser, these tools let you embed code within your grammar that executes when parts of the grammar participate in a parse. Proto has the equivalent of semantic actions. They are called transforms. This section describes how to embed transforms within your Proto grammars, turning your grammars into function objects that can manipulate or evaluate expressions in powerful ways.

Proto transforms are an advanced topic. We'll take it slow, using examples to illustrate the key concepts, starting simple.

##### “Activating” Your Grammars

The Proto grammars we've seen so far are static. You can check at compile-time to see if an expression type matches a grammar, but that's it. Things get more interesting when you give them runtime behaviors. A grammar with embedded transforms is more than just a static grammar. It is a function object that accepts expressions that match the grammar and does something with them.

Below is a very simple grammar. It matches terminal expressions.

    // A simple Proto grammar that matches all terminals
    proto::terminal< _ >

Here is the same grammar with a transform that extracts the value from the terminal:

    // A simple Proto grammar that matches all terminals
    // *and* a function object that extracts the value from
    // the terminal
    proto::when<
        proto::terminal< _ >
      , proto::_value          // <-- Look, a transform!
    >

You can read this as follows: when you match a terminal expression, extract the value. The type `proto::_value` is a so-called transform. Later we'll see what makes it a transform, but for now just think of it as a kind of function object. Note the use of `proto::when<>`: the first template parameter is the grammar to match and the second is the transform to execute. The result is both a grammar that matches terminal expressions and a function object that accepts terminal expressions and extracts their values.

As with ordinary grammars, we can define an empty struct that inherits from a grammar+transform to give us an easy way to refer back to the thing we're defining, as follows:

    // A grammar and a function object, as before
    struct Value
      : proto::when<
            proto::terminal< _ >
          , proto::_value
        >
    {};

    // "Value" is a grammar that matches terminal expressions
    BOOST_MPL_ASSERT(( proto::matches< proto::terminal<int>::type, Value > ));

    // "Value" also defines a function object that accepts terminals
    // and extracts their value.
    proto::terminal<int>::type answer = {42};
    Value get_value;
    int i = get_value( answer );

As already mentioned, `Value` is a grammar that matches terminal expressions and a function object that operates on terminal expressions. It would be an error to pass a non-terminal expression to the `Value` function object. This is a general property of grammars with transforms; when using them as function objects, expressions passed to them must match the grammar.

Proto grammars are valid TR1-style function objects. That means you can use `boost::result_of<>` to ask a grammar what its return type will be, given a particular expression type. For instance, we can access the `Value` grammar's return type as follows:

    // We can use boost::result_of<> to get the return type
    // of a Proto grammar.
    typedef
        typename boost::result_of<Value(proto::terminal<int>::type)>::type
    result_type;

    // Check that we got the type we expected
    BOOST_MPL_ASSERT(( boost::is_same<result_type, int> ));

| Note
A grammar with embedded transforms is both a grammar and a function object. Calling these things "grammars with transforms" would get tedious. We could call them something like "active grammars", but as we'll see every grammar that you can define with Proto is "active"; that is, every grammar has some behavior when used as a function object. So we'll continue calling these things plain "grammars". The term "transform" is reserved for the thing that is used as the second parameter to the `proto::when<>` template.

##### Handling Alternation and Recursion

Most grammars are a little more complicated than the one in the preceding section. For the sake of illustration, let's define a rather nonsensical grammar that matches any expression and recurses to the leftmost terminal and returns its value. It will demonstrate how two key concepts of Proto grammars -- alternation and recursion -- interact with transforms. The grammar is described below.

    // A grammar that matches any expression, and a function object
    // that returns the value of the leftmost terminal.
    struct LeftmostLeaf
      : proto::or_<
            // If the expression is a terminal, return its value
            proto::when<
                proto::terminal< _ >
              , proto::_value
            >
            // Otherwise, it is a non-terminal. Return the result
            // of invoking LeftmostLeaf on the 0th (leftmost) child.
          , proto::when<
                _
              , LeftmostLeaf( proto::_child0 )
            >
        >
    {};

    // A Proto terminal wrapping std::cout
    proto::terminal< std::ostream & >::type cout_ = { std::cout };

    // Create an expression and use LeftmostLeaf to extract the
    // value of the leftmost terminal, which will be std::cout.
    std::ostream & sout = LeftmostLeaf()( cout_ << "the answer: " << 42 << '\n' );

We've seen `proto::or_<>` before. Here it is serving two roles. First, it is a grammar that matches any of its alternate sub-grammars; in this case, either a terminal or a non-terminal. Second, it is also a function object that accepts an expression, finds the alternate sub-grammar that matches the expression, and applies its transform. And since `LeftmostLeaf` inherits from `proto::or_<>`, `LeftmostLeaf` is also both a grammar and a function object.

| Note
The second alternate uses `proto::_` as its grammar. Recall that `proto::_` is the wildcard grammar that matches any expression. Since alternates in `proto::or_<>` are tried in order, and since the first alternate handles all terminals, the second alternate handles all (and only) non-terminals. Often enough, `proto::when< _, `some-transform` >` is the last alternate in a grammar, so for improved readability, you could use the equivalent `proto::otherwise< `some-transform` >`.

The next section describes this grammar further.

##### Callable Transforms

In the grammar defined in the preceding section, the transform associated with non-terminals is a little strange-looking:

    proto::when<
        _
      , LeftmostLeaf( proto::_child0 )   // <-- a "callable" transform
    >

It has the effect of accepting non-terminal expressions, taking the 0th (leftmost) child and recursively invoking the `LeftmostLeaf` function on it. But `LeftmostLeaf( proto::_child0 )` is actually a function type. Literally, it is the type of a function that accepts an object of type `proto::_child0` and returns an object of type `LeftmostLeaf`. So how do we make sense of this transform? Clearly, there is no function that actually has this signature, nor would such a function be useful. The key is in understanding how `proto::when<>` interprets its second template parameter.

When the second template parameter to `proto::when<>` is a function type, `proto::when<>` interprets the function type as a transform. In this case, `LeftmostLeaf` is treated as the type of a function object to invoke, and `proto::_child0` is treated as a transform. First, `proto::_child0` is applied to the current expression (the non-terminal that matched this alternate sub-grammar), and the result (the 0th child) is passed as an argument to `LeftmostLeaf`.

| Note
Transforms are a Domain-Specific Language `LeftmostLeaf( proto::_child0 )` looks like an invocation of the `LeftmostLeaf` function object, but it's not, but then it actually is! Why this confusing subterfuge? Function types give us a natural and concise syntax for composing more complicated transforms from simpler ones. The fact that the syntax is suggestive of a function invocation is on purpose. It is an embedded domain-specific language for defining expression transformations. If the subterfuge worked, it may have fooled you into thinking the transform is doing exactly what it actually does! And that's the point.

The type `LeftmostLeaf( proto::_child0 )` is an example of a callable transform. It is a function type that represents a function object to call and its arguments. The types `proto::_child0` and `proto::_value` are primitive transforms. They are plain structs, not unlike function objects, from which callable transforms can be composed. There is one other type of transform, object transforms, that we'll encounter next.

##### Object Transforms

The very first transform we looked at simply extracted the value of terminals. Let's do the same thing, but this time we'll promote all ints to longs first. (Please forgive the contrived-ness of the examples so far; they get more interesting later.) Here's the grammar:

    // A simple Proto grammar that matches all terminals,
    // and a function object that extracts the value from
    // the terminal, promoting ints to longs:
    struct ValueWithPomote
      : proto::or_<
            proto::when<
                proto::terminal< int >
              , long(proto::_value)     // <-- an "object" transform
            >
          , proto::when<
                proto::terminal< _ >
              , proto::_value
            >
        >
    {};

You can read the above grammar as follows: when you match an int terminal, extract the value from the terminal and use it to initialize a long; otherwise, when you match another kind of terminal, just extract the value. The type `long(proto::_value)` is a so-called object transform. It looks like the creation of a temporary long, but it's really a function type. Just as a callable transform is a function type that represents a function to call and its arguments, an object transforms is a function type that represents an object to construct and the arguments to its constructor.

| Note
Object Transforms vs. Callable Transforms When using function types as Proto transforms, they can either represent an object to construct or a function to call. It is similar to "normal" C++ where the syntax `foo("arg")` can either be interpreted as an object to construct or a function to call, depending on whether `foo` is a type or a function. But consider two of the transforms we've seen so far:
    LeftmostLeaf(proto::_child0)  // <-- a callable transform
    long(proto::_value)           // <-- an object transform
Proto can't know in general which is which, so it uses a trait, `proto::is_callable<>`, to differentiate. `is_callable< long >::value` is false so `long(proto::_value)` is an object to construct, but `is_callable< LeftmostLeaf >::value` is true so `LeftmostLeaf(proto::_child0)` is a function to call. Later on, we'll see how Proto recognizes a type as "callable".

##### Example: Calculator Arity

Now that we have the basics of Proto transforms down, let's consider a slightly more realistic example. We can use transforms to improve the type-safety of the calculator EDSL. If you recall, it lets you write infix arithmetic expressions involving argument placeholders like `_1` and `_2` and pass them to STL algorithms as function objects, as follows:

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

This works because we gave calculator expressions an `operator()` that evaluates the expression, replacing the placeholders with the arguments to `operator()`. The overloaded `calculator<>::operator()` looked like this:

    // Overload operator() to invoke proto::eval() with
    // our calculator_context.
    template<typename Expr>
    double
    calculator<Expr>::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);
    }

Although this works, it's not ideal because it doesn't warn users if they supply too many or too few arguments to a calculator expression. Consider the following mistakes:

    (_1 * _1)(4, 2);  // Oops, too many arguments!
    (_2 * _2)(42);    // Oops, too few arguments!

The expression `_1 * _1` defines a unary calculator expression; it takes one argument and squares it. If we pass more than one argument, the extra arguments will be silently ignored, which might be surprising to users. The next expression, `_2 * _2` defines a binary calculator expression; it takes two arguments, ignores the first and squares the second. If we only pass one argument, the code silently fills in `0.0` for the second argument, which is also probably not what users expect. What can be done?

We can say that the arity of a calculator expression is the number of arguments it expects, and it is equal to the largest placeholder in the expression. So, the arity of `_1 * _1` is one, and the arity of `_2 * _2` is two. We can increase the type-safety of our calculator EDSL by making sure the arity of an expression equals the actual number of arguments supplied. Computing the arity of an expression is simple with the help of Proto transforms.

It's straightforward to describe in words how the arity of an expression should be calculated. Consider that calculator expressions can be made of `_1`, `_2`, literals, unary expressions and binary expressions. The following table shows the arities for each of these 5 constituents.

Table 20.8. Calculator Sub-Expression Arities

Sub-Expression | Arity
--- | ---
Placeholder 1 | `1`
Placeholder 2 | `2`
Literal | `0`
Unary Expression | arity of the operand
Binary Expression | max arity of the two operands

Using this information, we can write the grammar for calculator expressions and attach transforms for computing the arity of each constituent. The code below computes the expression arity as a compile-time integer, using integral wrappers and metafunctions from the Boost MPL Library. The grammar is described below.

    struct CalcArity
      : proto::or_<
            proto::when< proto::terminal< placeholder<0> >,
                mpl::int_<1>()
            >
          , proto::when< proto::terminal< placeholder<1> >,
                mpl::int_<2>()
            >
          , proto::when< proto::terminal<_>,
                mpl::int_<0>()
            >
          , proto::when< proto::unary_expr<_, CalcArity>,
                CalcArity(proto::_child)
            >
          , proto::when< proto::binary_expr<_, CalcArity, CalcArity>,
                mpl::max<CalcArity(proto::_left),
                         CalcArity(proto::_right)>()
            >
        >
    {};

When we find a placeholder terminal or a literal, we use an object transform such as `mpl::int_<1>()` to create a (default-constructed) compile-time integer representing the arity of that terminal.

For unary expressions, we use `CalcArity(proto::_child)` which is a callable transform that computes the arity of the expression's child.

The transform for binary expressions has a few new tricks. Let's look more closely:

    // Compute the left and right arities and
    // take the larger of the two.
    mpl::max<CalcArity(proto::_left),
             CalcArity(proto::_right)>()

This is an object transform; it default-constructs ... what exactly? The `mpl::max<>` template is an MPL metafunction that accepts two compile-time integers. It has a nested `::type` typedef (not shown) that is the maximum of the two. But here, we appear to be passing it two things that are not compile-time integers; they're Proto callable transforms. Proto is smart enough to recognize that fact. It first evaluates the two nested callable transforms, computing the arities of the left and right child expressions. Then it puts the resulting integers into `mpl::max<>` and evaluates the metafunction by asking for the nested `::type`. That is the type of the object that gets default-constructed and returned.

More generally, when evaluating object transforms, Proto looks at the object type and checks whether it is a template specialization, like `mpl::max<>`. If it is, Proto looks for nested transforms that it can evaluate. After any nested transforms have been evaluated and substituted back into the template, the new template specialization is the result type, unless that type has a nested `::type`, in which case that becomes the result.

Now that we can calculate the arity of a calculator expression, let's redefine the `calculator<>` expression wrapper we wrote in the Getting Started guide to use the `CalcArity` grammar and some macros from Boost.MPL to issue compile-time errors when users specify too many or too few arguments.

    // The calculator expression wrapper, as defined in the Hello
    // Calculator example in the Getting Started guide. It behaves
    // just like the expression it wraps, but with extra operator()
    // member functions that evaluate the expression.
    //   NEW: Use the CalcArity grammar to ensure that the correct
    //   number of arguments are supplied.
    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;

        // Use CalcArity to compute the arity of Expr:
        static int const arity = boost::result_of<CalcArity(Expr)>::type::value;

        double operator()() const
        {
            BOOST_MPL_ASSERT_RELATION(0, ==, arity);
            calculator_context ctx;
            return proto::eval(*this, ctx);
        }

        double operator()(double a1) const
        {
            BOOST_MPL_ASSERT_RELATION(1, ==, arity);
            calculator_context ctx;
            ctx.args.push_back(a1);
            return proto::eval(*this, ctx);
        }

        double operator()(double a1, double a2) const
        {
            BOOST_MPL_ASSERT_RELATION(2, ==, arity);
            calculator_context ctx;
            ctx.args.push_back(a1);
            ctx.args.push_back(a2);
            return proto::eval(*this, ctx);
        }
    };

Note the use of `boost::result_of<>` to access the return type of the `CalcArity` function object. Since we used compile-time integers in our transforms, the arity of the expression is encoded in the return type of the `CalcArity` function object. Proto grammars are valid TR1-style function objects, so you can use `boost::result_of<>` to figure out their return types.

With our compile-time assertions in place, when users provide too many or too few arguments to a calculator expression, as in:

    (_2 * _2)(42); // Oops, too few arguments!

... they will get a compile-time error message on the line with the assertion that reads something like this[6]:

    c:\boost\org\trunk\libs\proto\scratch\main.cpp(97) : error C2664: 'boost::mpl::asse
    rtion_failed' : cannot convert parameter 1 from 'boost::mpl::failed ************boo
    st::mpl::assert_relation<x,y,__formal>::************' to 'boost::mpl::assert<false>
    ::type'
       with
       [
           x=1,
           y=2,
           __formal=bool boost::mpl::operator==(boost::mpl::failed,boost::mpl::failed)
       ]

The point of this exercise was to show that we can write a fairly simple Proto grammar with embedded transforms that is declarative and readable and can compute interesting properties of arbitrarily complicated expressions. But transforms can do more than that. Boost.Xpressive uses transforms to turn expressions into finite state automata for matching regular expressions, and Boost.Spirit uses transforms to build recursive descent parser generators. Proto comes with a collection of built-in transforms that you can use to perform very sophisticated expression manipulations like these. In the next few sections we'll see some of them in action.

##### Transforms With State Accumulation

So far, we've only seen examples of grammars with transforms that accept one argument: the expression to transform. But consider for a moment how, in ordinary procedural code, you would turn a binary tree into a linked list. You would start with an empty list. Then, you would recursively convert the right branch to a list, and use the result as the initial state while converting the left branch to a list. That is, you would need a function that takes two parameters: the current node and the list so far. These sorts of accumulation problems are quite common when processing trees. The linked list is an example of an accumulation variable or state. Each iteration of the algorithm takes the current element and state, applies some binary function to the two and creates a new state. In the STL, this algorithm is called `std::accumulate()`. In many other languages, it is called fold. Let's see how to implement a fold algorithm with Proto transforms.

All Proto grammars can optionally accept a state parameter in addition to the expression to transform. If you want to fold a tree to a list, you'll need to make use of the state parameter to pass around the list you've built so far. As for the list, the Boost.Fusion library provides a `fusion::cons<>` type from which you can build heterogeneous lists. The type `fusion::nil` represents an empty list.

Below is a grammar that recognizes output expressions like `cout_ << 42 << '\n'` and puts the arguments into a Fusion list. It is explained below.

    // Fold the terminals in output statements like
    // "cout_ << 42 << '\n'" into a Fusion cons-list.
    struct FoldToList
      : proto::or_<
            // Don't add the ostream terminal to the list
            proto::when<
                proto::terminal< std::ostream & >
              , proto::_state
            >
            // Put all other terminals at the head of the
            // list that we're building in the "state" parameter
          , proto::when<
                proto::terminal<_>
              , fusion::cons<proto::_value, proto::_state>(
                    proto::_value, proto::_state
                )
            >
            // For left-shift operations, first fold the right
            // child to a list using the current state. Use
            // the result as the state parameter when folding
            // the left child to a list.
          , proto::when<
                proto::shift_left<FoldToList, FoldToList>
              , FoldToList(
                    proto::_left
                  , FoldToList(proto::_right, proto::_state)
                )
            >
        >
    {};

Before reading on, see if you can apply what you know already about object, callable and primitive transforms to figure out how this grammar works.

When you use the `FoldToList` function, you'll need to pass two arguments: the expression to fold, and the initial state: an empty list. Those two arguments get passed around to each transform. We learned previously that `proto::_value` is a primitive transform that accepts a terminal expression and extracts its value. What we didn't know until now was that it also accepts the current state and ignores it. `proto::_state` is also a primitive transform. It accepts the current expression, which it ignores, and the current state, which it returns.

When we find a terminal, we stick it at the head of the cons list, using the current state as the tail of the list. (The first alternate causes the `ostream` to be skipped. We don't want `cout` in the list.) When we find a shift-left node, we apply the following transform:

    // Fold the right child and use the result as
    // state while folding the right.
    FoldToList(
        proto::_left
      , FoldToList(proto::_right, proto::_state)
    )

You can read this transform as follows: using the current state, fold the right child to a list. Use the new list as the state while folding the left child to a list.

| Tip
If your compiler is Microsoft Visual C++, you'll find that the above transform does not compile. The compiler has bugs with its handling of nested function types. You can work around the bug by wrapping the inner transform in `proto::call<>` as follows:
    FoldToList(
        proto::_left
      , proto::call<FoldToList(proto::_right, proto::_state)>
    )
`proto::call<>` turns a callable transform into a primitive transform, but more on that later.

Now that we have defined the `FoldToList` function object, we can use it to turn output expressions into lists as follows:

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

    // This is the type of the list we build below
    typedef
        fusion::cons<
            int
          , fusion::cons<
                double
              , fusion::cons<
                    char
                  , fusion::nil
                >
            >
        >
    result_type;

    // Fold an output expression into a Fusion list, using
    // fusion::nil as the initial state of the transformation.
    FoldToList to_list;
    result_type args = to_list(cout_ << 1 << 3.14 << '\n', fusion::nil());

    // Now "args" is the list: {1, 3.14, '\n'}

When writing transforms, "fold" is such a basic operation that Proto provides a number of built-in fold transforms. We'll get to them later. For now, rest assured that you won't always have to stretch your brain so far to do such basic things.

##### Passing Auxiliary Data to Transforms

In the last section, we saw that we can pass a second parameter to grammars with transforms: an accumulation variable or state that gets updated as your transform executes. There are times when your transforms will need to access auxiliary data that does not accumulate, so bundling it with the state parameter is impractical. Instead, you can pass auxiliary data as a third parameter, known as the data parameter.

Let's modify our previous example so that it writes each terminal to `std::cout` before it puts it into a list. This could be handy for debugging your transforms, for instance. We can make it general by passing a `std::ostream` into the transform in the data parameter. Within the transform itself, we can retrieve the `ostream` with the `proto::_data` transform. The strategy is as follows: use the `proto::and_<>` transform to chain two actions. The second action will create the `fusion::cons<>` node as before. The first action, however, will display the current expression. For that, we first construct an instance of `proto::functional::display_expr` and then call it.

    // Fold the terminals in output statements like
    // "cout_ << 42 << '\n'" into a Fusion cons-list.
    struct FoldToList
      : proto::or_<
            // Don't add the ostream terminal to the list
            proto::when<
                proto::terminal< std::ostream & >
              , proto::_state
            >
            // Put all other terminals at the head of the
            // list that we're building in the "state" parameter
          , proto::when<
                proto::terminal<_>
              , proto::and_<
                    // First, write the terminal to an ostream passed
                    // in the data parameter
                    proto::lazy<
                        proto::make<proto::functional::display_expr(proto::_data)>(_)
                    >
                    // Then, constuct the new cons list.
                  , fusion::cons<proto::_value, proto::_state>(
                        proto::_value, proto::_state
                    )
                >
            >
            // For left-shift operations, first fold the right
            // child to a list using the current state. Use
            // the result as the state parameter when folding
            // the left child to a list.
          , proto::when<
                proto::shift_left<FoldToList, FoldToList>
              , FoldToList(
                    proto::_left
                  , FoldToList(proto::_right, proto::_state, proto::_data)
                  , proto::_data
                )
            >
        >
    {};

This is a lot to take in, no doubt. But focus on the second `when` clause above. It says: when you find a terminal, first display the terminal using the `ostream` you find in the data parameter, then take the value of the terminal and the current state to build a new `cons` list. The function object `display_expr` does the job of printing the terminal, and `proto::and_<>` chains the actions together and executes them in sequence, returning the result of the last one.

| Note
Also new is `proto::lazy<>`. Sometimes you don't have a ready-made callable object to execute. Instead, you want to first make one and then execute it. Above, we need to create a `display_expr`, initializing it with our `ostream`. After that, we want to invoke it by passing it the current expression. It's as if we were doing `display_expr(std::cout)(the-expr)`. We achieve this two-phase evaluation using `proto::lazy<>`. If this doesn't make sense yet, don't worry about it.

We can use the above transform as before, but now we can pass an `ostream` as the third parameter and get to watch the transform in action. Here's a sample usage:

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

    // This is the type of the list we build below
    typedef
        fusion::cons<
            int
          , fusion::cons<
                double
              , fusion::cons<
                    char
                  , fusion::nil
                >
            >
        >
    result_type;

    // Fold an output expression into a Fusion list, using
    // fusion::nil as the initial state of the transformation.
    // Pass std::cout as the data parameter so that we can track
    // the progress of the transform on the console.
    FoldToList to_list;
    result_type args = to_list(cout_ << 1 << 3.14 << '\n', fusion::nil(), std::cout);

    // Now "args" is the list: {1, 3.14, '\n'}

This code displays the following:

    terminal(
    )
    terminal(3.14)
    terminal(1)

This is a rather round-about way of demonstrating that you can pass extra data to a transform as a third parameter. There are no restrictions on what this parameter can be, and, unlike the state parameter, Proto will never mess with it.

###### Transform Environment Variables

| Note
This is an advanced topic. Feel free to skip if you are new to Proto.

The example above uses the data parameter as a transport mechanism for an unstructured blob of data; in this case, a reference to an `ostream`. As your Proto algorithms become more sophisticated, you may find that an unstructured blob of data isn't terribly convenient to work with. Different parts of your algorithm may be interested in different bits of data. What you want, instead, is a way to pass in a collection of environment variables to a transform, like a collection of key/value pairs. Then, you can easily get at the piece of data you want by asking the data parameter for the value associated with a particular key. Proto's transform environments give you just that.

Let's start by defining a key.

    BOOST_PROTO_DEFINE_ENV_VAR(mykey_type, mykey);

This defines a global constant `mykey` with the type `mykey_type`. We can use `mykey` to store a piece of assiciated data in a transform environment, as so:

    // Call the MyEval algorithm with a transform environment containing
    // two key/value pairs: one for proto::data and one for mykey
    MyEval()( expr, state, (proto::data = 42, mykey = "hello world") );

The above means to invoke the `MyEval` algorithm with three parameters: an expression, an initial state, and a transform environment containing two key/value pairs.

From within a Proto algorithm, you can access the values associated with different keys using the `proto::_env_var<>` transform. For instance, `proto::_env_var<mykey_type>` would fetch the value `"hello world"` from the transform environment created above.

The `proto::_data` transform has some additional smarts. Rather than always returning the third parameter regarless of whether it is a blob or a transform environment, it checks first to see if it's a blob or not. If so, that's what gets returned. If not, it returns the value associated with the `proto::data` key. In the above example, that would be the value `42`.

There's a small host of functions, metafunction, and classes that you can use to create and manipulate transform environments, some for testing whether an object is a transform environment, some for coercing an object to be a transform environment, and some for querying a transform environment whether or not is has a value for a particular key. For an exhaustive treatment of the topic, check out the reference for the `boost/proto/transform/env.hpp` header.

##### Implicit Parameters to Primitive Transforms

Let's use `FoldToList` example from the previous two sections to illustrate some other niceties of Proto transforms. We've seen that grammars, when used as function objects, can accept up to 3 parameters, and that when using these grammars in callable transforms, you can also specify up to 3 parameters. Let's take another look at the transform associated with non-terminals from the last section:

    FoldToList(
        proto::_left
      , FoldToList(proto::_right, proto::_state, proto::_data)
      , proto::_data
    )

Here we specify all three parameters to both invocations of the `FoldToList` grammar. But we don't have to specify all three. If we don't specify a third parameter, `proto::_data` is assumed. Likewise for the second parameter and `proto::_state`. So the above transform could have been written more simply as:

    FoldToList(
        proto::_left
      , StringCopy(proto::_right)
    )

The same is true for any primitive transform. The following are all equivalent:

Table 20.9. Implicit Parameters to Primitive Transforms

Equivalent Transforms
`proto::when<_, FoldToList>`
`proto::when<_, FoldToList()>`
`proto::when<_, FoldToList(_)>`
`proto::when<_, FoldToList(_, proto::_state)>`
`proto::when<_, FoldToList(_, proto::_state, proto::_data)>`

| Note
Grammars Are Primitive Transforms Are Function Objects So far, we've said that all Proto grammars are function objects. But it's more accurate to say that Proto grammars are primitive transforms -- a special kind of function object that takes between 1 and 3 arguments, and that Proto knows to treat specially when used in a callable transform, as in the table above.

| Note
Not All Function Objects Are Primitive Transforms You might be tempted now to drop the `_state` and `_data` parameters for all your callable transforms. That would be an error. You can only do that for primitive transforms, and not all callables are primitive transforms. Later on, we'll see what distinguishes ordinary callables from their more powerful primitive transfor cousins, but the short version is this: primitive transforms inherit from `proto::transform<>`.

Once you know that primitive transforms will always receive all three parameters -- expression, state, and data -- it makes things possible that wouldn't be otherwise. For instance, consider that for binary expressions, these two transforms are equivalent. Can you see why?

Table 20.10. Two Equivalent Transforms

Without `proto::reverse_fold<>` | With `proto::reverse_fold<>`
--- | ---
    FoldToList(
        proto::_left
      , FoldToList(proto::_right, proto::_state, proto::_data)
      , proto::_data
    )
    proto::reverse_fold<_, proto::_state, FoldToList>

##### Unpacking Expressions

Processing expressions with an arbitrary number of children can be a pain. What if you want to do something to each child, then pass the results as arguments to some other function? Can you do it just once without worrying about how many children an expression has? Yes. This is where Proto's unpacking expressions come in handy. Unpacking expressions give you a way to write callable and object transforms that handle n-ary expressions.

| Note
Inspired by C++11 Variadic Templates Proto's unpacking expressions take inspiration from the C++11 feature of the same name. If you are familiar with variadic functions, and in particular how to expand a function parameter pack, this discussion should seem very familiar. However, this feature doesn't actually use any C++11 features, so the code describe here will work with any compliant C++98 compiler.

###### Example: A C++ Expression Evaluator

Proto has the built-in `proto::_default<>` transform for evaluating Proto expressions in a C++-ish way. But if it didn't, it wouldn't be too hard to implement one from scratch using Proto's unpacking patterns. The transform `eval` below does just that.

    // A callable polymorphic function object that takes an unpacked expression
    // and a tag, and evaluates the expression. A plus tag and two operands adds
    // them with operator +, for instance.
    struct do_eval : proto::callable
    {
        typedef double result_type;

    #define UNARY_OP(TAG, OP)                                                       \
        template<typename Arg>                                                      \
        double operator()(proto::tag::TAG, Arg arg) const                           \
        {                                                                           \
            return OP arg;                                                          \
        }                                                                           \
        /**/

    #define BINARY_OP(TAG, OP)                                                      \
        template<typename Left, typename Right>                                     \
        double operator()(proto::tag::TAG, Left left, Right right) const            \
        {                                                                           \
            return left OP right;                                                   \
        }                                                                           \
        /**/

        UNARY_OP(negate, -)
        BINARY_OP(plus, +)
        BINARY_OP(minus, -)
        BINARY_OP(multiplies, *)
        BINARY_OP(divides, /)
        /*... others ...*/
    };

    struct eval
      : proto::or_<
            // Evaluate terminals by simply returning their value
            proto::when<proto::terminal<_>, proto::_value>

            // Non-terminals are handled by unpacking the expression,
            // recursively calling eval on each child, and passing
            // the results along with the expression's tag to do_eval
            // defined above.
          , proto::otherwise<do_eval(proto::tag_of<_>(), eval(proto::pack(_))...)>
            // UNPACKING PATTERN HERE -------------------^^^^^^^^^^^^^^^^^^^^^^^^
        >
    {};

The bulk of the above code is devoted to the `do_eval` function object that maps tag types to behaviors, but the interesting bit is the definition of the `eval` algorithm at the bottom. Terminals are handled quite simply, but non-terminals could be unary, binary, ternary, even n-ary if we consider function call expressions. The `eval` algorithm handles this uniformly with the help of an unpacking pattern.

Non-terminals are evaluated with this callable transform:

    do_eval(proto::tag_of<_>(), eval(proto::pack(_))...)

You can read this as: call the `do_eval` function object with the tag of the current expression and all its children after they have each been evaluated with `eval`. The unpacking pattern is the bit just before the ellipsis: `eval(proto::pack(_))`.

What's going on here is this. The unpacking expression gets repeated once for each child in the expression currently being evaluated. In each repetition, the type `proto::pack(_)` gets replaced with `proto::_child_c<N>`. So, if a unary expression is passed to `eval`, it actually gets evaluated like this:

    // After the unpacking pattern is expanded for a unary expression
    do_eval(proto::tag_of<_>(), eval(proto::_child_c<0>))

And when passed a binary expression, the unpacking pattern expands like this:

    // After the unpacking pattern is expanded for a binary expression
    do_eval(proto::tag_of<_>(), eval(proto::_child_c<0>), eval(proto::_child_c<1>))

Although it can't happen in our example, when passed a terminal, the unpacking pattern expands such that it extracts the value from the terminal instead of the children. So it gets handled like this:

    // If a terminal were passed to this transform, Proto would try
    // to evaluate it like this, which would fail:
    do_eval(proto::tag_of<_>(), eval(proto::_value))

That doesn't make sense. `proto::_value` would return something that isn't a Proto expression, and `eval` wouldn't be able to evaluate it. Proto algorithms don't work unless you pass them Proto expressions.

| Note
Kickin' It Old School You may be thinking, my compiler doesn't support C++11 variadic templates! How can this possibly work? The answer is simple: The `...` above isn't a C++11 pack expansion. It's actually an old-school C-style vararg. Remember that callable and object transforms are function types. A transform with one of these pseudo-pack expansions is really just the type of a boring, old vararg function. Proto just interprets it differently.

Unpacking patterns are very expressive. Any callable or object transform can be used as an unpacking pattern, so long as `proto::pack(_)` appears exactly once somewhere within it. This gives you a lot of flexibility in how you want to process the children of an expression before passing them on to some function object or object constructor.

##### Separating Grammars And Transforms

| Note
This is an advanced topic that is only necessary for people defining large EDSLs. Feel free to skip this if you're just getting started with Proto.

So far, we've seen examples of grammars with embedded transforms. In practice, grammars can get pretty large, and you may want to use them to drive several different computations. For instance, you may have a grammar for a linear algebra domain, and you may want to use it to compute the shape of the result (vector or matrix?) and also to compute the result optimally. You don't want to have to copy and paste the whole shebang just to tweak one of the embedded transforms. What you want instead is to define the grammar once, and specify the transforms later when you're ready to evaluate an expression. For that, you use external transforms. The pattern you'll use is this: replace one or more of the transforms in your grammar with the special placeholder `proto::external_transform`. Then, you'll create a bundle of transforms that you will pass to the grammar in the data parameter (the 3rd parameter after the expression and state) when evaluating it.

To illustrate external transforms, we'll build a calculator evaluator that can be configured to throw an exception on division by zero. Here is a bare-bones front end that defines a domain, a grammar, an expression wrapper, and some placeholder terminals.

    #include <boost/assert.hpp>
    #include <boost/mpl/int.hpp>
    #include <boost/fusion/container/vector.hpp>
    #include <boost/fusion/container/generation/make_vector.hpp>
    #include <boost/proto/proto.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    namespace fusion = boost::fusion;

    // The argument placeholder type
    template<typename I> struct placeholder : I {};

    // The grammar for valid calculator expressions
    struct calc_grammar
      : proto::or_<
            proto::terminal<placeholder<proto::_> >
          , proto::terminal<int>
          , proto::plus<calc_grammar, calc_grammar>
          , proto::minus<calc_grammar, calc_grammar>
          , proto::multiplies<calc_grammar, calc_grammar>
          , proto::divides<calc_grammar, calc_grammar>
        >
    {};

    template<typename E> struct calc_expr;
    struct calc_domain : proto::domain<proto::generator<calc_expr> > {};

    template<typename E>
    struct calc_expr
      : proto::extends<E, calc_expr<E>, calc_domain>
    {
        calc_expr(E const &e = E()) : calc_expr::proto_extends(e) {}
    };

    calc_expr<proto::terminal<placeholder<mpl::int_<0> > >::type> _1;
    calc_expr<proto::terminal<placeholder<mpl::int_<1> > >::type> _2;

    int main()
    {
        // Build a calculator expression, and do nothing with it.
        (_1 + _2);
    }

Now, let's embed transforms into `calc_grammar` so that we can use it to evaluate calculator expressions:

    // The calculator grammar with embedded transforms for evaluating expression.
    struct calc_grammar
      : proto::or_<
            proto::when<
                proto::terminal<placeholder<proto::_> >
              , proto::functional::at(proto::_state, proto::_value)
            >
          , proto::when<
                proto::terminal<int>
              , proto::_value
            >
          , proto::when<
                proto::plus<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
          , proto::when<
                proto::minus<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
          , proto::when<
                proto::multiplies<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
          , proto::when<
                proto::divides<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
        >
    {};

With this definition of `calc_grammar` we can evaluate expressions by passing along a Fusion vector containing the values to use for the `_1` and `_2` placeholders:

    int result = calc_grammar()(_1 + _2, fusion::make_vector(3, 4));
    BOOST_ASSERT(result == 7);

We also want an alternative evaluation strategy that checks for division by zero and throws an exception. Just how ridiculous would it be to copy the entire `calc_grammar` just to change the one line that transforms division expressions?! External transforms are ideally suited to this problem.

First, we give the division rule in our grammar a "name"; that is, we make it a struct. We'll use this unique type later to dispatch to the right transforms.

    struct calc_grammar;
    struct divides_rule : proto::divides<calc_grammar, calc_grammar> {};

Next, we change `calc_grammar` to make the handling of division expressions external.

    // The calculator grammar with an external transform for evaluating
    // division expressions.
    struct calc_grammar
      : proto::or_<
            /* ... as before ... */
          , proto::when<
                divides_rule
              , proto::external_transform
            >
        >
    {};

The use of `proto::external_transform` above makes the handling of division expressions externally parameterizeable.

Next, we use `proto::external_transforms<>` (note the trailing 's') to capture our evaluation strategy in a bundle that we can pass along to the transform in the data parameter. Read on for the explanation.

    // Evaluate division nodes as before
    struct non_checked_division
      : proto::external_transforms<
            proto::when< divides_rule, proto::_default<calc_grammar> >
        >
    {};

    /* ... */

    non_checked_division non_checked;
    int result2 = calc_grammar()(_1 / _2, fusion::make_vector(6, 2), non_checked);

The struct `non_cecked_division` associates the transform `proto::_default<calc_grammar>` with the `divides_rule` grammar rule. An instance of that struct is passed along as the third parameter when invoking `calc_grammar`.

Now, let's implement checked division. The rest should be unsurprising.

    struct division_by_zero : std::exception {};

    struct do_checked_divide : proto::callable
    {
        typedef int result_type;
        int operator()(int left, int right) const
        {
            if (right == 0) throw division_by_zero();
            return left / right;
        }
    };

    struct checked_division
      : proto::external_transforms<
            proto::when<
                divides_rule
              , do_checked_divide(calc_grammar(proto::_left), calc_grammar(proto::_right))
            >
        >
    {};

    /* ... */

    try
    {
        checked_division checked;
        int result3 = calc_grammar_extern()(_1 / _2, fusion::make_vector(6, 0), checked);
    }
    catch(division_by_zero)
    {
        std::cout << "caught division by zero!\n";
    }

The above code demonstrates how a single grammar can be used with different transforms specified externally. This makes it possible to reuse a grammar to drive several different computations.

###### Separating Data From External Transforms

As described above, the external transforms feature usurps the data parameter, which is intended to be a place where you can pass arbitrary data, and gives it a specific meaning. But what if you are already using the data parameter for something else? The answer is to use a transform environment. By associating your external transforms with the `proto::transforms` key, you are free to pass arbitrary data in other slots.

To continue the above example, what if we also needed to pass a piece of data into our transform along with the external transforms? It would look like this:

    int result3 = calc_grammar_extern()(
        _1 / _2
      , fusion::make_vector(6, 0)
      , (proto::data = 42, proto::transforms = checked)
    );

In the above invocation of the `calc_grammar_extern` algorithm, the map of external transforms is associated with the `proto::transforms` key and passed to the algorithm in a transform environment. Also in the transform environment is a key/value pair that associated the value `42` with the `proto::data` key.

##### Proto's Built-In Transforms

Primitive transforms are the building blocks for more interesting composite transforms. Proto defines a bunch of generally useful primitive transforms. They are summarized below.

`proto::_value`

  Given a terminal expression, return the value of the terminal.

`proto::_child_c<>`

  Given a non-terminal expression, `proto::_child_c<`N`>` returns the `N`-th child.

`proto::_child`

  A synonym for `proto::_child_c<0>`.

`proto::_left`

  A synonym for `proto::_child_c<0>`.

`proto::_right`

  A synonym for `proto::_child_c<1>`.

`proto::_expr`

  Returns the current expression unmodified.

`proto::_state`

  Returns the current state unmodified.

`proto::_data`

  Returns the current data unmodified.

`proto::call<>`

  For a given callable transform ``CT``, `proto::call<`CT`>` turns the callable transform into a primitive transform. This is useful for disambiguating callable transforms from object transforms, and also for working around compiler bugs with nested function types.

`proto::make<>`

  For a given object transform ``OT``, `proto::make<`OT`>` turns the object transform into a primitive transform. This is useful for disambiguating object transforms from callable transforms, and also for working around compiler bugs with nested function types.

`proto::_default<>`

  Given a grammar `G`, `proto::_default<`G`>` evaluates the current node according to the standard C++ meaning of the operation the node represents. For instance, if the current node is a binary plus node, the two children will both be evaluated according to ``G`` and the results will be added and returned. The return type is deduced with the help of the Boost.Typeof library.

`proto::fold<>`

  Given three transforms ``ET``, ``ST``, and ``FT``, `proto::fold<`ET`, `ST`, `FT`>` first evaluates ``ET`` to obtain a Fusion sequence and ``ST`` to obtain an initial state for the fold, and then evaluates ``FT`` for each element in the sequence to generate the next state from the previous.

`proto::reverse_fold<>`

  Like `proto::fold<>`, except the elements in the Fusion sequence are iterated in reverse order.

`proto::fold_tree<>`

  Like `proto::fold<`ET`, `ST`, `FT`>`, except that the result of the ``ET`` transform is treated as an expression tree that is flattened to generate the sequence to be folded. Flattening an expression tree causes child nodes with the same tag type as the parent to be put into sequence. For instance, `a >> b >> c` would be flattened to the sequence [`a`, `b`, `c`], and this is the sequence that would be folded.

`proto::reverse_fold_tree<>`

  Like `proto::fold_tree<>`, except that the flattened sequence is iterated in reverse order.

`proto::lazy<>`

  A combination of `proto::make<>` and `proto::call<>` that is useful when the nature of the transform depends on the expression, state and/or data parameters. `proto::lazy<R(A0,A1...An)>` first evaluates `proto::make<R()>` to compute a callable type `R2`. Then, it evaluates `proto::call<R2(A0,A1...An)>`.

###### All Grammars Are Primitive Transforms

In addition to the above primitive transforms, all of Proto's grammar elements are also primitive transforms. Their behaviors are described below.

`proto::_`

  Return the current expression unmodified.

`proto::or_<>`

  For the specified set of alternate sub-grammars, find the one that matches the given expression and apply its associated transform.

`proto::and_<>`

  For the given set of sub-grammars, apply all the associated transforms and return the result of the last.

`proto::not_<>`

  Return the current expression unmodified.

`proto::if_<>`

  Given three transforms, evaluate the first and treat the result as a compile-time Boolean value. If it is true, evaluate the second transform. Otherwise, evaluate the third.

`proto::switch_<>`

  As with `proto::or_<>`, find the sub-grammar that matches the given expression and apply its associated transform.

`proto::terminal<>`

  Return the current terminal expression unmodified.

`proto::plus<>`, `proto::nary_expr<>`, et. al.

  A Proto grammar that matches a non-terminal such as `proto::plus<`G0`, `G1`>`, when used as a primitive transform, creates a new plus node where the left child is transformed according to ``G0`` and the right child with ``G1``.

###### The Pass-Through Transform

Note the primitive transform associated with grammar elements such as `proto::plus<>` described above. They possess a so-called pass-through transform. The pass-through transform accepts an expression of a certain tag type (say, `proto::tag::plus`) and creates a new expression of the same tag type, where each child expression is transformed according to the corresponding child grammar of the pass-through transform. So for instance this grammar ...

    proto::function< X, proto::vararg<Y> >

... matches function expressions where the first child matches the `X` grammar and the rest match the `Y` grammar. When used as a transform, the above grammar will create a new function expression where the first child is transformed according to `X` and the rest are transformed according to `Y`.

The following class templates in Proto can be used as grammars with pass-through transforms:

Table 20.11. Class Templates With Pass-Through Transforms

Templates with Pass-Through Transforms
`proto::unary_plus<>`
`proto::negate<>`
`proto::dereference<>`
`proto::complement<>`
`proto::address_of<>`
`proto::logical_not<>`
`proto::pre_inc<>`
`proto::pre_dec<>`
`proto::post_inc<>`
`proto::post_dec<>`
`proto::shift_left<>`
`proto::shift_right<>`
`proto::multiplies<>`
`proto::divides<>`
`proto::modulus<>`
`proto::plus<>`
`proto::minus<>`
`proto::less<>`
`proto::greater<>`
`proto::less_equal<>`
`proto::greater_equal<>`
`proto::equal_to<>`
`proto::not_equal_to<>`
`proto::logical_or<>`
`proto::logical_and<>`
`proto::bitwise_and<>`
`proto::bitwise_or<>`
`proto::bitwise_xor<>`
`proto::comma<>`
`proto::mem_ptr<>`
`proto::assign<>`
`proto::shift_left_assign<>`
`proto::shift_right_assign<>`
`proto::multiplies_assign<>`
`proto::divides_assign<>`
`proto::modulus_assign<>`
`proto::plus_assign<>`
`proto::minus_assign<>`
`proto::bitwise_and_assign<>`
`proto::bitwise_or_assign<>`
`proto::bitwise_xor_assign<>`
`proto::subscript<>`
`proto::if_else_<>`
`proto::function<>`
`proto::unary_expr<>`
`proto::binary_expr<>`
`proto::nary_expr<>`

###### The Many Roles of Proto Operator Metafunctions

We've seen templates such as `proto::terminal<>`, `proto::plus<>` and `proto::nary_expr<>` fill many roles. They are metafunction that generate expression types. They are grammars that match expression types. And they are primitive transforms. The following code samples show examples of each.

As Metafunctions ...

    // proto::terminal<> and proto::plus<> are metafunctions
    // that generate expression types:
    typedef proto::terminal<int>::type int_;
    typedef proto::plus<int_, int_>::type plus_;

    int_ i = {42}, j = {24};
    plus_ p = {i, j};

As Grammars ...

    // proto::terminal<> and proto::plus<> are grammars that
    // match expression types
    struct Int : proto::terminal<int> {};
    struct Plus : proto::plus<Int, Int> {};

    BOOST_MPL_ASSERT(( proto::matches< int_, Int > ));
    BOOST_MPL_ASSERT(( proto::matches< plus_, Plus > ));

As Primitive Transforms ...

    // A transform that removes all unary_plus nodes in an expression
    struct RemoveUnaryPlus
      : proto::or_<
            proto::when<
                proto::unary_plus<RemoveUnaryPlus>
              , RemoveUnaryPlus(proto::_child)
            >
            // Use proto::terminal<> and proto::nary_expr<>
            // both as grammars and as primitive transforms.
          , proto::terminal<_>
          , proto::nary_expr<_, proto::vararg<RemoveUnaryPlus> >
        >
    {};

    int main()
    {
        proto::literal<int> i(0);

        proto::display_expr(
            +i - +(i - +i)
        );

        proto::display_expr(
            RemoveUnaryPlus()( +i - +(i - +i) )
        );
    }

The above code displays the following, which shows that unary plus nodes have been stripped from the expression:

    minus(
        unary_plus(
            terminal(0)
        )
      , unary_plus(
            minus(
                terminal(0)
              , unary_plus(
                    terminal(0)
                )
            )
        )
    )
    minus(
        terminal(0)
      , minus(
            terminal(0)
          , terminal(0)
        )
    )

##### Building Custom Primitive Transforms

In previous sections, we've seen how to compose larger transforms out of smaller transforms using function types. The smaller transforms from which larger transforms are composed are primitive transforms, and Proto provides a bunch of common ones such as `_child0` and `_value`. In this section we'll see how to author your own primitive transforms.

| Note
There are a few reasons why you might want to write your own primitive transforms. For instance, your transform may be complicated, and composing it out of primitives becomes unwieldy. You might also need to work around compiler bugs on legacy compilers that make composing transforms using function types problematic. Finally, you might also decide to define your own primitive transforms to improve compile times. Since Proto can simply invoke a primitive transform directly without having to process arguments or differentiate callable transforms from object transforms, primitive transforms are more efficient.

Primitive transforms inherit from `proto::transform<>` and have a nested `impl<>` template that inherits from `proto::transform_impl<>`. For example, this is how Proto defines the `_child_c<`N`>` transform, which returns the `N`-th child of the current expression:

    namespace boost { namespace proto
    {
        // A primitive transform that returns N-th child
        // of the current expression.
        template<int N>
        struct _child_c : transform<_child_c<N> >
        {
            template<typename Expr, typename State, typename Data>
            struct impl : transform_impl<Expr, State, Data>
            {
                typedef
                    typename result_of::child_c<Expr, N>::type
                result_type;

                result_type operator ()(
                    typename impl::expr_param expr
                  , typename impl::state_param state
                  , typename impl::data_param data
                ) const
                {
                    return proto::child_c<N>(expr);
                }
            };
        };

        // Note that _child_c<N> is callable, so that
        // it can be used in callable transforms, as:
        //   _child_c<0>(_child_c<1>)
        template<int N>
        struct is_callable<_child_c<N> >
          : mpl::true_
        {};
    }}

The `proto::transform<>` base class provides the `operator()` overloads and the nested `result<>` template that make your transform a valid function object. These are implemented in terms of the nested `impl<>` template you define.

The `proto::transform_impl<>` base class is a convenience. It provides some nested typedefs that are generally useful. They are specified in the table below:

Table 20.12. proto::transform_impl<Expr, State, Data> typedefs

typedef | Equivalent To
--- | ---
`expr` | `typename remove_reference<Expr>::type`
`state` | `typename remove_reference<State>::type`
`data` | `typename remove_reference<Data>::type`
`expr_param` | `typename add_reference<typename add_const<Expr>::type>::type`
`state_param` | `typename add_reference<typename add_const<State>::type>::type`
`data_param` | `typename add_reference<typename add_const<Data>::type>::type`

You'll notice that `_child_c::impl::operator()` takes arguments of types `expr_param`, `state_param`, and `data_param`. The typedefs make it easy to accept arguments by reference or const reference accordingly.

The only other interesting bit is the `is_callable<>` specialization, which will be described in the next section.

##### Making Your Transform Callable

Transforms are typically of the form `proto::when< Something, R(A0,A1,...) >`. The question is whether `R` represents a function to call or an object to construct, and the answer determines how `proto::when<>` evaluates the transform. `proto::when<>` uses the `proto::is_callable<>` trait to disambiguate between the two. Proto does its best to guess whether a type is callable or not, but it doesn't always get it right. It's best to know the rules Proto uses, so that you know when you need to be more explicit.

For most types `R`, `proto::is_callable<R>` checks for inheritance from `proto::callable`. However, if the type `R` is a template specialization, Proto assumes that it is not callable even if the template inherits from `proto::callable`. We'll see why in a minute. Consider the following erroneous callable object:

    // Proto can't tell this defines something callable!
    template<typename T>
    struct times2 : proto::callable
    {
        typedef T result_type;

        T operator()(T i) const
        {
            return i * 2;
        }
    };

    // ERROR! This is not going to multiply the int by 2:
    struct IntTimes2
      : proto::when<
            proto::terminal<int>
          , times2<int>(proto::_value)
        >
    {};

The problem is that Proto doesn't know that `times2<int>` is callable, so rather that invoking the `times2<int>` function object, Proto will try to construct a `times2<int>` object and initialize it will an `int`. That will not compile.

| Note
Why can't Proto tell that `times2<int>` is callable? After all, it inherits from `proto::callable`, and that is detectable, right? The problem is that merely asking whether some type `X<Y>` inherits from `callable` will cause the template `X<Y>` to be instantiated. That's a problem for a type like `std::vector<_value(_child1)>`. `std::vector<>` will not suffer to be instantiated with `_value(_child1)` as a template parameter. Since merely asking the question will sometimes result in a hard error, Proto can't ask; it has to assume that `X<Y>` represents an object to construct and not a function to call.

There are a couple of solutions to the `times2<int>` problem. One solution is to wrap the transform in `proto::call<>`. This forces Proto to treat `times2<int>` as callable:

    // OK, calls times2<int>
    struct IntTimes2
      : proto::when<
            proto::terminal<int>
          , proto::call<times2<int>(proto::_value)>
        >
    {};

This can be a bit of a pain, because we need to wrap every use of `times2<int>`, which can be tedious and error prone, and makes our grammar cluttered and harder to read.

Another solution is to specialize `proto::is_callable<>` on our `times2<>` template:

    namespace boost { namespace proto
    {
        // Tell Proto that times2<> is callable
        template<typename T>
        struct is_callable<times2<T> >
          : mpl::true_
        {};
    }}

    // OK, times2<> is callable
    struct IntTimes2
      : proto::when<
            proto::terminal<int>
          , times2<int>(proto::_value)
        >
    {};

This is better, but still a pain because of the need to open Proto's namespace.

You could simply make sure that the callable type is not a template specialization. Consider the following:

    // No longer a template specialization!
    struct times2int : times2<int> {};

    // OK, times2int is callable
    struct IntTimes2
      : proto::when<
            proto::terminal<int>
          , times2int(proto::_value)
        >
    {};

This works because now Proto can tell that `times2int` inherits (indirectly) from `proto::callable`. Any non-template types can be safely checked for inheritance because, as they are not templates, there is no worry about instantiation errors.

There is one last way to tell Proto that `times2<>` is callable. You could add an extra dummy template parameter that defaults to `proto::callable`:

    // Proto will recognize this as callable
    template<typename T, typename Callable = proto::callable>
    struct times2 : proto::callable
    {
        typedef T result_type;

        T operator()(T i) const
        {
            return i * 2;
        }
    };

    // OK, this works!
    struct IntTimes2
      : proto::when<
            proto::terminal<int>
          , times2<int>(proto::_value)
        >
    {};

Note that in addition to the extra template parameter, `times2<>` still inherits from `proto::callable`. That's not necessary in this example but it is good style because any types derived from `times2<>` (as `times2int` defined above) will still be considered callable.

### Examples

A code example is worth a thousand words ...

#### Hello World: Building an Expression Template and Evaluating It

A trivial example which builds and expression template and evaluates it.

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

    #include <iostream>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    // This #include is only needed for compilers that use typeof emulation:
    #include <boost/typeof/std/ostream.hpp>
    namespace proto = boost::proto;

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

#### Calc1: Defining an Evaluation Context

A simple example that builds a miniature embedded domain-specific language for lazy arithmetic expressions, with TR1 bind-style argument placeholders.

    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is a simple example of how to build an arithmetic expression
    // evaluator with placeholders.

    #include <iostream>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    namespace proto = boost::proto;
    using proto::_;

    template<int I> struct placeholder {};

    // Define some placeholders
    proto::terminal< placeholder< 1 > >::type const _1 = {{}};
    proto::terminal< placeholder< 2 > >::type const _2 = {{}};

    // Define a calculator context, for evaluating arithmetic expressions
    struct calculator_context
      : proto::callable_context< calculator_context const >
    {
        // The values bound to the placeholders
        double d[2];

        // The result of evaluating arithmetic expressions
        typedef double result_type;

        explicit calculator_context(double d1 = 0., double d2 = 0.)
        {
            d[0] = d1;
            d[1] = d2;
        }

        // Handle the evaluation of the placeholder terminals
        template<int I>
        double operator ()(proto::tag::terminal, placeholder<I>) const
        {
            return d[ I - 1 ];
        }
    };

    template<typename Expr>
    double evaluate( Expr const &expr, double d1 = 0., double d2 = 0. )
    {
        // Create a calculator context with d1 and d2 substituted for _1 and _2
        calculator_context const ctx(d1, d2);

        // Evaluate the calculator expression with the calculator_context
        return proto::eval(expr, ctx);
    }

    int main()
    {
        // Displays "5"
        std::cout << evaluate( _1 + 2.0, 3.0 ) << std::endl;

        // Displays "6"
        std::cout << evaluate( _1 * _2, 3.0, 2.0 ) << std::endl;

        // Displays "0.5"
        std::cout << evaluate( (_1 - _2) / _2, 3.0, 2.0 ) << std::endl;

        return 0;
    }

#### Calc2: Adding Members Using `proto::extends<>`

An extension of the Calc1 example that uses `proto::extends<>` to make calculator expressions valid function objects that can be used with STL algorithms.

    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This example enhances the simple arithmetic expression evaluator
    // in calc1.cpp by using proto::extends to make arithmetic
    // expressions immediately evaluable with operator (), a-la a
    // function object

    #include <iostream>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    namespace proto = boost::proto;
    using proto::_;

    template<typename Expr>
    struct calculator_expression;

    // Tell proto how to generate expressions in the calculator_domain
    struct calculator_domain
      : proto::domain<proto::generator<calculator_expression> >
    {};

    // Will be used to define the placeholders _1 and _2
    template<int I> struct placeholder {};

    // Define a calculator context, for evaluating arithmetic expressions
    // (This is as before, in calc1.cpp)
    struct calculator_context
      : proto::callable_context< calculator_context const >
    {
        // The values bound to the placeholders
        double d[2];

        // The result of evaluating arithmetic expressions
        typedef double result_type;

        explicit calculator_context(double d1 = 0., double d2 = 0.)
        {
            d[0] = d1;
            d[1] = d2;
        }

        // Handle the evaluation of the placeholder terminals
        template<int I>
        double operator ()(proto::tag::terminal, placeholder<I>) const
        {
            return d[ I - 1 ];
        }
    };

    // Wrap all calculator expressions in this type, which defines
    // operator () to evaluate the expression.
    template<typename Expr>
    struct calculator_expression
      : proto::extends<Expr, calculator_expression<Expr>, calculator_domain>
    {
        explicit calculator_expression(Expr const &expr = Expr())
          : calculator_expression::proto_extends(expr)
        {}

        BOOST_PROTO_EXTENDS_USING_ASSIGN(calculator_expression<Expr>)

        // Override operator () to evaluate the expression
        double operator ()() const
        {
            calculator_context const ctx;
            return proto::eval(*this, ctx);
        }

        double operator ()(double d1) const
        {
            calculator_context const ctx(d1);
            return proto::eval(*this, ctx);
        }

        double operator ()(double d1, double d2) const
        {
            calculator_context const ctx(d1, d2);
            return proto::eval(*this, ctx);
        }
    };

    // Define some placeholders (notice they're wrapped in calculator_expression<>)
    calculator_expression<proto::terminal< placeholder< 1 > >::type> const _1;
    calculator_expression<proto::terminal< placeholder< 2 > >::type> const _2;

    // Now, our arithmetic expressions are immediately executable function objects:
    int main()
    {
        // Displays "5"
        std::cout << (_1 + 2.0)( 3.0 ) << std::endl;

        // Displays "6"
        std::cout << ( _1 * _2 )( 3.0, 2.0 ) << std::endl;

        // Displays "0.5"
        std::cout << ( (_1 - _2) / _2 )( 3.0, 2.0 ) << std::endl;

        return 0;
    }

#### Calc3: Defining a Simple Transform

An extension of the Calc2 example that uses a Proto transform to calculate the arity of a calculator expression and statically assert that the correct number of arguments are passed.

    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This example enhances the arithmetic expression evaluator
    // in calc2.cpp by using a proto transform to calculate the
    // number of arguments an expression requires and using a
    // compile-time assert to guarantee that the right number of
    // arguments are actually specified.

    #include <iostream>
    #include <boost/mpl/int.hpp>
    #include <boost/mpl/assert.hpp>
    #include <boost/mpl/min_max.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    #include <boost/proto/transform.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    using proto::_;

    // Will be used to define the placeholders _1 and _2
    template<typename I> struct placeholder : I {};

    // This grammar basically says that a calculator expression is one of:
    //   - A placeholder terminal
    //   - Some other terminal
    //   - Some non-terminal whose children are calculator expressions
    // In addition, it has transforms that say how to calculate the
    // expression arity for each of the three cases.
    struct CalculatorGrammar
      : proto::or_<

            // placeholders have a non-zero arity ...
            proto::when< proto::terminal< placeholder<_> >, proto::_value >

            // Any other terminals have arity 0 ...
          , proto::when< proto::terminal<_>, mpl::int_<0>() >

            // For any non-terminals, find the arity of the children and
            // take the maximum. This is recursive.
          , proto::when< proto::nary_expr<_, proto::vararg<_> >
                 , proto::fold<_, mpl::int_<0>(), mpl::max<CalculatorGrammar, proto::_state>() > >

        >
    {};

    // Simple wrapper for calculating a calculator expression's arity.
    // It specifies mpl::int_<0> as the initial state. The data, which
    // is not used, is mpl::void_.
    template<typename Expr>
    struct calculator_arity
      : boost::result_of<CalculatorGrammar(Expr)>
    {};

    template<typename Expr>
    struct calculator_expression;

    // Tell proto how to generate expressions in the calculator_domain
    struct calculator_domain
      : proto::domain<proto::generator<calculator_expression> >
    {};

    // Define a calculator context, for evaluating arithmetic expressions
    // (This is as before, in calc1.cpp and calc2.cpp)
    struct calculator_context
      : proto::callable_context< calculator_context const >
    {
        // The values bound to the placeholders
        double d[2];

        // The result of evaluating arithmetic expressions
        typedef double result_type;

        explicit calculator_context(double d1 = 0., double d2 = 0.)
        {
            d[0] = d1;
            d[1] = d2;
        }

        // Handle the evaluation of the placeholder terminals
        template<typename I>
        double operator ()(proto::tag::terminal, placeholder<I>) const
        {
            return d[ I() - 1 ];
        }
    };

    // Wrap all calculator expressions in this type, which defines
    // operator () to evaluate the expression.
    template<typename Expr>
    struct calculator_expression
      : proto::extends<Expr, calculator_expression<Expr>, calculator_domain>
    {
        typedef
            proto::extends<Expr, calculator_expression<Expr>, calculator_domain>
        base_type;

        explicit calculator_expression(Expr const &expr = Expr())
          : base_type(expr)
        {}

        BOOST_PROTO_EXTENDS_USING_ASSIGN(calculator_expression<Expr>)

        // Override operator () to evaluate the expression
        double operator ()() const
        {
            // Assert that the expression has arity 0
            BOOST_MPL_ASSERT_RELATION(0, ==, calculator_arity<Expr>::type::value);
            calculator_context const ctx;
            return proto::eval(*this, ctx);
        }

        double operator ()(double d1) const
        {
            // Assert that the expression has arity 1
            BOOST_MPL_ASSERT_RELATION(1, ==, calculator_arity<Expr>::type::value);
            calculator_context const ctx(d1);
            return proto::eval(*this, ctx);
        }

        double operator ()(double d1, double d2) const
        {
            // Assert that the expression has arity 2
            BOOST_MPL_ASSERT_RELATION(2, ==, calculator_arity<Expr>::type::value);
            calculator_context const ctx(d1, d2);
            return proto::eval(*this, ctx);
        }
    };

    // Define some placeholders (notice they're wrapped in calculator_expression<>)
    calculator_expression<proto::terminal< placeholder< mpl::int_<1> > >::type> const _1;
    calculator_expression<proto::terminal< placeholder< mpl::int_<2> > >::type> const _2;

    // Now, our arithmetic expressions are immediately executable function objects:
    int main()
    {
        // Displays "5"
        std::cout << (_1 + 2.0)( 3.0 ) << std::endl;

        // Displays "6"
        std::cout << ( _1 * _2 )( 3.0, 2.0 ) << std::endl;

        // Displays "0.5"
        std::cout << ( (_1 - _2) / _2 )( 3.0, 2.0 ) << std::endl;

        // This won't compile because the arity of the
        // expression doesn't match the number of arguments
        // ( (_1 - _2) / _2 )( 3.0 );

        return 0;
    }

#### Lazy Vector: Controlling Operator Overloads

This example constructs a mini-library for linear algebra, using expression templates to eliminate the need for temporaries when adding vectors of numbers.

This example uses a domain with a grammar to prune the set of overloaded operators. Only those operators that produce valid lazy vector expressions are allowed.

    ///////////////////////////////////////////////////////////////////////////////
    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This example constructs a mini-library for linear algebra, using
    // expression templates to eliminate the need for temporaries when
    // adding vectors of numbers.
    //
    // This example uses a domain with a grammar to prune the set
    // of overloaded operators. Only those operators that produce
    // valid lazy vector expressions are allowed.

    #include <vector>
    #include <iostream>
    #include <boost/mpl/int.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    using proto::_;

    template<typename Expr>
    struct lazy_vector_expr;

    // This grammar describes which lazy vector expressions
    // are allowed; namely, vector terminals and addition
    // and subtraction of lazy vector expressions.
    struct LazyVectorGrammar
      : proto::or_<
            proto::terminal< std::vector<_> >
          , proto::plus< LazyVectorGrammar, LazyVectorGrammar >
          , proto::minus< LazyVectorGrammar, LazyVectorGrammar >
        >
    {};

    // Tell proto that in the lazy_vector_domain, all
    // expressions should be wrapped in laxy_vector_expr<>
    // and must conform to the lazy vector grammar.
    struct lazy_vector_domain
      : proto::domain<proto::generator<lazy_vector_expr>, LazyVectorGrammar>
    {};

    // Here is an evaluation context that indexes into a lazy vector
    // expression, and combines the result.
    template<typename Size = std::size_t>
    struct lazy_subscript_context
    {
        lazy_subscript_context(Size subscript)
          : subscript_(subscript)
        {}

        // Use default_eval for all the operations ...
        template<typename Expr, typename Tag = typename Expr::proto_tag>
        struct eval
          : proto::default_eval<Expr, lazy_subscript_context>
        {};

        // ... except for terminals, which we index with our subscript
        template<typename Expr>
        struct eval<Expr, proto::tag::terminal>
        {
            typedef typename proto::result_of::value<Expr>::type::value_type result_type;

            result_type operator ()( Expr const & expr, lazy_subscript_context & ctx ) const
            {
                return proto::value( expr )[ ctx.subscript_ ];
            }
        };

        Size subscript_;
    };

    // Here is the domain-specific expression wrapper, which overrides
    // operator [] to evaluate the expression using the lazy_subscript_context.
    template<typename Expr>
    struct lazy_vector_expr
      : proto::extends<Expr, lazy_vector_expr<Expr>, lazy_vector_domain>
    {
        lazy_vector_expr( Expr const & expr = Expr() )
          : lazy_vector_expr::proto_extends( expr )
        {}

        // Use the lazy_subscript_context<> to implement subscripting
        // of a lazy vector expression tree.
        template< typename Size >
        typename proto::result_of::eval< Expr, lazy_subscript_context<Size> >::type
        operator []( Size subscript ) const
        {
            lazy_subscript_context<Size> ctx(subscript);
            return proto::eval(*this, ctx);
        }
    };

    // Here is our lazy_vector terminal, implemented in terms of lazy_vector_expr
    template< typename T >
    struct lazy_vector
      : lazy_vector_expr< typename proto::terminal< std::vector<T> >::type >
    {
        typedef typename proto::terminal< std::vector<T> >::type expr_type;

        lazy_vector( std::size_t size = 0, T const & value = T() )
          : lazy_vector_expr<expr_type>( expr_type::make( std::vector<T>( size, value ) ) )
        {}

        // Here we define a += operator for lazy vector terminals that
        // takes a lazy vector expression and indexes it. expr[i] here
        // uses lazy_subscript_context<> under the covers.
        template< typename Expr >
        lazy_vector &operator += (Expr const & expr)
        {
            std::size_t size = proto::value(*this).size();
            for(std::size_t i = 0; i < size; ++i)
            {
                proto::value(*this)[i] += expr[i];
            }
            return *this;
        }
    };

    int main()
    {
        // lazy_vectors with 4 elements each.
        lazy_vector< double > v1( 4, 1.0 ), v2( 4, 2.0 ), v3( 4, 3.0 );

        // Add two vectors lazily and get the 2nd element.
        double d1 = ( v2 + v3 )[ 2 ];   // Look ma, no temporaries!
        std::cout << d1 << std::endl;

        // Subtract two vectors and add the result to a third vector.
        v1 += v2 - v3;                  // Still no temporaries!
        std::cout << '{' << v1[0] << ',' << v1[1]
                  << ',' << v1[2] << ',' << v1[3] << '}' << std::endl;

        // This expression is disallowed because it does not conform
        // to the LazyVectorGrammar
        //(v2 + v3) += v1;

        return 0;
    }

#### RGB: Type Manipulations with Proto Transforms

This is a simple example of doing arbitrary type manipulations with Proto transforms. It takes some expression involving primary colors and combines the colors according to arbitrary rules. It is a port of the RGB example from PETE.

    ///////////////////////////////////////////////////////////////////////////////
    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is a simple example of doing arbitrary type manipulations with proto
    // transforms. It takes some expression involving primary colors and combines
    // the colors according to arbitrary rules. It is a port of the RGB example
    // from PETE (http://www.codesourcery.com/pooma/download.html).

    #include <iostream>
    #include <boost/proto/core.hpp>
    #include <boost/proto/transform.hpp>
    namespace proto = boost::proto;

    struct RedTag
    {
        friend std::ostream &operator <<(std::ostream &sout, RedTag)
        {
            return sout << "This expression is red.";
        }
    };

    struct BlueTag
    {
        friend std::ostream &operator <<(std::ostream &sout, BlueTag)
        {
            return sout << "This expression is blue.";
        }
    };

    struct GreenTag
    {
        friend std::ostream &operator <<(std::ostream &sout, GreenTag)
        {
            return sout << "This expression is green.";
        }
    };

    typedef proto::terminal<RedTag>::type RedT;
    typedef proto::terminal<BlueTag>::type BlueT;
    typedef proto::terminal<GreenTag>::type GreenT;

    struct Red;
    struct Blue;
    struct Green;

    ///////////////////////////////////////////////////////////////////////////////
    // A transform that produces new colors according to some arbitrary rules:
    // red & green give blue, red & blue give green, blue and green give red.
    struct Red
      : proto::or_<
            proto::plus<Green, Blue>
          , proto::plus<Blue, Green>
          , proto::plus<Red, Red>
          , proto::terminal<RedTag>
        >
    {};

    struct Green
      : proto::or_<
            proto::plus<Red, Blue>
          , proto::plus<Blue, Red>
          , proto::plus<Green, Green>
          , proto::terminal<GreenTag>
        >
    {};

    struct Blue
      : proto::or_<
            proto::plus<Red, Green>
          , proto::plus<Green, Red>
          , proto::plus<Blue, Blue>
          , proto::terminal<BlueTag>
        >
    {};

    struct RGB
      : proto::or_<
            proto::when< Red, RedTag() >
          , proto::when< Blue, BlueTag() >
          , proto::when< Green, GreenTag() >
        >
    {};

    template<typename Expr>
    void printColor(Expr const & expr)
    {
        int i = 0; // dummy state and data parameter, not used
        std::cout << RGB()(expr, i, i) << std::endl;
    }

    int main()
    {
        printColor(RedT() + GreenT());
        printColor(RedT() + GreenT() + BlueT());
        printColor(RedT() + (GreenT() + BlueT()));

        return 0;
    }

#### TArray: A Simple Linear Algebra Library

This example constructs a mini-library for linear algebra, using expression templates to eliminate the need for temporaries when adding arrays of numbers. It duplicates the TArray example from PETE.

    ///////////////////////////////////////////////////////////////////////////////
    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This example constructs a mini-library for linear algebra, using
    // expression templates to eliminate the need for temporaries when
    // adding arrays of numbers. It duplicates the TArray example from
    // PETE (http://www.codesourcery.com/pooma/download.html)

    #include <iostream>
    #include <boost/mpl/int.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    using proto::_;

    // This grammar describes which TArray expressions
    // are allowed; namely, int and array terminals
    // plus, minus, multiplies and divides of TArray expressions.
    struct TArrayGrammar
      : proto::or_<
            proto::terminal< int >
          , proto::terminal< int[3] >
          , proto::plus< TArrayGrammar, TArrayGrammar >
          , proto::minus< TArrayGrammar, TArrayGrammar >
          , proto::multiplies< TArrayGrammar, TArrayGrammar >
          , proto::divides< TArrayGrammar, TArrayGrammar >
        >
    {};

    template<typename Expr>
    struct TArrayExpr;

    // Tell proto that in the TArrayDomain, all
    // expressions should be wrapped in TArrayExpr<> and
    // must conform to the TArrayGrammar
    struct TArrayDomain
      : proto::domain<proto::generator<TArrayExpr>, TArrayGrammar>
    {};

    // Here is an evaluation context that indexes into a TArray
    // expression, and combines the result.
    struct TArraySubscriptCtx
      : proto::callable_context< TArraySubscriptCtx const >
    {
        typedef int result_type;

        TArraySubscriptCtx(std::ptrdiff_t i)
          : i_(i)
        {}

        // Index array terminals with our subscript. Everything
        // else will be handled by the default evaluation context.
        int operator ()(proto::tag::terminal, int const (&data)[3]) const
        {
            return data[this->i_];
        }

        std::ptrdiff_t i_;
    };

    // Here is an evaluation context that prints a TArray expression.
    struct TArrayPrintCtx
      : proto::callable_context< TArrayPrintCtx const >
    {
        typedef std::ostream &result_type;

        TArrayPrintCtx() {}

        std::ostream &operator ()(proto::tag::terminal, int i) const
        {
            return std::cout << i;
        }

        std::ostream &operator ()(proto::tag::terminal, int const (&arr)[3]) const
        {
            return std::cout << '{' << arr[0] << ", " << arr[1] << ", " << arr[2] << '}';
        }

        template<typename L, typename R>
        std::ostream &operator ()(proto::tag::plus, L const &l, R const &r) const
        {
            return std::cout << '(' << l << " + " << r << ')';
        }

        template<typename L, typename R>
        std::ostream &operator ()(proto::tag::minus, L const &l, R const &r) const
        {
            return std::cout << '(' << l << " - " << r << ')';
        }

        template<typename L, typename R>
        std::ostream &operator ()(proto::tag::multiplies, L const &l, R const &r) const
        {
            return std::cout << l << " * " << r;
        }

        template<typename L, typename R>
        std::ostream &operator ()(proto::tag::divides, L const &l, R const &r) const
        {
            return std::cout << l << " / " << r;
        }
    };

    // Here is the domain-specific expression wrapper, which overrides
    // operator [] to evaluate the expression using the TArraySubscriptCtx.
    template<typename Expr>
    struct TArrayExpr
      : proto::extends<Expr, TArrayExpr<Expr>, TArrayDomain>
    {
        typedef proto::extends<Expr, TArrayExpr<Expr>, TArrayDomain> base_type;

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

        // Use the TArraySubscriptCtx to implement subscripting
        // of a TArray expression tree.
        int operator []( std::ptrdiff_t i ) const
        {
            TArraySubscriptCtx const ctx(i);
            return proto::eval(*this, ctx);
        }

        // Use the TArrayPrintCtx to display a TArray expression tree.
        friend std::ostream &operator <<(std::ostream &sout, TArrayExpr<Expr> const &expr)
        {
            TArrayPrintCtx const ctx;
            return proto::eval(expr, ctx);
        }
    };

    // Here is our TArray terminal, implemented in terms of TArrayExpr
    // It is basically just an array of 3 integers.
    struct TArray
      : TArrayExpr< proto::terminal< int[3] >::type >
    {
        explicit TArray( int i = 0, int j = 0, int k = 0 )
        {
            (*this)[0] = i;
            (*this)[1] = j;
            (*this)[2] = k;
        }

        // Here we override operator [] to give read/write access to
        // the elements of the array. (We could use the TArrayExpr
        // operator [] if we made the subscript context smarter about
        // returning non-const reference when appropriate.)
        int &operator [](std::ptrdiff_t i)
        {
            return proto::value(*this)[i];
        }

        int const &operator [](std::ptrdiff_t i) const
        {
            return proto::value(*this)[i];
        }

        // Here we define a operator = for TArray terminals that
        // takes a TArray expression.
        template< typename Expr >
        TArray &operator =(Expr const & expr)
        {
            // proto::as_expr<TArrayDomain>(expr) is the same as
            // expr unless expr is an integer, in which case it
            // is made into a TArrayExpr terminal first.
            return this->assign(proto::as_expr<TArrayDomain>(expr));
        }

        template< typename Expr >
        TArray &printAssign(Expr const & expr)
        {
            *this = expr;
            std::cout << *this << " = " << expr << std::endl;
            return *this;
        }

    private:
        template< typename Expr >
        TArray &assign(Expr const & expr)
        {
            // expr[i] here uses TArraySubscriptCtx under the covers.
            (*this)[0] = expr[0];
            (*this)[1] = expr[1];
            (*this)[2] = expr[2];
            return *this;
        }
    };

    int main()
    {
        TArray a(3,1,2);

        TArray b;

        std::cout << a << std::endl;
        std::cout << b << std::endl;

        b[0] = 7; b[1] = 33; b[2] = -99;

        TArray c(a);

        std::cout << c << std::endl;

        a = 0;

        std::cout << a << std::endl;
        std::cout << b << std::endl;
        std::cout << c << std::endl;

        a = b + c;

        std::cout << a << std::endl;

        a.printAssign(b+c*(b + 3*c));

        return 0;
    }

#### Vec3: Computing With Transforms and Contexts

This is a simple example using `proto::extends<>` to extend a terminal type with additional behaviors, and using custom contexts and `proto::eval()` for evaluating expressions. It is a port of the Vec3 example from PETE.

    ///////////////////////////////////////////////////////////////////////////////
    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is a simple example using proto::extends to extend a terminal type with
    // additional behaviors, and using custom contexts and proto::eval for
    // evaluating expressions. It is a port of the Vec3 example
    // from PETE (http://www.codesourcery.com/pooma/download.html).

    #include <iostream>
    #include <functional>
    #include <boost/assert.hpp>
    #include <boost/mpl/int.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    #include <boost/proto/proto_typeof.hpp>
    #include <boost/proto/transform.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    using proto::_;

    // Here is an evaluation context that indexes into a Vec3
    // expression, and combines the result.
    struct Vec3SubscriptCtx
      : proto::callable_context< Vec3SubscriptCtx const >
    {
        typedef int result_type;

        Vec3SubscriptCtx(int i)
          : i_(i)
        {}

        // Index array terminals with our subscript. Everything
        // else will be handled by the default evaluation context.
        int operator ()(proto::tag::terminal, int const (&arr)[3]) const
        {
            return arr[this->i_];
        }

        int i_;
    };

    // Here is an evaluation context that counts the number
    // of Vec3 terminals in an expression.
    struct CountLeavesCtx
      : proto::callable_context< CountLeavesCtx, proto::null_context >
    {
        CountLeavesCtx()
          : count(0)
          {}

          typedef void result_type;

          void operator ()(proto::tag::terminal, int const(&)[3])
          {
              ++this->count;
          }

          int count;
    };

    struct iplus : std::plus<int>, proto::callable {};

    // Here is a transform that does the same thing as the above context.
    // It demonstrates the use of the std::plus<> function object
    // with the fold transform. With minor modifications, this
    // transform could be used to calculate the leaf count at compile
    // time, rather than at runtime.
    struct CountLeaves
      : proto::or_<
            // match a Vec3 terminal, return 1
            proto::when<proto::terminal<int[3]>, mpl::int_<1>() >
            // match a terminal, return int() (which is 0)
          , proto::when<proto::terminal<_>, int() >
            // fold everything else, using std::plus<> to add
            // the leaf count of each child to the accumulated state.
          , proto::otherwise< proto::fold<_, int(), iplus(CountLeaves, proto::_state) > >
        >
    {};

    // Here is the Vec3 struct, which is a vector of 3 integers.
    struct Vec3
      : proto::extends<proto::terminal<int[3]>::type, Vec3>
    {
        explicit Vec3(int i=0, int j=0, int k=0)
        {
            (*this)[0] = i;
            (*this)[1] = j;
            (*this)[2] = k;
        }

        int &operator [](int i)
        {
            return proto::value(*this)[i];
        }

        int const &operator [](int i) const
        {
            return proto::value(*this)[i];
        }

        // Here we define a operator = for Vec3 terminals that
        // takes a Vec3 expression.
        template< typename Expr >
        Vec3 &operator =(Expr const & expr)
        {
            typedef Vec3SubscriptCtx const CVec3SubscriptCtx;
            (*this)[0] = proto::eval(proto::as_expr(expr), CVec3SubscriptCtx(0));
            (*this)[1] = proto::eval(proto::as_expr(expr), CVec3SubscriptCtx(1));
            (*this)[2] = proto::eval(proto::as_expr(expr), CVec3SubscriptCtx(2));
            return *this;
        }

        void print() const
        {
            std::cout << '{' << (*this)[0]
                      << ", " << (*this)[1]
                      << ", " << (*this)[2]
                      << '}' << std::endl;
        }
    };

    // The count_leaves() function uses the CountLeaves transform and
    // to count the number of leaves in an expression.
    template<typename Expr>
    int count_leaves(Expr const &expr)
    {
        // Count the number of Vec3 terminals using the
        // CountLeavesCtx evaluation context.
        CountLeavesCtx ctx;
        proto::eval(expr, ctx);

        // This is another way to count the leaves using a transform.
        int i = 0;
        BOOST_ASSERT( CountLeaves()(expr, i, i) == ctx.count );

        return ctx.count;
    }

    int main()
    {
        Vec3 a, b, c;

        c = 4;

        b[0] = -1;
        b[1] = -2;
        b[2] = -3;

        a = b + c;

        a.print();

        Vec3 d;
        BOOST_PROTO_AUTO(expr1, b + c);
        d = expr1;
        d.print();

        int num = count_leaves(expr1);
        std::cout << num << std::endl;

        BOOST_PROTO_AUTO(expr2, b + 3 * c);
        num = count_leaves(expr2);
        std::cout << num << std::endl;

        BOOST_PROTO_AUTO(expr3, b + c * d);
        num = count_leaves(expr3);
        std::cout << num << std::endl;

        return 0;
    }

#### Vector: Adapting a Non-Proto Terminal Type

This is an example of using `BOOST_PROTO_DEFINE_OPERATORS()` to Protofy expressions using `std::vector<>`, a non-Proto type. It is a port of the Vector example from PETE.

    ///////////////////////////////////////////////////////////////////////////////
    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is an example of using BOOST_PROTO_DEFINE_OPERATORS to Protofy
    // expressions using std::vector<>, a non-proto type. It is a port of the
    // Vector example from PETE (http://www.codesourcery.com/pooma/download.html).

    #include <vector>
    #include <iostream>
    #include <stdexcept>
    #include <boost/mpl/bool.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/debug.hpp>
    #include <boost/proto/context.hpp>
    #include <boost/utility/enable_if.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    using proto::_;

    template<typename Expr>
    struct VectorExpr;

    // Here is an evaluation context that indexes into a std::vector
    // expression and combines the result.
    struct VectorSubscriptCtx
    {
        VectorSubscriptCtx(std::size_t i)
          : i_(i)
        {}

        // Unless this is a vector terminal, use the
        // default evaluation context
        template<typename Expr, typename EnableIf = void>
        struct eval
          : proto::default_eval<Expr, VectorSubscriptCtx const>
        {};

        // Index vector terminals with our subscript.
        template<typename Expr>
        struct eval<
            Expr
          , typename boost::enable_if<
                proto::matches<Expr, proto::terminal<std::vector<_, _> > >
            >::type
        >
        {
            typedef typename proto::result_of::value<Expr>::type::value_type result_type;

            result_type operator ()(Expr &expr, VectorSubscriptCtx const &ctx) const
            {
                return proto::value(expr)[ctx.i_];
            }
        };

        std::size_t i_;
    };

    // Here is an evaluation context that verifies that all the
    // vectors in an expression have the same size.
    struct VectorSizeCtx
    {
        VectorSizeCtx(std::size_t size)
          : size_(size)
        {}

        // Unless this is a vector terminal, use the
        // null evaluation context
        template<typename Expr, typename EnableIf = void>
        struct eval
          : proto::null_eval<Expr, VectorSizeCtx const>
        {};

        // Index array terminals with our subscript. Everything
        // else will be handled by the default evaluation context.
        template<typename Expr>
        struct eval<
            Expr
          , typename boost::enable_if<
                proto::matches<Expr, proto::terminal<std::vector<_, _> > >
            >::type
        >
        {
            typedef void result_type;

            result_type operator ()(Expr &expr, VectorSizeCtx const &ctx) const
            {
                if(ctx.size_ != proto::value(expr).size())
                {
                    throw std::runtime_error("LHS and RHS are not compatible");
                }
            }
        };

        std::size_t size_;
    };

    // A grammar which matches all the assignment operators,
    // so we can easily disable them.
    struct AssignOps
      : proto::switch_<struct AssignOpsCases>
    {};

    // Here are the cases used by the switch_ above.
    struct AssignOpsCases
    {
        template<typename Tag, int D = 0> struct case_  : proto::not_<_> {};

        template<int D> struct case_< proto::tag::plus_assign, D >         : _ {};
        template<int D> struct case_< proto::tag::minus_assign, D >        : _ {};
        template<int D> struct case_< proto::tag::multiplies_assign, D >   : _ {};
        template<int D> struct case_< proto::tag::divides_assign, D >      : _ {};
        template<int D> struct case_< proto::tag::modulus_assign, D >      : _ {};
        template<int D> struct case_< proto::tag::shift_left_assign, D >   : _ {};
        template<int D> struct case_< proto::tag::shift_right_assign, D >  : _ {};
        template<int D> struct case_< proto::tag::bitwise_and_assign, D >  : _ {};
        template<int D> struct case_< proto::tag::bitwise_or_assign, D >   : _ {};
        template<int D> struct case_< proto::tag::bitwise_xor_assign, D >  : _ {};
    };

    // A vector grammar is a terminal or some op that is not an
    // assignment op. (Assignment will be handled specially.)
    struct VectorGrammar
      : proto::or_<
            proto::terminal<_>
          , proto::and_<proto::nary_expr<_, proto::vararg<VectorGrammar> >, proto::not_<AssignOps> >
        >
    {};

    // Expressions in the vector domain will be wrapped in VectorExpr<>
    // and must conform to the VectorGrammar
    struct VectorDomain
      : proto::domain<proto::generator<VectorExpr>, VectorGrammar>
    {};

    // Here is VectorExpr, which extends a proto expr type by
    // giving it an operator [] which uses the VectorSubscriptCtx
    // to evaluate an expression with a given index.
    template<typename Expr>
    struct VectorExpr
      : proto::extends<Expr, VectorExpr<Expr>, VectorDomain>
    {
        explicit VectorExpr(Expr const &expr)
          : proto::extends<Expr, VectorExpr<Expr>, VectorDomain>(expr)
        {}

        // Use the VectorSubscriptCtx to implement subscripting
        // of a Vector expression tree.
        typename proto::result_of::eval<Expr const, VectorSubscriptCtx const>::type
        operator []( std::size_t i ) const
        {
            VectorSubscriptCtx const ctx(i);
            return proto::eval(*this, ctx);
        }
    };

    // Define a trait type for detecting vector terminals, to
    // be used by the BOOST_PROTO_DEFINE_OPERATORS macro below.
    template<typename T>
    struct IsVector
      : mpl::false_
    {};

    template<typename T, typename A>
    struct IsVector<std::vector<T, A> >
      : mpl::true_
    {};

    namespace VectorOps
    {
        // This defines all the overloads to make expressions involving
        // std::vector to build expression templates.
        BOOST_PROTO_DEFINE_OPERATORS(IsVector, VectorDomain)

        typedef VectorSubscriptCtx const CVectorSubscriptCtx;

        // Assign to a vector from some expression.
        template<typename T, typename A, typename Expr>
        std::vector<T, A> &assign(std::vector<T, A> &arr, Expr const &expr)
        {
            VectorSizeCtx const size(arr.size());
            proto::eval(proto::as_expr<VectorDomain>(expr), size); // will throw if the sizes don't match
            for(std::size_t i = 0; i < arr.size(); ++i)
            {
                arr[i] = proto::as_expr<VectorDomain>(expr)[i];
            }
            return arr;
        }

        // Add-assign to a vector from some expression.
        template<typename T, typename A, typename Expr>
        std::vector<T, A> &operator +=(std::vector<T, A> &arr, Expr const &expr)
        {
            VectorSizeCtx const size(arr.size());
            proto::eval(proto::as_expr<VectorDomain>(expr), size); // will throw if the sizes don't match
            for(std::size_t i = 0; i < arr.size(); ++i)
            {
                arr[i] += proto::as_expr<VectorDomain>(expr)[i];
            }
            return arr;
        }
    }

    int main()
    {
        using namespace VectorOps;

        int i;
        const int n = 10;
        std::vector<int> a,b,c,d;
        std::vector<double> e(n);

        for (i = 0; i < n; ++i)
        {
            a.push_back(i);
            b.push_back(2*i);
            c.push_back(3*i);
            d.push_back(i);
        }

        VectorOps::assign(b, 2);
        VectorOps::assign(d, a + b * c);
        a += if_else(d < 30, b, c);

        VectorOps::assign(e, c);
        e += e - 4 / (c + 1);

        for (i = 0; i < n; ++i)
        {
            std::cout
                << " a(" << i << ") = " << a[i]
                << " b(" << i << ") = " << b[i]
                << " c(" << i << ") = " << c[i]
                << " d(" << i << ") = " << d[i]
                << " e(" << i << ") = " << e[i]
                << std::endl;
        }
    }

#### Mixed: Adapting Several Non-Proto Terminal Types

This is an example of using `BOOST_PROTO_DEFINE_OPERATORS()` to Protofy expressions using `std::vector<>` and `std::list<>`, non-Proto types. It is a port of the Mixed example from PETE.

    ///////////////////////////////////////////////////////////////////////////////
    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is an example of using BOOST_PROTO_DEFINE_OPERATORS to Protofy
    // expressions using std::vector<> and std::list, non-proto types. It is a port
    // of the Mixed example from PETE.
    // (http://www.codesourcery.com/pooma/download.html).

    #include <list>
    #include <cmath>
    #include <vector>
    #include <complex>
    #include <iostream>
    #include <stdexcept>
    #include <boost/proto/core.hpp>
    #include <boost/proto/debug.hpp>
    #include <boost/proto/context.hpp>
    #include <boost/proto/transform.hpp>
    #include <boost/utility/enable_if.hpp>
    #include <boost/typeof/std/list.hpp>
    #include <boost/typeof/std/vector.hpp>
    #include <boost/typeof/std/complex.hpp>
    #include <boost/type_traits/remove_reference.hpp>
    namespace proto = boost::proto;
    namespace mpl = boost::mpl;
    using proto::_;

    template<typename Expr>
    struct MixedExpr;

    template<typename Iter>
    struct iterator_wrapper
    {
        typedef Iter iterator;

        explicit iterator_wrapper(Iter iter)
          : it(iter)
        {}

        mutable Iter it;
    };

    struct begin : proto::callable
    {
        template<class Sig>
        struct result;

        template<class This, class Cont>
        struct result<This(Cont)>
          : proto::result_of::as_expr<
                iterator_wrapper<typename boost::remove_reference<Cont>::type::const_iterator>
            >
        {};

        template<typename Cont>
        typename result<begin(Cont const &)>::type
        operator ()(Cont const &cont) const
        {
            iterator_wrapper<typename Cont::const_iterator> it(cont.begin());
            return proto::as_expr(it);
        }
    };

    // Here is a grammar that replaces vector and list terminals with their
    // begin iterators
    struct Begin
      : proto::or_<
            proto::when< proto::terminal< std::vector<_, _> >, begin(proto::_value) >
          , proto::when< proto::terminal< std::list<_, _> >, begin(proto::_value) >
          , proto::when< proto::terminal<_> >
          , proto::when< proto::nary_expr<_, proto::vararg<Begin> > >
        >
    {};

    // Here is an evaluation context that dereferences iterator
    // terminals.
    struct DereferenceCtx
    {
        // Unless this is an iterator terminal, use the
        // default evaluation context
        template<typename Expr, typename EnableIf = void>
        struct eval
          : proto::default_eval<Expr, DereferenceCtx const>
        {};

        // Dereference iterator terminals.
        template<typename Expr>
        struct eval<
            Expr
          , typename boost::enable_if<
                proto::matches<Expr, proto::terminal<iterator_wrapper<_> > >
            >::type
        >
        {
            typedef typename proto::result_of::value<Expr>::type IteratorWrapper;
            typedef typename IteratorWrapper::iterator iterator;
            typedef typename std::iterator_traits<iterator>::reference result_type;

            result_type operator ()(Expr &expr, DereferenceCtx const &) const
            {
                return *proto::value(expr).it;
            }
        };
    };

    // Here is an evaluation context that increments iterator
    // terminals.
    struct IncrementCtx
    {
        // Unless this is an iterator terminal, use the
        // default evaluation context
        template<typename Expr, typename EnableIf = void>
        struct eval
          : proto::null_eval<Expr, IncrementCtx const>
        {};

        // advance iterator terminals.
        template<typename Expr>
        struct eval<
            Expr
          , typename boost::enable_if<
                proto::matches<Expr, proto::terminal<iterator_wrapper<_> > >
            >::type
        >
        {
            typedef void result_type;

            result_type operator ()(Expr &expr, IncrementCtx const &) const
            {
                ++proto::value(expr).it;
            }
        };
    };

    // A grammar which matches all the assignment operators,
    // so we can easily disable them.
    struct AssignOps
      : proto::switch_<struct AssignOpsCases>
    {};

    // Here are the cases used by the switch_ above.
    struct AssignOpsCases
    {
        template<typename Tag, int D = 0> struct case_  : proto::not_<_> {};

        template<int D> struct case_< proto::tag::plus_assign, D >         : _ {};
        template<int D> struct case_< proto::tag::minus_assign, D >        : _ {};
        template<int D> struct case_< proto::tag::multiplies_assign, D >   : _ {};
        template<int D> struct case_< proto::tag::divides_assign, D >      : _ {};
        template<int D> struct case_< proto::tag::modulus_assign, D >      : _ {};
        template<int D> struct case_< proto::tag::shift_left_assign, D >   : _ {};
        template<int D> struct case_< proto::tag::shift_right_assign, D >  : _ {};
        template<int D> struct case_< proto::tag::bitwise_and_assign, D >  : _ {};
        template<int D> struct case_< proto::tag::bitwise_or_assign, D >   : _ {};
        template<int D> struct case_< proto::tag::bitwise_xor_assign, D >  : _ {};
    };

    // An expression conforms to the MixedGrammar if it is a terminal or some
    // op that is not an assignment op. (Assignment will be handled specially.)
    struct MixedGrammar
      : proto::or_<
            proto::terminal<_>
          , proto::and_<
                proto::nary_expr<_, proto::vararg<MixedGrammar> >
              , proto::not_<AssignOps>
            >
        >
    {};

    // Expressions in the MixedDomain will be wrapped in MixedExpr<>
    // and must conform to the MixedGrammar
    struct MixedDomain
      : proto::domain<proto::generator<MixedExpr>, MixedGrammar>
    {};

    // Here is MixedExpr, a wrapper for expression types in the MixedDomain.
    template<typename Expr>
    struct MixedExpr
      : proto::extends<Expr, MixedExpr<Expr>, MixedDomain>
    {
        explicit MixedExpr(Expr const &expr)
          : MixedExpr::proto_extends(expr)
        {}
    private:
        // hide this:
        using proto::extends<Expr, MixedExpr<Expr>, MixedDomain>::operator [];
    };

    // Define a trait type for detecting vector and list terminals, to
    // be used by the BOOST_PROTO_DEFINE_OPERATORS macro below.
    template<typename T>
    struct IsMixed
      : mpl::false_
    {};

    template<typename T, typename A>
    struct IsMixed<std::list<T, A> >
      : mpl::true_
    {};

    template<typename T, typename A>
    struct IsMixed<std::vector<T, A> >
      : mpl::true_
    {};

    namespace MixedOps
    {
        // This defines all the overloads to make expressions involving
        // std::vector to build expression templates.
        BOOST_PROTO_DEFINE_OPERATORS(IsMixed, MixedDomain)

        struct assign_op
        {
            template<typename T, typename U>
            void operator ()(T &t, U const &u) const
            {
                t = u;
            }
        };

        struct plus_assign_op
        {
            template<typename T, typename U>
            void operator ()(T &t, U const &u) const
            {
                t += u;
            }
        };

        struct minus_assign_op
        {
            template<typename T, typename U>
            void operator ()(T &t, U const &u) const
            {
                t -= u;
            }
        };

        struct sin_
        {
            template<typename Sig>
            struct result;

            template<typename This, typename Arg>
            struct result<This(Arg)>
              : boost::remove_const<typename boost::remove_reference<Arg>::type>
            {};

            template<typename Arg>
            Arg operator ()(Arg const &a) const
            {
                return std::sin(a);
            }
        };

        template<typename A>
        typename proto::result_of::make_expr<
            proto::tag::function
          , MixedDomain
          , sin_ const
          , A const &
        >::type sin(A const &a)
        {
            return proto::make_expr<proto::tag::function, MixedDomain>(sin_(), boost::ref(a));
        }

        template<typename FwdIter, typename Expr, typename Op>
        void evaluate(FwdIter begin, FwdIter end, Expr const &expr, Op op)
        {
            IncrementCtx const inc = {};
            DereferenceCtx const deref = {};
            typename boost::result_of<Begin(Expr const &)>::type expr2 = Begin()(expr);
            for(; begin != end; ++begin)
            {
                op(*begin, proto::eval(expr2, deref));
                proto::eval(expr2, inc);
            }
        }

        // Add-assign to a vector from some expression.
        template<typename T, typename A, typename Expr>
        std::vector<T, A> &assign(std::vector<T, A> &arr, Expr const &expr)
        {
            evaluate(arr.begin(), arr.end(), proto::as_expr<MixedDomain>(expr), assign_op());
            return arr;
        }

        // Add-assign to a list from some expression.
        template<typename T, typename A, typename Expr>
        std::list<T, A> &assign(std::list<T, A> &arr, Expr const &expr)
        {
            evaluate(arr.begin(), arr.end(), proto::as_expr<MixedDomain>(expr), assign_op());
            return arr;
        }

        // Add-assign to a vector from some expression.
        template<typename T, typename A, typename Expr>
        std::vector<T, A> &operator +=(std::vector<T, A> &arr, Expr const &expr)
        {
            evaluate(arr.begin(), arr.end(), proto::as_expr<MixedDomain>(expr), plus_assign_op());
            return arr;
        }

        // Add-assign to a list from some expression.
        template<typename T, typename A, typename Expr>
        std::list<T, A> &operator +=(std::list<T, A> &arr, Expr const &expr)
        {
            evaluate(arr.begin(), arr.end(), proto::as_expr<MixedDomain>(expr), plus_assign_op());
            return arr;
        }

        // Minus-assign to a vector from some expression.
        template<typename T, typename A, typename Expr>
        std::vector<T, A> &operator -=(std::vector<T, A> &arr, Expr const &expr)
        {
            evaluate(arr.begin(), arr.end(), proto::as_expr<MixedDomain>(expr), minus_assign_op());
            return arr;
        }

        // Minus-assign to a list from some expression.
        template<typename T, typename A, typename Expr>
        std::list<T, A> &operator -=(std::list<T, A> &arr, Expr const &expr)
        {
            evaluate(arr.begin(), arr.end(), proto::as_expr<MixedDomain>(expr), minus_assign_op());
            return arr;
        }
    }

    int main()
    {
        using namespace MixedOps;

        int n = 10;
        std::vector<int> a,b,c,d;
        std::list<double> e;
        std::list<std::complex<double> > f;

        int i;
        for(i = 0;i < n; ++i)
        {
            a.push_back(i);
            b.push_back(2*i);
            c.push_back(3*i);
            d.push_back(i);
            e.push_back(0.0);
            f.push_back(std::complex<double>(1.0, 1.0));
        }

        MixedOps::assign(b, 2);
        MixedOps::assign(d, a + b * c);
        a += if_else(d < 30, b, c);

        MixedOps::assign(e, c);
        e += e - 4 / (c + 1);

        f -= sin(0.1 * e * std::complex<double>(0.2, 1.2));

        std::list<double>::const_iterator ei = e.begin();
        std::list<std::complex<double> >::const_iterator fi = f.begin();
        for (i = 0; i < n; ++i)
        {
            std::cout
                << "a(" << i << ") = " << a[i]
                << " b(" << i << ") = " << b[i]
                << " c(" << i << ") = " << c[i]
                << " d(" << i << ") = " << d[i]
                << " e(" << i << ") = " << *ei++
                << " f(" << i << ") = " << *fi++
                << std::endl;
        }
    }

#### Map Assign: An Intermediate Transform

A demonstration of how to implement `map_list_of()` from the Boost.Assign library using Proto. `map_list_assign()` is used to conveniently initialize a `std::map<>`. By using Proto, we can avoid any dynamic allocation while building the intermediate representation.

    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is a port of map_list_of() from the Boost.Assign library.
    // It has the advantage of being more efficient at runtime by not
    // building any temporary container that requires dynamic allocation.

    #include <map>
    #include <string>
    #include <iostream>
    #include <boost/proto/core.hpp>
    #include <boost/proto/transform.hpp>
    #include <boost/type_traits/add_reference.hpp>
    namespace proto = boost::proto;
    using proto::_;

    struct map_list_of_tag
    {};

    // A simple callable function object that inserts a
    // (key,value) pair into a map.
    struct insert
      : proto::callable
    {
        template<typename Sig>
        struct result;

        template<typename This, typename Map, typename Key, typename Value>
        struct result<This(Map, Key, Value)>
          : boost::add_reference<Map>
        {};

        template<typename Map, typename Key, typename Value>
        Map &operator()(Map &map, Key const &key, Value const &value) const
        {
            map.insert(typename Map::value_type(key, value));
            return map;
        }
    };

    // Work-arounds for Microsoft Visual C++ 7.1
    #if BOOST_WORKAROUND(BOOST_MSVC, == 1310)
    #define MapListOf(x) proto::call<MapListOf(x)>
    #define _value(x) call<proto::_value(x)>
    #endif

    // The grammar for valid map-list expressions, and a
    // transform that populates the map.
    struct MapListOf
      : proto::or_<
            proto::when<
                // map_list_of(a,b)
                proto::function<
                    proto::terminal<map_list_of_tag>
                  , proto::terminal<_>
                  , proto::terminal<_>
                >
              , insert(
                    proto::_data
                  , proto::_value(proto::_child1)
                  , proto::_value(proto::_child2)
                )
            >
          , proto::when<
                // map_list_of(a,b)(c,d)...
                proto::function<
                    MapListOf
                  , proto::terminal<_>
                  , proto::terminal<_>
                >
              , insert(
                    MapListOf(proto::_child0)
                  , proto::_value(proto::_child1)
                  , proto::_value(proto::_child2)
                )
            >
        >
    {};

    #if BOOST_WORKAROUND(BOOST_MSVC, == 1310)
    #undef MapListOf
    #undef _value
    #endif

    template<typename Expr>
    struct map_list_of_expr;

    struct map_list_of_dom
      : proto::domain<proto::pod_generator<map_list_of_expr>, MapListOf>
    {};

    // An expression wrapper that provides a conversion to a
    // map that uses the MapListOf
    template<typename Expr>
    struct map_list_of_expr
    {
        BOOST_PROTO_BASIC_EXTENDS(Expr, map_list_of_expr, map_list_of_dom)
        BOOST_PROTO_EXTENDS_FUNCTION()

        template<typename Key, typename Value, typename Cmp, typename Al>
        operator std::map<Key, Value, Cmp, Al> () const
        {
            BOOST_MPL_ASSERT((proto::matches<Expr, MapListOf>));
            std::map<Key, Value, Cmp, Al> map;
            return MapListOf()(*this, 0, map);
        }
    };

    map_list_of_expr<proto::terminal<map_list_of_tag>::type> const map_list_of = {{{}}};

    int main()
    {
        // Initialize a map:
        std::map<std::string, int> op =
            map_list_of
                ("<", 1)
                ("<=",2)
                (">", 3)
                (">=",4)
                ("=", 5)
                ("<>",6)
            ;

        std::cout << "\"<\"  --> " << op["<"] << std::endl;
        std::cout << "\"<=\" --> " << op["<="] << std::endl;
        std::cout << "\">\"  --> " << op[">"] << std::endl;
        std::cout << "\">=\" --> " << op[">="] << std::endl;
        std::cout << "\"=\"  --> " << op["="] << std::endl;
        std::cout << "\"<>\" --> " << op["<>"] << std::endl;

        return 0;
    }

#### Future Group: A More Advanced Transform

An advanced example of a Proto transform that implements Howard Hinnant's design for future groups that block for all or some asynchronous operations to complete and returns their results in a tuple of the appropriate type.

    //  Copyright 2008 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is an example of using Proto transforms to implement
    // Howard Hinnant's future group proposal.

    #include <boost/fusion/include/vector.hpp>
    #include <boost/fusion/include/as_vector.hpp>
    #include <boost/fusion/include/joint_view.hpp>
    #include <boost/fusion/include/single_view.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/transform.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    namespace fusion = boost::fusion;
    using proto::_;

    template<class L,class R>
    struct pick_left
    {
        BOOST_MPL_ASSERT((boost::is_same<L, R>));
        typedef L type;
    };

    // Work-arounds for Microsoft Visual C++ 7.1
    #if BOOST_WORKAROUND(BOOST_MSVC, == 1310)
    #define FutureGroup(x) proto::call<FutureGroup(x)>
    #endif

    // Define the grammar of future group expression, as well as a
    // transform to turn them into a Fusion sequence of the correct
    // type.
    struct FutureGroup
      : proto::or_<
            // terminals become a single-element Fusion sequence
            proto::when<
                proto::terminal<_>
              , fusion::single_view<proto::_value>(proto::_value)
            >
            // (a && b) becomes a concatenation of the sequence
            // from 'a' and the one from 'b':
          , proto::when<
                proto::logical_and<FutureGroup, FutureGroup>
              , fusion::joint_view<
                    boost::add_const<FutureGroup(proto::_left) >
                  , boost::add_const<FutureGroup(proto::_right) >
                >(FutureGroup(proto::_left), FutureGroup(proto::_right))
            >
            // (a || b) becomes the sequence for 'a', so long
            // as it is the same as the sequence for 'b'.
          , proto::when<
                proto::logical_or<FutureGroup, FutureGroup>
              , pick_left<
                    FutureGroup(proto::_left)
                  , FutureGroup(proto::_right)
                >(FutureGroup(proto::_left))
            >
        >
    {};

    #if BOOST_WORKAROUND(BOOST_MSVC, == 1310)
    #undef FutureGroup
    #endif

    template<class E>
    struct future_expr;

    struct future_dom
      : proto::domain<proto::generator<future_expr>, FutureGroup>
    {};

    // Expressions in the future group domain have a .get()
    // member function that (ostensibly) blocks for the futures
    // to complete and returns the results in an appropriate
    // tuple.
    template<class E>
    struct future_expr
      : proto::extends<E, future_expr<E>, future_dom>
    {
        explicit future_expr(E const &e)
          : future_expr::proto_extends(e)
        {}

        typename fusion::result_of::as_vector<
            typename boost::result_of<FutureGroup(E)>::type
        >::type
        get() const
        {
            return fusion::as_vector(FutureGroup()(*this));
        }
    };

    // The future<> type has an even simpler .get()
    // member function.
    template<class T>
    struct future
      : future_expr<typename proto::terminal<T>::type>
    {
        future(T const &t = T())
          : future::proto_derived_expr(future::proto_base_expr::make(t))
        {}

        T get() const
        {
            return proto::value(*this);
        }
    };

    // TEST CASES
    struct A {};
    struct B {};
    struct C {};

    int main()
    {
        using fusion::vector;
        future<A> a;
        future<B> b;
        future<C> c;
        future<vector<A,B> > ab;

        // Verify that various future groups have the
        // correct return types.
        A                       t0 = a.get();
        vector<A, B, C>         t1 = (a && b && c).get();
        vector<A, C>            t2 = ((a || a) && c).get();
        vector<A, B, C>         t3 = ((a && b || a && b) && c).get();
        vector<vector<A, B>, C> t4 = ((ab || ab) && c).get();

        return 0;
    }

#### Lambda: A Simple Lambda Library with Proto

This is an advanced example that shows how to implement a simple lambda EDSL with Proto, like the Boost.Lambda_library. It uses contexts, transforms and expression extension.

    ///////////////////////////////////////////////////////////////////////////////
    // Copyright 2008 Eric Niebler. Distributed under the Boost
    // Software License, Version 1.0. (See accompanying file
    // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This example builds a simple but functional lambda library using Proto.

    #include <iostream>
    #include <algorithm>
    #include <boost/mpl/int.hpp>
    #include <boost/mpl/min_max.hpp>
    #include <boost/mpl/eval_if.hpp>
    #include <boost/mpl/identity.hpp>
    #include <boost/mpl/next_prior.hpp>
    #include <boost/fusion/tuple.hpp>
    #include <boost/typeof/typeof.hpp>
    #include <boost/typeof/std/ostream.hpp>
    #include <boost/typeof/std/iostream.hpp>
    #include <boost/proto/core.hpp>
    #include <boost/proto/context.hpp>
    #include <boost/proto/transform.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    namespace fusion = boost::fusion;
    using proto::_;

    // Forward declaration of the lambda expression wrapper
    template<typename T>
    struct lambda;

    struct lambda_domain
      : proto::domain<proto::pod_generator<lambda> >
    {};

    template<typename I>
    struct placeholder
    {
        typedef I arity;
    };

    template<typename T>
    struct placeholder_arity
    {
        typedef typename T::arity type;
    };

    // The lambda grammar, with the transforms for calculating the max arity
    struct lambda_arity
      : proto::or_<
            proto::when<
                proto::terminal< placeholder<_> >
              , mpl::next<placeholder_arity<proto::_value> >()
            >
          , proto::when< proto::terminal<_>
              , mpl::int_<0>()
            >
          , proto::when<
                proto::nary_expr<_, proto::vararg<_> >
              , proto::fold<_, mpl::int_<0>(), mpl::max<lambda_arity, proto::_state>()>
            >
        >
    {};

    // The lambda context is the same as the default context
    // with the addition of special handling for lambda placeholders
    template<typename Tuple>
    struct lambda_context
      : proto::callable_context<lambda_context<Tuple> const>
    {
        lambda_context(Tuple const &args)
          : args_(args)
        {}

        template<typename Sig>
        struct result;

        template<typename This, typename I>
        struct result<This(proto::tag::terminal, placeholder<I> const &)>
          : fusion::result_of::at<Tuple, I>
        {};

        template<typename I>
        typename fusion::result_of::at<Tuple, I>::type
        operator ()(proto::tag::terminal, placeholder<I> const &) const
        {
            return fusion::at<I>(this->args_);
        }

        Tuple args_;
    };

    // The lambda<> expression wrapper makes expressions polymorphic
    // function objects
    template<typename T>
    struct lambda
    {
        BOOST_PROTO_BASIC_EXTENDS(T, lambda<T>, lambda_domain)
        BOOST_PROTO_EXTENDS_ASSIGN()
        BOOST_PROTO_EXTENDS_SUBSCRIPT()

        // Calculate the arity of this lambda expression
        static int const arity = boost::result_of<lambda_arity(T)>::type::value;

        template<typename Sig>
        struct result;

        // Define nested result<> specializations to calculate the return
        // type of this lambda expression. But be careful not to evaluate
        // the return type of the nullary function unless we have a nullary
        // lambda!
        template<typename This>
        struct result<This()>
          : mpl::eval_if_c<
                0 == arity
              , proto::result_of::eval<T const, lambda_context<fusion::tuple<> > >
              , mpl::identity<void>
            >
        {};

        template<typename This, typename A0>
        struct result<This(A0)>
          : proto::result_of::eval<T const, lambda_context<fusion::tuple<A0> > >
        {};

        template<typename This, typename A0, typename A1>
        struct result<This(A0, A1)>
          : proto::result_of::eval<T const, lambda_context<fusion::tuple<A0, A1> > >
        {};

        // Define our operator () that evaluates the lambda expression.
        typename result<lambda()>::type
        operator ()() const
        {
            fusion::tuple<> args;
            lambda_context<fusion::tuple<> > ctx(args);
            return proto::eval(*this, ctx);
        }

        template<typename A0>
        typename result<lambda(A0 const &)>::type
        operator ()(A0 const &a0) const
        {
            fusion::tuple<A0 const &> args(a0);
            lambda_context<fusion::tuple<A0 const &> > ctx(args);
            return proto::eval(*this, ctx);
        }

        template<typename A0, typename A1>
        typename result<lambda(A0 const &, A1 const &)>::type
        operator ()(A0 const &a0, A1 const &a1) const
        {
            fusion::tuple<A0 const &, A1 const &> args(a0, a1);
            lambda_context<fusion::tuple<A0 const &, A1 const &> > ctx(args);
            return proto::eval(*this, ctx);
        }
    };

    // Define some lambda placeholders
    lambda<proto::terminal<placeholder<mpl::int_<0> > >::type> const _1 = {{}};
    lambda<proto::terminal<placeholder<mpl::int_<1> > >::type> const _2 = {{}};

    template<typename T>
    lambda<typename proto::terminal<T>::type> const val(T const &t)
    {
        lambda<typename proto::terminal<T>::type> that = {{t}};
        return that;
    }

    template<typename T>
    lambda<typename proto::terminal<T &>::type> const var(T &t)
    {
        lambda<typename proto::terminal<T &>::type> that = {{t}};
        return that;
    }

    template<typename T>
    struct construct_helper
    {
        typedef T result_type; // for TR1 result_of

        T operator()() const
        { return T(); }

        // Generate BOOST_PROTO_MAX_ARITY overloads of the
        // following function call operator.
    #define BOOST_PROTO_LOCAL_MACRO(N, typename_A, A_const_ref, A_const_ref_a, a)\
        template<typename_A(N)>                                       \
        T operator()(A_const_ref_a(N)) const                          \
        { return T(a(N)); }
    #define BOOST_PROTO_LOCAL_a BOOST_PROTO_a
    #include BOOST_PROTO_LOCAL_ITERATE()
    };

    // Generate BOOST_PROTO_MAX_ARITY-1 overloads of the
    // following construct() function template.
    #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                                          \
      , lambda_domain                                                 \
      , construct_helper<T>                                           \
      , A_const_ref(N)                                                \
    >::type const                                                     \
    construct(A_const_ref_a(N))                                       \
    {                                                                 \
        return proto::make_expr<                                      \
            proto::tag::function                                      \
          , lambda_domain                                             \
        >(                                                            \
            construct_helper<T>()                                     \
          , ref_a(N)                                                  \
        );                                                            \
    }
    BOOST_PROTO_REPEAT_FROM_TO(1, BOOST_PROTO_MAX_ARITY, M0)
    #undef M0

    struct S
    {
        S() {}
        S(int i, char c)
        {
            std::cout << "S(" << i << "," << c << ")\n";
        }
    };

    int main()
    {
        // Create some lambda objects and immediately
        // invoke them by applying their operator():
        int i = ( (_1 + 2) / 4 )(42);
        std::cout << i << std::endl; // prints 11

        int j = ( (-(_1 + 2)) / 4 )(42);
        std::cout << j << std::endl; // prints -11

        double d = ( (4 - _2) * 3 )(42, 3.14);
        std::cout << d << std::endl; // prints 2.58

        // check non-const ref terminals
        (std::cout << _1 << " -- " << _2 << '\n')(42, "Life, the Universe and Everything!");
        // prints "42 -- Life, the Universe and Everything!"

        // "Nullary" lambdas work too
        int k = (val(1) + val(2))();
        std::cout << k << std::endl; // prints 3

        // check array indexing for kicks
        int integers[5] = {0};
        (var(integers)[2] = 2)();
        (var(integers)[_1] = _1)(3);
        std::cout << integers[2] << std::endl; // prints 2
        std::cout << integers[3] << std::endl; // prints 3

        // Now use a lambda with an STL algorithm!
        int rgi[4] = {1,2,3,4};
        char rgc[4] = {'a','b','c','d'};
        S rgs[4];

        std::transform(rgi, rgi+4, rgc, rgs, construct<S>(_1, _2));
        return 0;
    }

#### Checked Calculator: A Simple Example of External Transforms

This is an advanced example that shows how to externally parameterize a grammar's transforms. It defines a calculator EDSL with a grammar that can perform either checked or unchecked arithmetic.

    //  Copyright 2011 Eric Niebler. Distributed under the Boost
    //  Software License, Version 1.0. (See accompanying file
    //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
    //
    // This is an example of how to specify a transform externally so
    // that a single grammar can be used to drive multiple differnt
    // calculations. In particular, it defines a calculator grammar
    // that computes the result of an expression with either checked
    // or non-checked division.

    #include <iostream>
    #include <boost/assert.hpp>
    #include <boost/mpl/int.hpp>
    #include <boost/mpl/next.hpp>
    #include <boost/mpl/min_max.hpp>
    #include <boost/fusion/container/vector.hpp>
    #include <boost/fusion/container/generation/make_vector.hpp>
    #include <boost/proto/proto.hpp>
    namespace mpl = boost::mpl;
    namespace proto = boost::proto;
    namespace fusion = boost::fusion;

    // The argument placeholder type
    template<typename I> struct placeholder : I {};

    // Give each rule in the grammar a "name". This is so that we
    // can easily dispatch on it later.
    struct calc_grammar;
    struct divides_rule : proto::divides<calc_grammar, calc_grammar> {};

    // Use external transforms in calc_gramar
    struct calc_grammar
      : proto::or_<
            proto::when<
                proto::terminal<placeholder<proto::_> >
                , proto::functional::at(proto::_state, proto::_value)
            >
          , proto::when<
                proto::terminal<proto::convertible_to<double> >
              , proto::_value
            >
          , proto::when<
                proto::plus<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
          , proto::when<
                proto::minus<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
          , proto::when<
                proto::multiplies<calc_grammar, calc_grammar>
              , proto::_default<calc_grammar>
            >
            // Note that we don't specify how division nodes are
            // handled here. Proto::external_transform is a placeholder
            // for an actual transform.
          , proto::when<
                divides_rule
              , proto::external_transform
            >
        >
    {};

    template<typename E> struct calc_expr;
    struct calc_domain : proto::domain<proto::generator<calc_expr> > {};

    template<typename E>
    struct calc_expr
      : proto::extends<E, calc_expr<E>, calc_domain>
    {
        calc_expr(E const &e = E()) : calc_expr::proto_extends(e) {}
    };

    calc_expr<proto::terminal<placeholder<mpl::int_<0> > >::type> _1;
    calc_expr<proto::terminal<placeholder<mpl::int_<1> > >::type> _2;

    // Use proto::external_transforms to map from named grammar rules to
    // transforms.
    struct non_checked_division
      : proto::external_transforms<
            proto::when< divides_rule, proto::_default<calc_grammar> >
        >
    {};

    struct division_by_zero : std::exception {};

    struct do_checked_divide
      : proto::callable
    {
        typedef int result_type;
        int operator()(int left, int right) const
        {
            if (right == 0) throw division_by_zero();
            return left / right;
        }
    };

    // Use proto::external_transforms again, this time to map the divides_rule
    // to a transforms that performs checked division.
    struct checked_division
      : proto::external_transforms<
            proto::when<
                divides_rule
              , do_checked_divide(calc_grammar(proto::_left), calc_grammar(proto::_right))
            >
        >
    {};

    int main()
    {
        non_checked_division non_checked;
        int result2 = calc_grammar()(_1 / _2, fusion::make_vector(6, 2), non_checked);
        BOOST_ASSERT(result2 == 3);

        try
        {
            checked_division checked;
            // This should throw
            int result3 = calc_grammar()(_1 / _2, fusion::make_vector(6, 0), checked);
            BOOST_ASSERT(false); // shouldn't get here!
        }
        catch(division_by_zero)
        {
            std::cout << "caught division by zero!\n";
        }
    }

### Background and Resources

Proto was initially developed as part of Boost.Xpressive to simplify the job of transforming an expression template into an executable finite state machine capable of matching a regular expression. Since then, Proto has found application in the redesigned and improved Spirit-2 and the related Karma library. As a result of these efforts, Proto evolved into a generic and abstract grammar and tree transformation framework applicable in a wide variety of EDSL scenarios.

The grammar and tree transformation framework is modeled on Spirit's grammar and semantic action framework. The expression tree data structure is similar to Fusion data structures in many respects, and is interoperable with Fusion's iterators and algorithms.

The syntax for the grammar-matching features of `proto::matches<>` is inspired by MPL's lambda expressions.

The idea for using function types for Proto's composite transforms is inspired by Aleksey Gurtovoy's "round" lambda notation.

##### References

> Ren, D. and Erwig, M. 2006. A generic recursion toolbox for Haskell or: scrap your boilerplate systematically. In Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell (Portland, Oregon, USA, September 17 - 17, 2006). Haskell '06. ACM, New York, NY, 13-24. DOI=http://doi.acm.org/10.1145/1159842.1159845

##### Further Reading

A technical paper about an earlier version of Proto was accepted into the ACM SIGPLAN Symposium on Library-Centric Software Design LCSD'07, and can be found at http://lcsd.cs.tamu.edu/2007/final/1/1_Paper.pdf. The tree transforms described in that paper differ from what exists today.

### Glossary

callable transform

  A transform of the form `R(A0,A1,...)` (i.e., a function type) where `proto::is_callable<R>::value` is `true`. `R` is treated as a polymorphic function object and the arguments are treated as transforms that yield the arguments to the function object.

context

  In Proto, the term context refers to an object that can be passed, along with an expression to evaluate, to the `proto::eval()` function. The context determines how the expression is evaluated. All context structs define a nested `eval<>` template that, when instantiated with a node tag type (e.g., `proto::tag::plus`), is a binary polymorphic function object that accepts an expression of that type and the context object. In this way, contexts associate behaviors with expression nodes.

domain

  In Proto, the term domain refers to a type that associates expressions within that domain with a generator for that domain and optionally a grammar for the domain. Domains are used primarily to imbue expressions within that domain with additional members and to restrict Proto's operator overloads such that expressions not conforming to the domain's grammar are never created. Domains are empty structs that inherit from `proto::domain<>`.

domain-specific language

  A programming language that targets a particular problem space by providing programming idioms, abstractions and constructs that match the constructs within that problem space.

embedded domain-specific language

  A domain-specific language implemented as a library. The language in which the library is written is called the "host" language, and the language implemented by the library is called the "embedded" language.

expression

  In Proto, an expression is a heterogeneous tree where each node is either an instantiation of `boost::proto::expr<>`, `boost::proto::basic_expr<>` or some type that is an extension (via `boost::proto::extends<>` or `BOOST_PROTO_EXTENDS()`) of such an instantiation.

expression template

  A C++ technique using templates and operator overloading to cause expressions to build trees that represent the expression for lazy evaluation later, rather than evaluating the expression eagerly. Some C++ libraries use expression templates to build embedded domain-specific languages.

generator

  In Proto, a generator is a unary polymorphic function object that you specify when defining a domain. After constructing a new expression, Proto passes the expression to your domain's generator for further processing. Often, the generator wraps the expression in an extension wrapper that adds additional members to it.

grammar

  In Proto, a grammar is a type that describes a subset of Proto expression types. Expressions in a domain must conform to that domain's grammar. The `proto::matches<>` metafunction evaluates whether an expression type matches a grammar. Grammars are either primitives such as `proto::_`, composites such as `proto::plus<>`, control structures such as `proto::or_<>`, or some type derived from a grammar.

object transform

  A transform of the form `R(A0,A1,...)` (i.e., a function type) where `proto::is_callable<R>::value` is `false`. `R` is treated as the type of an object to construct and the arguments are treated as transforms that yield the parameters to the constructor.

polymorphic function object

  An instance of a class type with an overloaded function call operator and a nested `result_type` typedef or `result<>` template for calculating the return type of the function call operator.

primitive transform

  A type that defines a kind of polymorphic function object that takes three arguments: expression, state, and data. Primitive transforms can be used to compose callable transforms and object transforms.

sub-domain

  A sub-domain is a domain that declares another domain as its super-domain. Expressions in sub-domains can be combined with expressions in the super-domain, and the resulting expression is in the super-domain.

transform

  Transforms are used to manipulate expression trees. They come in three flavors: primitive transforms, callable transforms, or object transforms. A transform ``T`` can be made into a ternary polymorphic function object with `proto::when<>`, as in `proto::when<proto::_, `T`>`. Such a function object accepts expression, state, and data parameters, and computes a result from them.

[5] It's not always possible to hold something by value. By default, `proto::as_expr()` makes an exception for functions, abstract types, and iostreams (types derived from `std::ios_base`). These objects are held by reference. All others are held by value, even arrays.

[6] This error message was generated with Microsoft Visual C++ 9.0. Different compilers will emit different messages with varying degrees of readability.