Boost C++ Libraries

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 DSEL to square each element ... HOW?
std::transform( data, data + 4, data, _1 * _1 );

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

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

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

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

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

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

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

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

    // This is usually needed because by default, the compiler-
    // generated assignment operator hides extends<>::operator=
    using base_type::operator =;

    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.

Although not strictly necessary in this case, we bring extends<>::operator= into scope with a using declaration. 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 using declaration.

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

BOOST_PROTO_BASIC_EXTENDS(
    expression
  , extension
  , domain
)

BOOST_PROTO_EXTENDS(
    expression
  , extension
  , domain
)

BOOST_PROTO_BASIC_EXTENDS(expression, extension, domain)
BOOST_PROTO_EXTENDS_ASSIGN()
BOOST_PROTO_EXTENDS_SUBSCRIPT()
BOOST_PROTO_EXTENDS_FUNCTION()

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 DSEL to square each element ... WORKS! :-)
std::transform( data, data + 4, data, _1 * _1 );

By default, Proto defines every possible operator overload for Protofied expressions. This makes it simple to bang together a DSEL. 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 DSEL 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.

Imagine your DSEL 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!

When the Output grammar is evaluated against an expression like cout_ << 1 << 2, 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::_ >. Then the second alternate is tried. We match the expression against proto::shift_left< Output, proto::_ >. The expression is a left-shift, so we try the operands. The right operand 2 matches proto::_ trivially. 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.

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.

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Notice the specialization that handles terminals:

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

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

Note

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

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.

In this section we'll see how to use Proto to define a grammar for your DSEL 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 DSEL 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 DSEL. This is easy to express with a grammar, and hard to do with straight operator overloading. Third, using a DSEL 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 a DSEL 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 DSEL 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 DSEL 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 > ));
    // ...
}

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.

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

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

hello, world

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