intermediate_form.qbk

来自「Boost provides free peer-reviewed portab」· QBK 代码 · 共 1,171 行 · 第 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)
 /]


[/talk about:

  tag types
  generator metafunctions
  accessing child nodes
  metafunctions for tag type and arity
  deep_copy
  flatten
  debug utilities
  introspection with grammars and proto::matches
]

[/================================================================================]
[section:intermediate_form Intermediate Form:
    Understanding and Introspecting Expressions]
[/================================================================================]

By now, you know a bit about how to build a front-end for your DSEL "compiler" -- you can define terminals and functions that generate expression templates. But we haven't said anything about the expression templates themselves. What do they look like? What can you do with them? In this section we'll see.

[/=========================]
[heading The [^expr<>] Type]
[/=========================]

All Proto expressions are an instantiation of a template called `expr<>` (or a wrapper around such an instantiation). When we define a terminal as below, we are really initializing an instance of the _expr_ template.

    // Define a placeholder type
    template<int I>
    struct placeholder
    {};

    // Define the Protofied placeholder terminal
    proto::terminal< placeholder<0> >::type const _1 = {{}};

The actual type of `_1` looks like this:

    proto::expr< proto::tag::terminal, proto::term< placeholder<0> >, 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 child types, or in the case of terminals, the terminal's value
type. 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::arity >
    struct expr;

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

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 are the initializer
for the _expr_ struct, and the inner braces are for the member `_1.child0` which
is of type `placeholder<0>`. Note that we use braces to initialize `_1.child0`
because `placeholder<0>` is also an aggregate.

[/================================]
[heading Building Expression Trees]
[/================================]

The `_1` node is an instantiation of _expr_, and expressions containing
`_1` are also instantiations of _expr_. 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. The types look
like this:

    // The type of the expression -_1
    typedef
        proto::expr<
            proto::tag::negate
          , proto::list1<
                proto::expr<
                    proto::tag::terminal
                  , proto::term< placeholder<0> >
                  , 0
                > const &
            >
          , 1
        >
    negate_placeholder_type;
    
    negate_placeholder_type x = -_1;

    // The type of the expression _1 + 42
    typedef
        proto::expr<
            proto::tag::plus
          , proto::list2<
                proto::expr<
                    proto::tag::terminal
                  , proto::term< placeholder<0> >
                  , 0
                > const &
              , proto::expr<
                    proto::tag::terminal
                  , proto::term< int const & >
                  , 0
                >
            >
          , 2
        >
    placeholder_plus_int_type;
    
    placeholder_plus_int_type y = _1 + 42;

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 held by reference, ['even if it is a temporary object]. This last
  point becomes important later.
# Non-Proto expressions, such as the integer literal, are turned into Proto
  expressions by wrapping them in new `expr<>` terminal objects. These new
  wrappers are not themselves held by reference, but the object wrapped /is/.
  Notice that the type of the Protofied `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 An astute reader will notice that the object `y` defined above will be
left holding a dangling reference to a temporary int. In the sorts of 
high-performance applications Proto addresses, it is typical to build and
evaluate an expression tree before any temporary objects go out of scope, so
this dangling reference situation often doesn't arise, but it is certainly
something to be aware of. Proto provides utilities for deep-copying expression
trees so they can be passed around as value types without concern for dangling
references.]

[/=============================================]
[section:left_right_child Accessing Child Nodes]
[/=============================================]

After assembling an expression into a tree, you'll naturally want to be
able to do the reverse, and access a node's 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 child
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 = {42};

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

[/===================]
[heading [^child_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 _child_c_ function template, as demonstrated
below:

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

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

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

You can use the `result_of::child_c<>` metafunction to get the type of the Nth
child of an expression node. Usually you don't care to know whether a child
is stored by value or by reference, so when you ask for the type of the Nth
child of an expression `Expr`, you get the child's type after references and
cv-qualifiers have been stripped from it.

    template<typename Expr>
    void test_result_of_child_c(Expr const &expr)
    {
        typedef typename proto::result_of::child_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 = {42};
    test_result_of_child_c( i + 2 );

However, if you ask for the type of the Nth child of `Expr &` or `Expr const &`
(note the reference), the result type will be a reference, regardless of whether
the child is actually stored by reference or not. If you need to know exactly
how the child is stored in the node, whether by reference or by value, you can
use `fusion::result_of::value_at<Expr, N>::type`. The following table summarizes
the behavior of the `child_c<>` metafunction.

[table Accessing Child Types
    [[Metafunction Invocation][When the Child Is ...][The Result Is ...]]
    [[`proto::result_of::child_c<Expr, N>::type`][T][T]]
    [[][T &][T]]
    [[][T const &][T]]
    [[`proto::result_of::child_c<Expr &, N>::type`][T][T &]]
    [[][T &][T &]]
    [[][T const &][T const &]]
    [[`proto::result_of::child_c<Expr const &, N>::type`][T][T const &]]
    [[][T &][T &]]
    [[][T const &][T const &]]
    [[`fusion::result_of::value_at<Expr, N>::type`][T][T]]
    [[][T &][T &]]
    [[][T const &][T const &]]
]

[/========================================================]
[heading [^value()], [^child()], [^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 _child_, _left_, and _right_ functions. _child_
and _left_ are synonymous with `child_c<0>()`, and _right_ is synonymous with
`child_c<1>()`.

Another very common operation is accessing the value stored within a Proto
terminal. You can use the _value_ function for that.

There are also `result_of::child<>`, `result_of::left<>`, and `result_of::right<>`
metafunctions that merely forward to their `result_of::child_c<>` counterparts.
Likewise, there is a `result_of::value<>` metafunction that returns the type of the
value stored in a terminal node.

[/===========================================]
[heading Expression Nodes as Fusion Sequences]
[/===========================================]

Proto expression nodes are valid Fusion random-access sequences of their
child 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 are 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 {};
    proto::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
          , proto::functional::value()
        )
      , display()
    );

Recall from the Introduction that types in the `proto::functional` namespace
define function objects that correspond to Proto's free functions. So 
`proto::functional::value()` creates a function object that is equivalent to
the `proto::value()` function. 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:

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

    // ERROR: this doesn't work! Why?
    fusion::for_each(
        fusion::transform(
            _1 + 2 + 3 + 4
          , proto::functional::value()
        )
      , 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 child nodes that do /not/ have tag type `T`. This
process is evaluated recursively. So the above can correctly be written as:

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

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

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

[pre
1
2
3
4
]

[endsect]

[/=============================================================]
[section:tags_and_metafunctions Operator Tags and Metafunctions]
[/=============================================================]

The following table lists the overloadable C++ operators, the Proto tag types for 
each, and the name of the metafunctions for generating the corresponding Proto 
expression types. And as we'll see later, the metafunctions are also usable as 
grammars for matching such nodes, as well as pass-through transforms.

[table Operators, Tags and Metafunctions
    [[Operator]
    [Proto Tag]
    [Proto Metafunction]]

    [[unary `+`]
    [`proto::tag::unary_plus`]
    [`proto::unary_plus<>`]]

    [[unary `-`]
    [`proto::tag::negate`]
    [`proto::negate<>`]]

    [[unary `*`]
    [`proto::tag::dereference`]
    [`proto::dereference<>`]]

    [[unary `~`]
    [`proto::tag::complement`]
    [`proto::complement<>`]]

    [[unary `&`]
    [`proto::tag::address_of`]
    [`proto::address_of<>`]]