construction.qbk

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

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

[def __implelemtation_defined__ [~implementation-defined]]

[/=======================================================================================]
[section:expression_construction Expression Construction: Building Proto Expression Trees]
[/=======================================================================================]

We've seen some simple examples of how to use Proto, but we haven't really said
much about what is going on under the hood. How exactly does Proto build and
process expression trees? Now is the time to find out.

In the calculator example, we defined a placeholder terminal like this:

    // Define a placeholder type
    struct placeholder1 {};

    // Define the Proto-ified placeholder terminal
    terminal< placeholder1 >::type const _1 = {{}};

The actual type of `_1` looks like this:

    expr< tag::terminal, args0< placeholder1 >, 0 >

The _expr_ template is the most important type in Proto. Although you will
rarely need to deal with it directly, it's always there behind the scenes
holding your expression trees together. In fact, _expr_ /is/ the expression
tree -- branches, leaves and all. 

The _expr_ template makes up the nodes in expression trees. The first template
parameter is the node type; in this case, `proto::tag::terminal`. That means
that `_1` is a leaf-node in the expression tree. The second template parameter
is a list of children types. Terminals will always have only one type in the
type list. The last parameter is the arity of the expression. Terminals have
arity 0, unary expressions have arity 1, etc.

The _expr_ struct is defined as follows:

    template< typename Tag, typename Args, long Arity = Args::size >
    struct expr;

    template< typename Tag, typename Args >
    struct expr< Tag, Args, 1 >
    {
        typename Args::arg0 arg0;
        // ...
    };

The _expr_ struct does not define a constructor, or anything else that would
prevent static initialization. All _expr_ objects are initialized using
['aggregate initialization], with curly braces. In our example, `_1` is
initialized with the initializer `{{}}`. The outer braces is the initializer
for the _expr_ struct, and the inner braces are for the member `_1.arg0` which
is of type `placeholder1`. Note that we use braces to initialize `_1.arg0`
because `placeholder1` is also an aggregate.

[/====================================================]
[section:operator_overloads Proto's Operator Overloads]
[/====================================================]

Once we have some Proto terminals, expressions involving those terminals build
expression trees for us, as if by magic. It's not magic; Proto defines
overloads for each of C++'s overloadable operators to make it happen. As long
as one operand is a Proto expression, the result of the operation is a tree
node representing that operation.[footnote There are a couple of exceptions to
this. In ["`int x; x = _1`], the assignment isn't a Proto expression, even
though the right hand operand /is/ a Proto expression. That's just how C++ works.
The same is also true for the subscript operator and the function call
operator, as in ["`int *x; x[_1];`] and ["`std::sin(_1);`]. Them's the breaks,
as they say.]

[note The _expr_ struct lives in the `boost::proto` namespace, as do all of
Proto's operator overloads. The overloads are found via ADL (Argument-Dependent
Lookup). That is why expressions must be "tainted" with Proto-ness for Proto to
be able to build trees out of expressions.]

As a result of Proto's operator overloads, we can say:

    -_1;        // OK, build a unary-negate tree node
    _1 + 42;    // OK, build a binary-plus tree node

[endsect]

[/=================================================]
[section:expression_trees Building Expression Trees]
[/=================================================]

The `_1` node is an _expr_ type, and new nodes created with this type are
also _expr_ types. They look like this:

    // typeof( -_1 )
    expr<
        tag::negate
      , args1<
            ref_< expr< tag::terminal, args0< placeholder1 >, 0 > >
        >
      , 1
    >

    // typeof( _1 + 42 )
    expr<
        tag::plus
      , args2<
            ref_< expr< tag::terminal, args0< placeholder1 >, 0 > >
          , expr< tag::terminal, args0< int const & >, 0 >
        >
      , 2
    >

There are a few things to note about these types:

# Terminals have arity 0, unary expressions have arity 1 and binary expressions
  have arity 2.
# When one Proto expression is made a child node of another Proto expression,
  it is wrapped in _ref_, which is a simple reference wrapper. That is, Proto
  expressions hold their children by reference ['even if they are temporary
  objects]. This last point becomes important later.
# Non-Proto expressions, such as the integer literal, are turned into Proto
  expressions by making them Proto terminals. These terminal expressions
  are /not/ wrapped in _ref_, but the object itself /is/ held by reference.
  Notice that the type of the Proto-ified `42` literal is `int const &` -- held
  by reference.

The types make it clear: everything in a Proto expression tree is held by
reference. That means that building an expression tree is exceptionally cheap.
It involves no copying at all.

[note To use Proto effectively, you won't have to bother yourself with the
actual types that Proto generates. These are details, but you're likely to
encounter these types in compiler error messages, so it's helpful to be familiar
with them.]

[endsect]

[/==============================================]
[section:left_right_arg Accessing Children Nodes]
[/==============================================]

After assembling an expression into a tree, you'll naturally want to be
able to do the reverse, and access its children.
You may even want to be able to iterate over the children with algorithms
from the Boost.Fusion library. This section shows how.

[heading [^tag_of<>]]

A node in an expression tree is nothing more than a collection of children
nodes and a tag type. You can access the tag type of any Proto expression type
`Expr` directly as `typename Expr::proto_tag`, or you can use the _tag_of_
metafunction, as shown below:

    template<typename Expr>
    typename proto::result_of::tag_of<Expr>::type
    get_tag_of(Expr const &)
    {
        // Tag types are required to be default-constructible
        return typename proto::result_of::tag_of<Expr>::type();
    }

    proto::terminal<int>::type const i = {0};

    // Addition nodes have the "plus" tag type:
    proto::tag::plus plus_tag = get_tag_of( i + 2 );

[heading [^arg_c()]]

Each node in an expression tree corresponds to an operator in an expression,
and the children correspond to the operands, or arguments of the operator.
To access them, you can use the _arg_c_ function template, as demonstrated
below:

    proto::terminal<int>::type i = {0};

    // Get the 0-th operand of an addition operation:
    proto::terminal<int>::type &ri = proto::arg_c<0>( i + 2 );

    // Assert that we got back what we put in:    
    assert( &i == &ri );

You can use the `result_of::arg_c<>` metafunction to get the type of the Nth
child of an expression node. The nested `::type` of the `arg_c<>` metafunction
gives you the type after references and cv-qualifiers have been stripped from
the child's type.

    template<typename Expr>
    void test_result_of_arg_c(Expr const &expr)
    {
        typedef typename proto::result_of::arg_c<Expr, 0>::type type;
        
        // ::type is a non-cv qualified, non-reference
        BOOST_MPL_ASSERT((is_same< type, terminal<int>::type>));
    }
    
    // ...    
    terminal<int>::type i = {0};
    test_result_of_arg_c( i + 2 );

Why does the `arg_c<>` metafunction strip cv-qualifiers and references? The
reason is one of practicality. Because expression trees are most typically
built by holding references to temporary objects, lifetime management of these
children nodes can be problematic. If `arg_c<>::type` were a reference, it
would be very simple to create dangling references. Avoiding dangling
references results in tedious and verbose applications of `remove_reference<>`
and `remove_const<>`. This is especially problematic when building transforms
that operate on ephemeral constelations of temporary objects. The current
behavior of the `arg_c<>` metafunction makes it much simpler to write correct
code.

If you would like to know exactly the type of the Nth argument, including
references and cv-qualifiers, you can use
`fusion::result_of::value_at<Expr, N>::type`. This way, you can tell whether
a child is stored by value or by reference. And if you would like to know
the exact type that _arg_c_ returns, you can use 
`fusion::result_of::at_c<Expr, N>::type`. It will always be a reference type,
and its cv-qualification depends on the cv-qualification of `Expr` and
whether the child is stored by reference or not.

[heading [^arg()], [^left()], and [^right()]]

Most operators in C++ are unary or binary. For that reason, accessing the
only operand, or the left and right operands, are very common operations. For
this reason, Proto provides the _arg_, _left_, and _right_ functions. _arg_
and _left_ are synonomous with `arg_c<0>()`, and _right_ is synonomous with
`arg_c<1>()`.

There are also `result_of::arg<>`, `result_of::left<>`, and `result_of::right<>`
metafunctions that merely forward to their `result_of::arg_c<>` counterparts.

[heading Expression Nodes as Fusion Sequences]

Proto expression nodes are valid Fusion random-access sequences of their
children nodes. That means you can apply Fusion algorithms to them,
transform them, apply Fusion filters and views to them, and access their
elements using `fusion::at()`. The things Fusion can do to heterogeneous
sequences is beyond the scope of this users' guide, but below is a simple
example. It takes a lazy function invocation like `fun(1,2,3,4)` and uses
Fusion to print the function arguments in order.

    struct display
    {
        template<typename T>
        void operator()(T const &t) const
        {
            std::cout << t << std::endl;
        }
    };

    struct fun_t {};
    terminal<fun_t>::type const fun = {{}};

    // ...
    fusion::for_each(
        fusion::transform(
            // pop_front() removes the "fun" child
            fusion::pop_front(fun(1,2,3,4))
            // Extract the ints from the terminal nodes
          , functional::arg<>()
        )
      , display()
    );

The above invocation of `fusion::for_each()` displays the following:

[pre
1
2
3
4
]

[heading Flattening Proto Expression Tress]

Imagine a slight variation of the above example where, instead of iterating
over the arguments of a lazy function invocation, we would like to iterate
over the terminals in an addition expression:

    terminal<int>::type const _1 = {1};

    // ERROR: this doesn't work! Why?
    fusion::for_each(
        fusion::transform(
            _1 + 2 + 3 + 4
          , functional::arg<>()
        )
      , display()
    );

The reason this doesn't work is because the expression `_1 + 2 + 3 + 4` does
not describe a flat sequence of terminals --- it describes a binary tree. We
can treat it as a flat sequence of terminals, however, using Proto's _flatten_
function. _flatten_ returns a view which makes a tree appear as a flat Fusion
sequence. If the top-most node has a tag type `T`, then the elements of the
flattened sequence are the children nodes that do *not* have tag type `T`. This
process is evaluated recursively. So the above can correctly be written as:

    terminal<int>::type const _1 = {1};

    // OK, iterate over a flattened view
    fusion::for_each(
        fusion::transform(
            proto::flatten(_1 + 2 + 3 + 4)
          , functional::arg<>()
        )
      , display()
    );

The above invocation of `fusion::for_each()` displays the following:

[pre
1
2
3
4
]

[endsect]

[/===============================================================]
[section:tags_and_meta_functions Operator Tags and Meta-Functions]
[/===============================================================]

The following table lists the overloadable C++ operators, the Proto tag types
for each, and the name of the Proto meta-function for generating the 
corresponding Proto expression nodes. The meta-functions are also usable as
grammars for matching such nodes, as well as pass-through transforms, as
explained in later sections.

[table Operators, Tags and Meta-Functions
    [[Operator]
    [Proto Tag]
    [Proto Meta-Function]]

    [[unary `+`]
    [`tag::posit`]
    [`posit<>`]]        

    [[unary `-`]
    [`tag::negate`]