[/
 / Copyright (c) 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)
 /]

[/============================================================================]
[section:expression_introspection 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.

[/===============================================]
[section:patterns Finding Patterns In Expressions]
[/===============================================]

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

    terminal< std::istream & >::type cin_ = { std::cin };
    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 intput and output
expressions of the form `cin_ >> i` and `cout_ << 1` we do this:

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

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

We've seen the template `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 `shift_right<>` and `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 _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( matches< Expr, Input >::value )
        {
            std::cout << "Input!\n";
        }

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

[pre
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 enable_if< matches< Expr, Input > >::type
    input_output( Expr const & expr )
    {
        std::cout << "Input!\n";
    }

    template< typename Expr >
    typename enable_if< 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 _or_. Here are the correct
`Input` and `Output` grammars:

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

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

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
_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 _or_ is tried first. It will
fail, because the expression `cout_ << 1 << 2` does not match the grammar
`shift_left< terminal< std::ostream & >, _ >`. Then the second
alternate is tried. We match the expression against
`shift_left< Output, _ >`. The expression is a left-shift, so we try
the operands. The right operand `2` matches `_` 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 _or_. We're done -- the grammar matches
successfully.

[endsect]

[/===========================================]
[section 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 _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 a `int const &`.

The table below shows how Proto matches terminals. The simiple 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 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 _exact_ 
template. For instance, `proto::terminal<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 
reference to 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
      : terminal< char const * >
    {};

    typedef terminal< char const (&)[6] >::type char_array;

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

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

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

    typedef terminal<char const (&)[6]>::type char_array;
    typedef terminal<char const *>::type      char_string;

    BOOST_MPL_ASSERT(( matches< char_string, CharString > ));
    BOOST_MPL_ASSERT_NOT(( 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 
`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:
`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
_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
      : terminal< std::complex< _ > >
    {};

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.

[endsect]

[/====================================================]
[section:if_and_not [^if_<>], [^and_<>], and [^not_<>]]
[/====================================================]

We've already seen how to use expression generators like `terminal<>` and
`shift_right<>` as grammars. We've also seen _or_, which we can use to
express a set of alternate grammars. There are a few others of interest; in
particular, _if_, _and_ and _not_.

The _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 _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 _and_ template is like _or_, except that each argument of the _and_ must
match in order for the _and_ to match. As an example, consider the definition
of `CharString` above that uses _exact_. It could have been written without
_exact_ as follows:

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

This says that a `CharString` must be a terminal, /and/ its argument must be
the same as `char const *`. Notice the template argument of _if_:
`is_same< _arg, char const * >()`. This is Proto transform that compares the
argument of a terminal to `char const *`.

The _if_ template has a couple of variants. In additon 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`.

[endsect]

[/==================================]
[section 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
some predefined maximum). How do you write a grammar to match such a node?

For such cases, Proto provides the _vararg_ class template. Its template
argument is a grammar, and the _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 : 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
      : function< FunTag, vararg< terminal< char > > >
    {};

The `FunCall` grammar uses _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
      : or_<
            terminal< _ >
          , nary_expr< _, vararg< Foo > >
        >
    {};

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

[endsect]

[/=============================]
[section Defining DSEL Grammars]
[/=============================]

We've already seen how to use small grammars to answer simple questions about
expression trees. Here's a harder question: ["Does this expression conform to the
grammar of my domain-specific embedded language?] 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 be thinking 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. As we'll see later, 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! We'll see how later.
]

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, multiplaction, division and grouping. If
we were to write the grammar for this DSEL in
[@http://en.wikipedia.org/wiki/Extended_Backus_Naur_Form EBNF], it might look
like this:

[pre
group       ::= '(' expression ')'
factor      ::= double | placeholder1 | placeholder2 | 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
      : terminal< convertible_to< double > >
    {};

    struct Placeholder1
      : terminal< placeholder1 >
    {};

    struct Placeholder2
      : terminal< placeholder2 >
    {};

    struct Terminal
      : 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
      : plus< CalculatorGrammar, CalculatorGrammar >
    {};

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

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

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

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

    struct CalculatorGrammar
      : 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 _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(( matches< Expr, CalculatorGrammar > ));
        // ...
    }

[endsect]

[endsect]
