back_end.qbk

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

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

[/================================================================================]
[section:back_end Back Ends:
    Making Expression Templates Do Useful Work]
[/================================================================================]

Now that you've written the front end for your DSEL compiler, and you've learned a bit about the intermediate form it produces, it's time to think about what to /do/ with the intermediate form. This is where you put your domain-specific algorithms and optimizations. Proto gives you two ways to evaluate and manipulate expression templates: contexts and transforms.

* A /context/ is like a function object that you pass along with an expression to 
  the _eval_ function. It associates behaviors with node types. _eval_ walks the 
  expression and invokes your context at each node.
* A /transform/ is a way to associate behaviors, not with node types in an 
  expression, but with rules in a Proto grammar. In this way, they are like 
  semantic actions in other compiler-construction toolkits.

Two ways to evaluate expressions! How to choose? Contexts are a bit simpler to understand and to debug, since they are largely procedural, so contexts are a good place to start. But although transforms are more advanced, they are also more powerful; since they are associated with rules in your grammar, you can select the proper transform based on the entire /structure/ of a sub-expression rather than simply on the type of its top-most node.

Also, transforms have a concise and declarative syntax that can be confusing at first, but highly expressive and fungible once you become accustomed to it. And -- this is admittedly very subjective -- the author finds programming with Proto transforms to be an inordinate amount of /fun!/ Your mileage may vary.

[/================================================================================]
[section:expression_evaluation Expression Evaluation:
    Imparting Behaviors with a Context]
[/================================================================================]

Once you have constructed a Proto expression tree, either by using Proto's
operator overloads or with _make_expr_ and friends, you probably want to
actually /do/ something with it. The simplest option is to use `proto::eval()`,
a generic expression evaluator. To use _eval_, you'll need to define a
/context/ that tells _eval_ how each node should be evaluated. This section
goes through the nuts and bolts of using _eval_, defining evaluation contexts,
and using the contexts that Proto provides.

[note `proto::eval()` is a less powerful but easier-to-use evaluation technique
than Proto transforms, which are covered later. Although very powerful,
transforms have a steep learning curve and can be more difficult to debug.
`proto::eval()` is a rather weak tree traversal algorithm. Dan Marsden has
been working on a more general and powerful tree traversal library. When it is
ready, I anticipate that it will eliminate the need for `proto::eval()`.]

[/================================================================]
[section:proto_eval Evaluating an Expression with [^proto::eval()]]
[/================================================================]

[:[*Synopsis:]]

    namespace proto
    {
        namespace result_of
        {
            // A metafunction for calculating the return
            // type of proto::eval() given certain Expr
            // and Context types.
            template<typename Expr, typename Context>
            struct eval
            {
                typedef
                    typename Context::template eval<Expr>::result_type
                type;
            };
        }

        namespace functional
        {
            // A callable function object type for evaluating
            // a Proto expression with a certain context.
            struct eval : callable
            {
                template<typename Sig>
                struct result;

                template<typename Expr, typename Context>
                typename proto::result_of::eval<Expr, Context>::type
                operator ()(Expr &expr, Context &context) const;

                template<typename Expr, typename Context>
                typename proto::result_of::eval<Expr, Context>::type
                operator ()(Expr &expr, Context const &context) const;
            };
        }

        template<typename Expr, typename Context>
        typename proto::result_of::eval<Expr, Context>::type
        eval(Expr &expr, Context &context);

        template<typename Expr, typename Context>
        typename proto::result_of::eval<Expr, Context>::type
        eval(Expr &expr, Context const &context);
    }

Given an expression and an evaluation context, using _eval_ is quite simple.
Simply pass the expression and the context to _eval_ and it does the rest and
returns the result. You can use the `eval<>` metafunction in the
`proto::result_of` namespace to compute the return type of _eval_. The
following demonstrates a use of _eval_:

    template<typename Expr>
    typename proto::result_of::eval<Expr const, MyContext>::type
    MyEvaluate(Expr const &expr)
    {
        // Some user-defined context type
        MyContext ctx;

        // Evaluate an expression with the context
        return proto::eval(expr, ctx);
    }

What _eval_ does is also very simple. It defers most of the work to the
context itself. Here essentially is the implementation of _eval_:

    // eval() dispatches to a nested "eval<>" function
    // object within the Context:
    template<typename Expr, typename Context>
    typename Context::template eval<Expr>::result_type
    eval(Expr &expr, Context &ctx)
    {
        typename Context::template eval<Expr> eval_fun;
        return eval_fun(expr, ctx);
    }

Really, _eval_ is nothing more than a thin wrapper that dispatches to the
appropriate handler within the context class. In the next section, we'll see
how to implement a context class from scratch.

[endsect]

[/==============================================]
[section:contexts Defining an Evaluation Context]
[/==============================================]

As we saw in the previous section, there is really not much to the _eval_
function. Rather, all the interesting expression evaluation goes on within
a context class. This section shows how to implement one from scratch.

All context classes have roughly the following form:

    // A prototypical user-defined context.
    struct MyContext
    {
        // A nested eval<> class template
        template<
            typename Expr
          , typename Tag = typename proto::tag_of<Expr>::type
        >
        struct eval;

        // Handle terminal nodes here...
        template<typename Expr>
        struct eval<Expr, proto::tag::terminal>
        {
            // Must have a nested result_type typedef.
            typedef ... result_type;

            // Must have a function call operator that takes
            // an expression and the context.
            result_type operator()(Expr &expr, MyContext &ctx) const
            {
                return ...;
            }
        };

        // ... other specializations of struct eval<> ...
    };

Context classes are nothing more than a collection of specializations of a
nested `eval<>` class template. Each specialization handles a different
expression type.

In the [link boost_proto.users_guide.hello_calculator Hello Calculator]
section, we saw an example of a user-defined context class for evaluating
calculator expressions. That context class was implemented with the help
of Proto's _callable_context_. If we were to implement it from scratch, it
would look something like this:

    // The calculator_context from the "Hello Calculator" section,
    // implemented from scratch.
    struct calculator_context
    {
        // The values with which we'll replace the placeholders
        std::vector<double> args;

        template<
            typename Expr
            // defaulted template parameters, so we can
            // specialize on the expressions that need
            // special handling.
          , typename Tag = typename proto::tag_of<Expr>::type
          , typename Arg0 = typename proto::child_c<Expr, 0>::type
        >
        struct eval;

        // Handle placeholder terminals here...
        template<typename Expr, int I>
        struct eval<Expr, proto::tag::terminal, placeholder<I> >
        {
            typedef double result_type;

            result_type operator()(Expr &, MyContext &ctx) const
            {
                return ctx.args[I];
            }
        };

        // Handle other terminals here...
        template<typename Expr, typename Arg0>
        struct eval<Expr, proto::tag::terminal, Arg0>
        {
            typedef double result_type;

            result_type operator()(Expr &expr, MyContext &) const
            {
                return proto::child(expr);
            }
        };

        // Handle addition here...
        template<typename Expr, typename Arg0>
        struct eval<Expr, proto::tag::plus, Arg0>
        {
            typedef double result_type;

            result_type operator()(Expr &expr, MyContext &ctx) const
            {
                return proto::eval(proto::left(expr), ctx)
                     + proto::eval(proto::right(expr), ctx);
            }
        };

        // ... other eval<> specializations for other node types ...
    };

Now we can use _eval_ with the context class above to evaluate calculator
expressions as follows:

    // Evaluate an expression with a calculator_context
    calculator_context ctx;
    ctx.args.push_back(5);
    ctx.args.push_back(6);
    double d = proto::eval(_1 + _2, ctx);
    assert(11 == d);

Defining a context from scratch this way is tedious and verbose, but it gives
you complete control over how the expression is evaluated. The context class in
the [link boost_proto.users_guide.hello_calculator Hello Calculator] example
was much simpler. In the next section we'll see the helper class Proto provides
to ease the job of implementing context classes.

[endsect]

[/================================================]
[section:canned_contexts Proto's Built-In Contexts]
[/================================================]

Proto provides some ready-made context classes that you can use as-is, or that
you can use to help while implementing your own contexts. They are:

[variablelist
  [ [[link boost_proto.users_guide.expression_evaluation.canned_contexts.default_context [^default_context]]]
    [An evaluation context that assigns the usual C++ meanings to all the
     operators. For example, addition nodes are handled by evaluating the
     left and right children and then adding the results. The _default_context_
     uses Boost.Typeof to deduce the types of the expressions it evaluates.] ]
  [ [[link boost_proto.users_guide.expression_evaluation.canned_contexts.null_context [^null_context]]]
    [A simple context that recursively evaluates children but does not combine
     the results in any way and returns void.] ]
  [ [[link boost_proto.users_guide.expression_evaluation.canned_contexts.callable_context [^callable_context<>]]]
    [A helper that simplifies the job of writing context classes. Rather than