transforms.qbk

来自「Boost provides free peer-reviewed portab」· QBK 代码 · 共 1,417 行 · 第 1/4 页

[/
 / 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;