Boost C++ Libraries Home Libraries People FAQ More

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


PrevUpHomeNext