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

[import ../test/examples.cpp]

[/==========================================================]
[section:expression_transformation Expression Transformation]
[/==========================================================]

Sometimes, rather than immediately executing an expression template, you'd
like to transform it into some other object. Maybe the transformation is simple,
like converting all references into values. Maybe it's complicated, like
transforming an expression template into a finite-state automata for matching a
regular expression. Proto provides a framework for applying tree
transformations and several canned transformations that are generally useful.

[/===============]
[heading Overview]
[/===============]

Defining tree transformations involves defining the grammar for your DSEL
and decorating it with transformations. Each rule in your grammar will
have an associated transform describing how sub-expressions matching that rule
are to be transformed. Just as the grammar is defined recursively, so too
is the tree transformation.

You associate transforms with your grammar rules using _when_. For instance,
you might want to promote all `int` terminals to `long`. You would say 
`when< terminal<int>, terminal<long>::type(_arg) >`. Here, 
`terminal<long>::type(_arg)` is an example of a Proto transform. It says to
create an object of type `terminal<long>::type` and initialize it with the
result of the `_arg` transform. `_arg` is a transform defined by Proto which
essentially calls `proto::arg()` on the current expression.

[note The transform above might look a little strange at first. It appears
to be constructing a temporary object in place. In fact, it is a 
/function type/. Since `terminal<long>::type` and `_arg` are types,
`terminal<long>::type(_arg)` is actually the type of a function that takes 
`_arg` as a parameter and returns `terminal<long>::type`. That is immaterial;
there is no such function in reality. Rather, Proto interprets this function
type as a transform, the effect of which is described above. The resemblance
to an in-place construction of a temporary object is intentional. It is a
concise and natural notation for specifying transforms. Proto transforms use
function types extensively, as we'll see.]

A grammar decorated with transforms is a function object that takes three
parameters:

* `expr`    -- the Proto expression to transform
* `state`   -- the initial state of the transformation
* `visitor` -- any optional mutable state information

Grammars with transforms are proper function objects, so you can use 
`boost::result_of<>` to calculate their return types. So, applying a 
transform typically looks like this:

    // Assuming we have an expression to transform,
    // an initial state, and a visitor ...
    Expr expr;
    State state;
    Visitor visitor;
    
    // ... calculate the result type of applying
    // Grammar's transform ...
    typedef typename
        boost::result_of<Grammar(Expr, State, Visitor)>::type
    result_type;
    
    // ... and apply Grammar's transform:
    result_type result = Grammar()(expr, state, visitor);

[/==========================================]
[section Example: Calculator Arity Transform]
[/==========================================]

Let's have another look at our trusty calculator example. If you recall, the
calculator allows the lazy evaluation of arithmetic expressions, with
placeholders substituted with actual values provided at evaluation time. Valid
expressions are of the form:

    (_1 + 3)
    (_2 - _1) / _2 * 100

... and so on. In the first expression, one argument must be provided before
the expression can be evaluated. In the second, two arguments are needed. We
could say the /arity/ of the first expression is one and of the second is two.
The arity is determined by the highest placeholder in the expression. Our job
will be to write a transform that calculates the arity of any calculator
expression.

[/=========================]
[heading Defining a Grammar]
[/=========================]

First, we must write the grammar for the calculator. It's really very simple.
Calculator expression can be made up of any combination of 5 constituents:

* Placeholder 1
* Placeholder 2
* A literal
* Unary operations
* Binary operations

We can immediately write the calculator grammar as follows:

[CalcGrammar]

We can read this as follows: a calculator expression is either placeholder 1,
placeholder 2, some other terminal, or some unary or binary operator whose
operands are calculator expressions. Recall that `proto::_` is a wildcard which
matches anything. So `terminal< _ >` will match any terminal, and
`unary_expr< _, CalcArity >` will match any unary expression
for which the operand matches CalcArity (the `_` matches any operator
tag).

[/============================]
[heading Writing the Transform]
[/============================]

It's straightforward to describe in words how the arity of an expression should
be calculated. First, we describe the arity of each of the 5 constituents in
the calculator grammar.

[table 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/ ]]
]

The total arity of a calculator expression is found by recursively evaluating
the arity of all of the sub-expressions and taking the maximum.

Let's look at the sub-expression for the placeholder `_1`. It is matched by this
part of our grammar: `terminal< placeholder1 >`. We want to associate this
part of our grammar with an arity of `1`. We do that by attaching a transform.
Since the arity of an expression can be evaluated at compile time, let's use
`mpl::int_<1>` to represent the arity of the first placeholder. The following
attaches a transform that always evaluates to `mpl::int_<1>`:

    when< terminal< placeholder1 >, mpl::int_<1>() >

This grammar rule will match any `placeholder1` terminal, and will transform it
to a (default-constructed) `mpl::int_<1>` object. As described previously, 
`mpl::int_<1>()` is a function type, but Proto interprets it as an object to
construct. We will have a similar transform to convert `placeholder2` terminals
into `mpl::int_<2>`, and other terminals into `mpl::int_<0>`.

Next, let's write a transform for unary operators that returns the arity of the
operand. It is simply:

    when< unary_expr< _, CalcArity >, CalcArity(_arg) >

The transform `CalcArity(_arg)` recursively applies the `CalcArity`
transform to the child node of the unary expression. As you might have noticed, 
`CalcArity(_arg)` is another function type, but Proto interprets this one 
differently. Rather than trying to construct a `CalcArity` object, Proto
knows this is a function object and invokes it instead.

[note When using function types as Proto transforms, they can either represent
an object to construct or a function to call. It is similar to C++ where the
syntax `foo(x)` can either be interpreted as an object to construct or a
function to call, depending on whether `foo` is a type or a function. Proto
can't know in general which is the case, so it uses a trait, `proto::is_callable<>`,
to differentiate. `is_callable< mpl::int_<1> >::value` is false so `mpl::int_<1>()`
is an object to construct, but `is_callable< CalcArity >::value` is true so
`CalcArity(_arg)` is a function to call. (`is_callable< CalcArity >::value` is true
because `CalcArity` inherits from `proto::or_<>`, which is callable.)]

[/
    That begs the question, what does `unary_expr<>`'s transform do? Well,
    `unary_expr< _, CalcArity >` has a default transform
    associated with it. It is a /pass-through/ transform. When an expression
    of the form `expr< T, arg1< X > >` is passed to the transform, its `apply<>`
    member template will invoke the `CalcArity` transform (which we haven't
    completely defined yet -- patience) on `X` resulting in `Y`, and then
    reassemble the expression as `expr< T, arg1< Y > >`.

    [note You may have noticed that Proto types like `unary_expr<>` serve several
    different but related roles. In particular, `unary_expr<>` is ...

    ... [*a meta-function]: `unary_expr<T, X>::type` is a typedef for
    `expr<T, args1<X> >`.

    ... [*a grammar]: `unary_expr<U, Y>` is a simle grammar that matches 
    `expr<T, args1<X> >` if an only if `U` is `T` or `proto::_`, and `Y` is a
    grammar that matches `X`.

    ... [*a transform]: `unary_expr<U, Y>::apply<expr<T, args1<X> >, S, V>::type`
    applies `unary_expr<>`'s pass-through transform to `expr<T, args1<X> >` with
    state `S` and visitor `V`. The result is 
    `expr<T, args1< Y::apply<X, S, V>::type > >`.
    ]

    So, putting a few things together, consider the calculator expression `+_1`,
    which would have the following type:

        expr< tag::posit, arg1<
            expr< tag::terminal, arg0< placeholder1 > >
        > >

    If we executed the `unary_expr< _, CalcArity >` transform on this
    expression, we would expect to get:

        expr< tag::posit, arg1<
            mpl::int_<1>
        > >

    And if we added the `transform::arg<>` transform also, as in
    `transform::arg< unary_expr< _, CalcArity > >`, we expect the result
    to be:

        mpl::int_<1>

    Which is exactly what we want.

    [note *Default Transforms*

    All the tools Proto provides for defining grammar rules have default transforms
    associated with them. Just as `unary_expr<>` has a pass-through transform,
    so too does `binary_expr<>`, `shift_right<>`, and all the others.
    `proto::or_<>` has a default transform which evaluates the transform of the
    branch that matched. `proto::and_<>`'s default transform evaluates the
    transform of the last branch. Even `proto::expr<>`, `proto::if_<>`,
    `proto::not_<>`, and `proto::_` have no-op default transforms that simply return
    unmodified the expressions passed to them.
    ]
]

The arity of a binary operator is the maximum of the arity of the left and
right operands. We can specify this with the help of `mpl::max<>`, which is a
so-called meta-function that computes the maximum of two compile-time integers.
The transform is described below:

    when<
        binary_expr< _, CalcArity, CalcArity >
      , mpl::max< CalcArity(_left), CalcArity(_right) >()
    >

The above says to match binary calculator expressions and compute their
arity by first computing the arity of the left and right children and then
taking their maximum.

There's a lot going on in the above transform, so let's take it one piece
at a time, starting with the parts we know. `CalcArity(_left)`
will calculate the arity of the left child, returning a compile-time integer.
Likewise for `CalcArity(_right)`. What is new is that these two
transforms are nested within another: `mpl::max<...>()`. Proto notices that
`mpl::max<...>` is not callable, so this transform is interpreted as an 
object to construct rather than a function to invoke. Using meta-programming
tricks, Proto disassembles the `mpl::max<...>` template looking for nested
Proto transforms to apply. It finds two and applies them, resulting in 
`mpl::max< mpl::int_<X>, mpl::int_<Y> >`.

Having first applied any nested transforms, Proto then looks to see if 
`mpl::max<X, Y>` has a nested `::type` typedef. This is a common convention
used by meta-functions. In this case, `mpl::max<>::type` is a typedef
for `mpl::int_< Z >` where `Z` is the maximum of `X` and `Y`. The trailing
`()` on the transform indicates that the result should be default-constructed,
so this transform returns `mpl::int_<Z>()`. And we're done.

[note Had `mpl::max<>` not had a nested `::type` typedef, the transform
would have created and returned a default-constructed `mpl::max<>` object
instead. That is, the result of substituting nested transforms need not
of necessity have a nested `::type` typedef, but it is used if it is there.]

Piecing it all together, the complete `CalcArity` looks like this:

[CalcArity]

We can use our `CalcArity` transform to calculate the arity of any
calculator expression:

    int i = 0; // not used, dummy state and visitor parameter

    std::cout << CalcArity()( lit(100) * 200, i, i) << '\n';
    std::cout << CalcArity()( (_1 - _1) / _1 * 100, i, i) << '\n';
    std::cout << CalcArity()( (_2 - _1) / _2 * 100, i, i) << '\n';

This displays the following:

[pre
0
1
2
]

(Aside: this uses the fact that `mpl::int_<1>` has a conversion to `int(1)`.)

[endsect]

[/========================]
[section Canned Transforms]
[/========================]

So far, we've seen how to write custom transforms using function types.
These were implemented in terms of more primitive transforms provided by
Proto, such as `_arg`, `_left`, and `_right`. This section describes those
transforms and others in detail.

All the transforms defined in this section are of the following form:

    struct some_transform : callable
    {
        template<typename Sig>
        struct result;

        template<typename This, typename Expr, typename State, typename Visitor>
        struct result<This(Expr, State, Visitor)>
        {
            typedef ... type;
        };

        template<typename Expr, typename State, typename Visitor>
        typename result<void(Expr, State, Visitor)>::type
        operator()(Expr const &expr, State const &state, Visitor &visitor) const
        {
            return ...;
        }
    };

So defined, `some_transform` is a transform "in the raw". It can be used
without needing to explicitly specify any arguments to the transform. These
are the building blocks from which you can compose larger transforms using
function types.

[section:arg_c_and_friends [^_arg], [^_left], and [^_right]]

    namespace boost { namespace proto 
    {
        namespace transform
        {
            template<long N>
            struct arg_c;

            typedef arg_c<0> arg0;
            typedef arg_c<1> arg1;
            ...
            typedef arg_c<9> arg9;

            typedef arg_c<0> arg;
            typedef arg_c<0> left;
            typedef arg_c<1> right;
        }

        typedef transform::arg0 _arg0;
        typedef transform::arg1 _arg1;
        ...
        typedef transform::arg9 _arg9;

        typedef transform::arg    _arg;
        typedef transform::left   _left;
        typedef transform::right  _right;
    }}

These transforms are useful for extracting the ['[^N]]th argument from an
expression. The `_left` transform is equivalent to the `arg_c<0>` transform,
and the `_right` transform is equivalent to the `arg_c<1>` transform.

[table
    [   [Expression]
        [Returns]
    ]
    [   [`transform::arg_c<N>::result<void(Expr, State, Visitor)>::type`]
        [`proto::result_of::arg_c<Expr, N>::type`]
    ]
    [   [`transform::arg_c<N>()(expr, state, visitor)`]
        [`proto::arg_c<N>(expr)`]
    ]
    [   [`transform::left::result<void(Expr, State, Visitor)>::type`]
        [`proto::result_of::left<Expr>::type`]
    ]
    [   [`transform::left()(expr, state, visitor)`]
        [`proto::left(expr)`]
    ]
    [   [`transform::right::result<void(Expr, State, Visitor)>::type`]
        [`proto::result_of::right<Expr>::type`]
    ]
    [   [`transform::right()(expr, state, visitor)`]
        [`proto::right(expr)`]
    ]
]

Example:

    // Matches an integer terminal and extracts the int.
    struct Int
      : when< terminal<int>, _arg >
    {};

[endsect]

[section:identity_and_friends [^_expr], [^_state] and [^_visitor]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            struct expr;
            struct state;
            struct visitor;
        }

        typedef transform::expr     _expr;
        typedef transform::state    _state;
        typedef transform::visitor  _visitor;
    }}

The `expr`, `state` and `visitor` transforms merely return the
`expr`, `state` and `visitor` arguments, respectively. Proto's
wildcard pattern, `_`, behaves like `transform::expr` when used
as a transform.

[table
    [   [Expression]
        [Returns]
    ]
    [   [`_::result<void(Expr, State, Visitor)>::type`]
        [`Expr`]
    ]
    [   [`_()(expr_, state, visitor)`]
        [`expr_`]
    ]
    [   [`transform::expr::result<void(Expr, State, Visitor)>::type`]
        [`Expr`]
    ]
    [   [`transform::expr()(expr_, state, visitor)`]
        [`expr_`]
    ]
    [   [`transform::state::result<void(Expr, State, Visitor)>::type`]
        [`State`]
    ]
    [   [`transform::state()(expr, state_, visitor)`]
        [`state_`]
    ]
    [   [`transform::visitor::result<void(Expr, State, Visitor)>::type`]
        [`Visitor`]
    ]
    [   [`transform::visitor()(expr, state, visitor_)`]
        [`visitor_`]
    ]
]

Example:

    // Matches a subscript expression where the left- and right-hand operands
    // match MyGrammar, returns the expression unmodified
    struct Subscript
      : when< subscript<MyGrammar, MyGrammar>, _expr >
    {};

[endsect]

[section:if [^if_<>]]

    namespace boost { namespace proto 
    {
        namespace control
        {
            template<
                typename If
              , typename Then = _
              , typename Else = not_<_> 
            >
            struct if_;
        }

        using control::if_;
    }}

We've already seen the _if_ template in the context of grammars, but
_if_ can also be used as a transform. It can be used to conditionally
apply one transform or another based on some condition. The three
template parameters are Proto transforms. The result of applying the
first transform should be a compile-time Boolean. If it is true, then
the first transform is applied. The second is applied otherwise.

[table
    [   [Expression]
        [Returns]
    ]
    [   [``control::if_<If, Then, Else>
    ::result<void(Expr, State, Visitor)>::type``]
        [``typedef
    mpl::if_<
        when<_, If>::result<void(Expr, State, Visitor)>::type
      , when<_, Then>
      , when<_, Else>
    >::type
branch;

typedef branch::result<void(Expr, State, Visitor)>::type type;``]
    ]
    [   [`control::if_<If, Then, Else>()(expr, state, visitor)`]
        [``typedef ... branch; // Same as above
branch()(expr, state, visitor);``]
    ]
]

Example:

    // Match a terminal. If size of the terminal
    // argument is less than or equal to 4, make
    // a new terminal that stores the argument by
    // value. Otherwise, store the argument by
    // reference.
    struct ByValOrRef
      : when<
            terminal<_>
          , if_<
                mpl::less_equal<
                    mpl::sizeof_<_arg>
                  , mpl::size_t<4>
                >()
              , _make_terminal(_arg)
              , _make_terminal(_ref(_arg))
            >
        >
    {};

[endsect]

[section:and_or_not [^and_<>], [^or_<>], and [^not_<>]]

    namespace boost { namespace proto 
    {
        namespace control
        {
            template<typename... T>
            struct and_;

            template<typename... T>
            struct or_;

            template<typename T>
            struct not_;
        }

        using control::and_;
        using control::or_;
        using control::not_;
    }}

As with _if_, the grammar elements _and_, _or_, and _not_ can
also be used as transforms. At a high level, here is what the
transforms do:

[variablelist
[ [`and_<T0,T1,...,Tn>`]
  [Apply the transform `Tn`.] ]
[ [`or_<T0,T1,...,Tn>`]
  [Apply the transform `Tx` where `x` is the lowest number
   such that `matches<Expr,Tx>::value` is `true`.] ]
[ [`not_<T>`] [Return the current expression unchanged.] ]
]

The following table specifies the behaviors described above more
precisely.

[table
    [   [Expression]
        [Returns]
    ]
    [   [``control::and_<A,B,C>
    ::result<void(Expr, State, Visitor)>::type``]
        [`C::result<void(Expr, State, Visitor)>::type`]
    ]
    [   [`control::and_<A,B,C>()(expr, state, visitor)`]
        [`C()(expr, state, visitor)`]
    ]
    [   [``control::or_<A,B,C>
    ::result<void(Expr, State, Visitor)>::type``]
        [``typedef mpl::if_<
    matches<Expr, A>
  , A
  , mpl::if_<
        matches<Expr, B>
      , B
      , C
    >::type
>::type which;

typedef which::result<void(Expr, State, Visitor)>::type type;``]
    ]
    [   [`control::or_<A,B,C>()(expr, state, visitor)`]
        [``typedef ... which; // Same as above
which()(expr, state, visitor);``]
    ]
    [   [``control::not_<A>
    ::result<void(Expr, State, Visitor)>::type``]
        [`Expr`]
    ]
    [   [`control::not_<A>()(expr, state, visitor)`]
        [`expr`]
    ]
]

Example:

    // A transform that matches any expression and
    // unwraps any reference_wrapped terminals it
    // finds.
    struct UnwrapReference
      : or_<
            // Pass through terminals that are not
            // reference_wrappers unchanged:
            and_<
                terminal<_>
              , not_<if_<is_reference_wrapper<_arg>()> >
            >
            // For other terminals (i.e., reference_wrapper
            // terminals), unwrap the reference:
          , when<
                terminal<_>
              , terminal<unwrap_reference<_arg> >(_arg)
            >
            // Otherwise, match non-terminals and
            // recurse.
          , when<
                nary_expr<_, vararg<UnwrapReference> >
            >
        >
    {};

The above transform serves to illustrate the behaviors of the _and_,
_or_, and _not_ transforms, but it is admittedly contrived. The
transform is more easily written as follows:

    // Functionally identical to the UnwrapReference
    // transform above:
    struct UnwrapReference
      : or_<
            when<
                terminal<reference_wrapper<_> >
              , terminal<unwrap_reference<_arg> >(_arg)
            >
          , terminal<_>
          , nary_expr<_, vararg<UnwrapReference> >
        >
    {};

[endsect]

[section:call [^call<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Fun>
            struct call;
        }

        using transform::call;
    }}

The `call<>` transform is used to invoke callable transforms and evaluate
their arguments. When you use a callable transform as in 
`when< posit<_>, Callable(_arg) >`, the `call<>` transform is used behind
the scenes to evaluate `Callable(_arg)`. In fact, for any callable
transform, the following short- and long-forms are equivalent:

[table
    [ [Short From]
      [Long Form] ]
    [ [ `when< Grammar, Callable(Tran1, Tran2...) >` ]
      [ `when< Grammar, call< Callable(Tran1, Tran2...) > >` ] ]
]

You might decide to use `call<>` explicitly in cases when Proto
can't figure out that a given transform is callable. (See the discussion on
the `is_callable<>` trait TODO LINK.) Rather than specialize 
`proto::is_callable<>` for your transform, you can simply wrap its use in
`call<>`, instead. 

[tip For users of legacy compilers like MSVC 7.1, `call<>` is useful to work
around compiler bugs. Doubly-nested transforms such as `Callable(_arg1(_arg2))`
cause older compilers problems, but the equivalent `Callable(call<_arg1(_arg2)>)`
solves the problem.]

The semantics of `call<>` are described in the table below:

[table
    [   [Expression]
        [Returns]
    ]
    [   [`call<Fun(A0, A1, ... AN)>::result<void(Expr, State, Visitor)>::type`]
        [``boost::result_of<Fun(
    when<_, A0>::result<void(Expr, State, Visitor)>::type
  , when<_, A1>::result<void(Expr, State, Visitor)>::type
    ...
  , when<_, AN>::result<void(Expr, State, Visitor)>::type
)>::type``]
    ]
    [   [`call<Fun(A0, A1, ... AN)>()(expr, state, visitor)`]
        [``Fun()(
    when<_, A0>()(expr, state, visitor)
  , when<_, A1>()(expr, state, visitor)
    ...
  , when<_, AN>()(expr, state, visitor)
)``]
    ]
]

The target of a callable transform can be any function object that implements
the Boost.ResultOf protocol. Function objects that take up to
`BOOST_PROTO_MAX_ARITY` are handled.

For callable transforms that take 0, 1, or 2 arguments, special handling is done 
to see if the transform actually expects 3 arguments, as Proto's primitive 
transforms do. (This can be detected with meta-programming tricks.) So, even 
though a transform like `_arg1` requires three parameters: expression, 
state and visitor; it can be "called" with just one, like `_arg1(_arg2)`. Proto
treats this as if were `call<_arg1(_arg2, _state, _visitor)>`.

If no transform arguments are specified at all, as in `call<_arg1>`, this is
the same as `_arg1`. For this reason, `call<_arg1>(_arg2)` is the same as
`call<_arg1(_arg2)>`.

Example:

[LazyMakePair2]

[endsect]

[section:make [^make<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Fun>
            struct make;
        }

        using transform::make;
    }}

The `make<>` transform is used to construct objects and evaluate
their constructor arguments. When you use an object transform as in 
`when< posit<_>, Object(_arg) >`, the `make<>` transform is used behind
the scenes to evaluate `Object(_arg)`. In fact, for any object
transform, the following short- and long-forms are equivalent:

[table
    [ [Short From]
      [Long Form] ]
    [ [ `when< Grammar, Object(Tran1, Tran2...) >` ]
      [ `when< Grammar, make< Object(Tran1, Tran2...) > >` ] ]
]

You might decide to use `make<>` to explicitly differentiate object
transforms from callable transforms. (See `call<>`.)

[tip For users of legacy compilers like MSVC 7.1, `make<>` is useful to work
around compiler bugs. Doubly-nested transforms such as `Object1(Object2(_arg))`
cause older compilers problems, but the equivalent `Object1(make<Object2(_arg)>)`
solves the problem.]

The `make<>` transform checks to see if the resulting object type is a template.
If it is, the template type is disassembled to find nested transforms. Proto
considers the following types to represent transforms:

[def __type__ [~type]]
[def __X__  X\']
[def __X0__ X0\']
[def __X1__ X1\']

* Function types
* Function pointer types
* Types for which `proto::is_callable<__type__>::value` is `true`

When an object transform with a template type such as
`Object<X0,X1,...>(Args...)` is evaluated with a given
`Expr`, `State`, and `Visitor`, the result type is 
`make_<Object<X0,X1,...>, Expr, State, Visitor>::type` which is
defined as follows. For each `X` in `X0,X1,...`, do:

* If `X` is a template like `Object2<Y0,Y1,...>`, then let `__X__`
  be `make_<Object2<Y0,Y1,...>, Expr, State, Visitor>::type`
  (which evaluates this procedure recursively). Note whether any
  substitutions took place during this operation.
* Otherwise, if `X` is a transform, then let `__X__` be
  `when<_, X>::result<void(Expr, State, Visitor)>::type`.
  Note that a substitution took place.
* Otherwise, let `__X__` be `X`, and note that no substitution
  took place.
* If any substitutions took place in any of the above steps and
  `Object<__X0__,__X1__,...>` has a nested `::type` typedef, the
  result type is `Object<__X0__,__X1__,...>::type`.
* Otherwise, the result type is `Object<__X0__,__X1__,...>`.

Note that `when<>` is implemented in terms of `call<>` and `make<>`,
so the above procedure is evaluated recursively.

Given the above description of the `make_<>` helper, the semantics
of the `make<>` transform is described as follows:

[def __AN__ A[~N]]

[table
    [   [Expression]
        [Returns]
    ]
    [   [`make<Object(A0, A1, ... __AN__)>::result<void(Expr, State, Visitor)>::type`]
        [`make_<Object, Expr, State, Visitor>::type`]
    ]
    [   [`make<Object(A0, A1, ... __AN__)>()(expr, state, visitor)`]
        [``make_<Object, Expr, State, Visitor>::type(
    when<_, A0>()(expr, state, visitor)
  , when<_, A1>()(expr, state, visitor)
    ...
  , when<_, __AN__>()(expr, state, visitor)
)``]
    ]
]

Objects with constructors that take up to `BOOST_PROTO_MAX_ARITY` are handled.
Some types are so-called /aggregates/ that do not have constructors; rather,
they use /aggregate initialization/. For these types, you can specialize 
`proto::is_aggregate<>` and Proto will use a brace initializer list to
initialize the object rather than a constructor. Proto knows that `proto::expr<>`
is such an aggregate, so if you use object transforms to "construct" a
new node in an expression tree, the right thing happens.

If no transform arguments are specified at all, as in `make<Object>`, this is
the same as `make<Object()>`.

Example:

[LazyMakePair]

[endsect]

[section:bind [^bind<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Fun>
            struct bind;
        }

        using transform::bind;
    }}

Sometimes you would like a higher-order transform that returns another
transform to be evaluated. This can happen when you have a transform
whose behavior needs to be parameterized on the current state of the
transformation. For these situations, you can use the `bind<>` transform,
which is essentially an invocation of the `make<>` transform (to evaluate
any nested transforms and create the higher-order transform) followed
by an invocation of `call<>` (to actually execute the higher-order
transform).

The behavior of `bind<>` is easily specified in terms of `make<>` and
`call<>`.

[table
    [   [Expression]
        [Returns]
    ]
    [   [`bind<Object(A0, A1, ... __AN__)>::result<void(Expr, State, Visitor)>::type`]
        [``call<
    make<Object>::result<void(Expr, State, Visitor)>::type(A0, A1, ... __AN__)
>::result<void(Expr, State, Visitor)>::type``]
    ]
    [   [`bind<Object(A0, A1, ... __AN__)>()(expr, state, visitor)`]
        [``call<
    make<Object>::result<void(Expr, State, Visitor)>::type(A0, A1, ... __AN__)
>()(expr, state, visitor)``]
    ]
]

If no transform arguments are specified at all, as in `bind<Object>`, this is
the same as `bind<Object(_expr, _state, _visitor)>`.

[endsect]

[section:when [^when<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Grammar, typename Transform = Grammar>
            struct when;
        }

        using transform::when;
    }}

`when<>` associates a grammar rule with a transform. It can be used
in a grammar in place of the rule; that is, it behaves as a grammar
rule. Expression tree nodes that match the grammar rule are processed
with the associated transform; that is, `when<>` also behaves like
a transform.

When no transform is specified, as with `when< posit<Calculator> >`,
the grammar is treated as the transform. Every grammar element has
a default transform. For most, such as `posit<>`, the default transform
is `pass_through<>`.

The `when<>` transform is easily specified in terms of `call<>`,
`make<>`, and the `is_callable<>` trait.

[table
    [   [Expression]
        [Returns]
    ]
    [   [`when<Grammar, R(A0, A1, ... __AN__)>::result<void(Expr, State, Visitor)>::type`]
        [``mpl::if_<
    is_callable<R>
  , call<R(A0, A1, ... __AN__)>
  , make<R(A0, A1, ... __AN__)>
>::type::result<void(Expr, State, Visitor)>::type``]
    ]
    [   [`when<Grammar, R(A0, A1, ... __AN__)>()(expr, state, visitor)`]
        [``mpl::if_<
    is_callable<R>
  , call<R(A0, A1, ... __AN__)>
  , make<R(A0, A1, ... __AN__)>
>::type()(expr, state, visitor)``]
    ]
]

If no transform arguments are specified, as in `when<Grammar, _arg>`, the
transform is assumed to be callable; that is, it is equivalent to
`when<Grammar, call<_arg> >`.

[endsect]

[section:fold [^fold<>] and [^reverse_fold<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Sequence, typename State0, typename Fun>
            struct fold;

            template<typename Sequence, typename State0, typename Fun>
            struct reverse_fold;
        }

        using transform::fold;
        using transform::reverse_fold;
    }}

The transforms `fold<>` and `reverse_fold<>` are akin to the
`std::accumulate()` algorithm in the STL, or the `fold()` algorithm in
Boost.Fusion. They iterate over some sequence and
accumulate some state at each element. The `fold<>`
transform iterates over the children in order, starting with the 0th child.
The `reverse_fold<>` transform does it in reverse order, starting with the Nth
child. (Note that for building things like cons lists, you'll often want to
built it back-to-front with `reverse_fold<>`.)

Both `fold<>` and `reverse_fold<>` are implemented in terms of `fusion::fold<>`.
The three template parameters must each be Proto transforms. The have the following
meaning:

* `Sequence`: A Proto transform that returns a Fusion sequence.
* `State`: A Proto transform that returns the initial state of the fold.
* `Fun`: A Proto transform representing the operation to perform at each
  iteration of the fold algorithm.

Often, the `Sequence` parameter is `proto::_`, which returns the current node
in the Proto expression tree. Tree nodes are valid Fusion sequences, where
the children are the elements of the sequence.

The semantics of the `fold<>` and `reverse_fold<>` transforms can both be
understood in terms of a helper struct, `as_callable<>`, which binds the
visitor and the `Fun` transform into a binary function object for use by
`fusion::fold()`. `as_callable<>` has the following behavior:

[table
    [   [Expression]
        [Returns]
    ]
    [   [`as_callable<Fun, Visitor>::result<void(Expr, State)>::type`]
        [`when<_, Fun>::result<void(Expr, State, Visitor)>::type`]
    ]
    [   [`as_callable<Fun, Visitor>(visitor)(expr, state)`]
        [`when<_, Fun>()(expr, state, visitor)`]
    ]
]

With the above `as_callable<>` adaptor, `fold<>` and `reverse_fold<>`
can be easily implemented in terms of `fusion::fold<>`:

[table
    [   [Expression]
        [Returns]
    ]
    [   [`fold<Sequence, State0, Fun>::result<void(Expr, State, Visitor)>::type`]
        [``fusion::result_of::fold<
    when<_, Sequence>::result<void(Expr, State, Visitor)>::type
  , when<_, State0>::result<void(Expr, State, Visitor)>::type
  , as_callable<Fun, Visitor>
>::type``]
    ]
    [   [`fold<Sequence, State0, Fun>()(expr, state, visitor)`]
        [``fusion::fold(
    when<_, Sequence>()(expr, state, visitor)
  , when<_, State0>()(expr, state, visitor)
  , as_callable<Fun, Visitor>(visitor)
)``]
    ]
    [   [`reverse_fold<Sequence, State0, Fun>::result<void(Expr, State, Visitor)>::type`]
        [``fusion::result_of::fold<
    fusion::result_of::reverse<
        when<_, Sequence>::result<void(Expr, State, Visitor)>::type
    >::type
  , when<_, State0>::result<void(Expr, State, Visitor)>::type
  , as_callable<Fun, Visitor>
>::type``]
    ]
    [   [`reverse_fold<Sequence, State0, Fun>()(expr, state, visitor)`]
        [``fusion::fold(
    fusion::reverse(
        when<_, Sequence>()(expr, state, visitor)
    )
  , when<_, State0>()(expr, state, visitor)
  , as_callable<Fun, Visitor>(visitor)
)``]
    ]
]

[#reverse_fold_example]Example:

[AsArgList]

[endsect]

[section:fold_tree [^fold_tree<>] and [^reverse_fold_tree<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Sequence, typename State0, typename Fun>
            struct fold_tree;

            template<typename Sequence, typename State0, typename Fun>
            struct reverse_fold_tree;
        }

        using transform::fold;
        using transform::reverse_fold;
    }}

The `fold_tree<>` and `reverse_fold_tree<>` transforms recursively apply the
`fold<>` and `reverse_fold<>` transforms to sub-trees that all share a common
tag type. This is useful for flattening trees into lists; for example, you
might use `reverse_fold_tree<>` to flatten an expression tree like `a | b | c`
into a Fusion list like `cons(a, cons(b, cons(c)))`.

The `fold_tree<>` and `reverse_fold_tree<>` transforms are unlike the other
transforms that Proto provides in that they operate on entire sub-trees rather
than just single nodes within the tree.

These are higher-level transforms, implemented in terms of the `fold<>`
and `reverse_fold<>` transforms and helper structs `fold_tree_<>` and
`reverse_fold_tree_<>`, one of which is shown below:

    // fold_tree_ either recurses into the expression, if its Grammar
    // matches, or else ends the recursion by matching Grammar and
    // applying its transform.
    template<typename Grammar, typename Fun>
    struct fold_tree_
      : or_<
            when<Grammar, fold<_, _state, fold_tree_<Grammar, Fun> > >
          , when<_, Fun>
        >
    {};
    
The `reverse_fold_tree_<>` helper is specified similarly, only with
`reverse_fold<>` instead of `fold<>`. With these two helpers, we can
specify the behavior of `fold_tree<>` and `reverse_fold_tree<>` as
follows:

[table
    [   [Expression]
        [Returns]
    ]
    [   [``fold_tree<Sequence, State0, Fun>
    ::result<void(Expr, State, Visitor)>::type``]
        [``fold<
    Sequence
  , State0
  , fold_tree_<
        nary_expr<Expr::proto_tag, vararg<_> >
      , Fun
    >
>::result<void(Expr, State, Visitor)>::type``]
    ]
    [   [`fold_tree<Sequence, State0, Fun>()(expr, state, visitor)`]
        [``fold<
    Sequence
  , State0
  , fold_tree_<
        nary_expr<Expr::proto_tag, vararg<_> >
      , Fun
    >
>()(expr, state, visitor)``]
    ]
    [   [``reverse_fold_tree<Sequence, State0, Fun>
    ::result<void(Expr, State, Visitor)>::type``]
        [``reverse_fold<
    Sequence
  , State0
  , reverse_fold_tree_<
        nary_expr<Expr::proto_tag, vararg<_> >
      , Fun
    >
>::result<void(Expr, State, Visitor)>::type``]
    ]
    [   [`reverse_fold_tree<Sequence, State0, Fun>()(expr, state, visitor)`]
        [``reverse_fold<
    Sequence
  , State0
  , reverse_fold_tree_<
        nary_expr<Expr::proto_tag, vararg<_> >
      , Fun
    >
>()(expr, state, visitor)``]
    ]
]

Example:

[FoldTreeToList]

[endsect]

[section:pass_through [^pass_through<>]]

    namespace boost { namespace proto
    {
        namespace transform
        {
            template<typename Grammar>
            struct pass_through;
        }

        using transform::pass_through;
    }}

The `pass_through<>` transform iterates over the pairs of
children in the grammar and the expression, applying the child grammar's
transform to the corresponding child expression. The resulting transformed
children expressions are reassembled back into an expression of the same
type as the parent expression.

As a side-effect, `pass_through<>` transforms all sub-expressions held by
reference into ones held by value.

Note that all expression generator meta-functions (Eg., `posit<>`, 
`shift_right<>`, `function<>`, `nary_expr<>`, etc.) have a pass-through
transform by default, so there is rarely any need to use the `pass_through<>`
transform explicitly.

[table
    [   [Expression]
        [Returns]
    ]
    [   [``transform::pass_through<Grammar>
    ::result<void(Expr, State, Visitor)>::type``]
        [``typename nary_expr<
    Expr::proto_tag
  , result_of::arg_c<Grammar, 0>::type::result<
        void(result_of::arg_c<Expr, 0>::type, State, Visitor)>::type
  , result_of::arg_c<Grammar, 1>::type::result<
        void(result_of::arg_c<Expr, 1>::type, State, Visitor)>::type
    // ...
  , result_of::arg_c<Grammar, N>::type::result<
        void(result_of::arg_c<Expr, N>::type, State, Visitor)>::type
>::type``]
    ]
    [   [`transform::pass_through<Grammar>()(expr, state, visitor)`]
        [``transform::pass_through<Grammar>
    ::result<void(Expr, State, Visitor)>::type::make(
        result_of::arg_c<Grammar, 0>::type()(
            proto::arg_c<0>(expr), state, visitor)
      , result_of::arg_c<Grammar, 1>::type()(
            proto::arg_c<1>(expr), state, visitor)
        // ...
      , result_of::arg_c<Grammar, N>::type()(
            proto::arg_c<N>(expr), state, visitor)
    )``]
    ]
]

Example:

[Promote]

[endsect]

[endsect]

[/======================================================]
[section:user_defined_transforms User-Defined Transforms]
[/======================================================]

In previous sections, we've seen how to compose larger transforms
out of smaller transforms using function types.
We've also seen the primitive transforms that Proto provides. 
So-called primitive transforms can be used without specifying
arguments, like `_arg0` which returns the first child of the 
current node. But primitive transforms are not special in any way.
They are merely ternary function objects that take the current
expression, state and visitor as arguments.

You can define your own primitive transforms. You might want to
do this if your transform is complicated and composing it out
of primitives becomes unwieldy. You might also do this
to work around compiler bugs on legacy compilers that makes
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.

To define your own primitive transform, merely define a ternary
function object that accepts an expression, a state and a visitor.
Here, for example, is how Proto defines the `arg_c<>` transform:

    namespace boost { namespace proto { namespace transform
    {
        // A transform that returns the I-th child
        template<int I>
        struct arg_c : callable
        {
            // Nested "result" template, used by
            // boost::result_of<> to compute the
            // return type of the function.
            template<typename Sig>
            struct result;

            template<typename This, typename Expr, typename State, typename Visitor>
            struct result<This(Expr, State, Visitor)>
              : proto::result_of::arg_c<Expr, I>
            {};

            // Function call operator that actually
            // executes the transform.
            template<typename Expr, typename State, typename Visitor>
            typename proto::result_of::arg_c<Expr, I>::const_reference
            operator ()(Expr const &expr, State const &, Visitor &) const
            {
                return proto::arg_c<I>(expr);
            }
        };
    }}}

    namespace boost { namespace proto
    {
        // Note that arg_c<I> is callable, so that
        // it can be used with arguments, as:
        //   arg_c<0>(arg_c<1>)
        template<int I>
        struct is_callable<transform::arg_c<I> >
          : mpl::true_
        {};
    }}

There is nothing particularly special about the definition of
`arg_c<>`. It is just an ordinary polymorphic function object. The
only interesting bit is the `is_callable<>` specialization, which
will be described in the section called "Making Your Transform 
Callable".

Once you have defined such a ternary function object, you can use
it as a transform without any arguments and Proto will automatically
pass it the current expression, state and visitor parameters.

[endsect]

[/=================================================]
[section:is_callable Making Your Transform Callable]
[/=================================================]

Transforms are typically of the form `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 `when<>` evaluates the transform.
`when<>` uses the `is_callable<>` trait to disambiguate between the two.
Proto does its best to guess whether a transform 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 specialize `is_callable<>`.

The first thing to know is that templates are not considered callable
by default. This is true ['even if the template inherits from 
`proto::callable`]. Consider the following erroneous transform:

    // Proto can't tell this defines a 
    // callable transform!
    template<typename T>
    struct times2 : 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
      : when< terminal<int>, times2<int>(_arg) >
    {};

The problem is that Proto doesn't know that `times2<int>` is a callable
transform. Instead, it assumes it's an object transform and 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?
In fact, determining 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<_arg(_arg1)>()`, which is a valid
transform that default-constructs a particular instantiation of 
`std::vector<>`. But `std::vector<>` will not suffer to be instantiated
with `_arg(_arg1)` as a template parameter! As a result, Proto has
to assume that a type `X<Y>` represents an object transform and not
a callable transform.]

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

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

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
    {
        template<typename T>
        struct is_callable<times2<T> >
          : mpl::true_
        {};
    }}

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

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

You could simply make sure that the transform is not
a template. Consider the following:

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

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

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 Dummy = callable>
    struct times2 : callable
    {
        typedef T result_type;

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

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

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

[endsect]

[endsect]
