back_end.qbk

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

    // just like the expression it wraps, but with extra operator()
    // member functions that evaluate the expression.
    //   NEW: Use the CalcArity grammar to ensure that the correct
    //   number of arguments are supplied.
    template<typename Expr>
    struct calculator
      : proto::extends<Expr, calculator<Expr>, calculator_domain>
    {
        typedef
            proto::extends<Expr, calculator<Expr>, calculator_domain>
        base_type;

        calculator(Expr const &expr = Expr())
          : base_type(expr)
        {}

        typedef double result_type;

        // Use CalcArity to compute the arity of Expr: 
        static int const arity = boost::result_of<CalcArity(Expr)>::type::value;

        double operator()() const
        {
            BOOST_MPL_ASSERT_RELATION(0, ==, arity);
            calculator_context ctx;
            return proto::eval(*this, ctx);
        }

        double operator()(double a1) const
        {
            BOOST_MPL_ASSERT_RELATION(1, ==, arity);
            calculator_context ctx;
            ctx.args.push_back(a1);
            return proto::eval(*this, ctx);
        }

        double operator()(double a1, double a2) const
        {
            BOOST_MPL_ASSERT_RELATION(2, ==, arity);
            calculator_context ctx;
            ctx.args.push_back(a1);
            ctx.args.push_back(a2);
            return proto::eval(*this, ctx);
        }
    };

Note the use of `boost::result_of<>` to access the return type of the `CalcArity` function object. Since we used compile-time integers in our transforms, the arity of the expression is encoded in the return type of the `CalcArity` function object. Proto grammars are valid TR1-style function objects, so you can use `boost::result_of<>` to figure out their return types.

With our compile-time assertions in place, when users provide too many or too few arguments to a calculator expression, as in:

    (_2 * _2)(42); // Oops, too few arguments!

... they will get a compile-time error message on the line with the assertion that reads something like this[footnote This error message was generated with Microsoft Visual C++ 9.0. Different compilers will emit different messages with varying degrees of readability.]:

[pre
c:\boost\org\trunk\libs\proto\scratch\main.cpp(97) : error C2664: 'boost::mpl::asse
rtion\_failed' : cannot convert parameter 1 from 'boost::mpl::failed \*\*\*\*\*\*\*\*\*\*\*\*boo
st::mpl::assert\_relation<x,y,\_\_formal>::\*\*\*\*\*\*\*\*\*\*\*\*' to 'boost::mpl::assert<false>
::type'
   with
   \[
       x\=1,
       y\=2,
       \_\_formal\=bool boost::mpl::operator\=\=(boost::mpl::failed,boost::mpl::failed)
   \]
]

The point of this exercise was to show that we can write a fairly simple Proto grammar with embedded transforms that is declarative and readable and can compute interesting properties of arbitrarily complicated expressions. But transforms can do more than that. Boost.Xpressive uses transforms to turn expressions into finite state automata for matching regular expressions, and Boost.Spirit uses transforms to build recursive descent parser generators. Proto comes with a collection of built-in transforms that you can use to perform very sophisticated expression manipulations like these. In the next few sections we'll see some of them in action.

[endsect]

[/===============================================]
[section:state Transforms With State Accumulation]
[/===============================================]

So far, we've only seen examples of grammars with transforms that accept one argument: the expression to transform. But consider for a moment how, in ordinary procedural code, you would turn a binary tree into a linked list. You would start with an empty list. Then, you would recursively convert the right branch to a list, and use the result as the initial state while converting the left branch to a list. That is, you would need a function that takes two parameters: the current node and the list so far. These sorts of /accumulation/ problems are quite common when processing trees. The linked list is an example of an accumulation variable or /state/. Each iteration of the algorithm takes the current element and state, applies some binary function to the two and creates a new state. In the STL, this algorithm is called `std::accumulate()`. In many other languages, it is called /fold/. Let's see how to implement a fold algorithm with Proto transforms.

All Proto grammars can optionally accept a state parameter in addition to the expression to transform. If you want to fold a tree to a list, you'll need to make use of the state parameter to pass around the list you've built so far. As for the list, the Boost.Fusion library provides a `fusion::cons<>` type from which you can build heterogeneous lists. The type `fusion::nil` represents an empty list. 

Below is a grammar that recognizes output expressions like `cout_ << 42 << '\n'` and puts the arguments into a Fusion list. It is explained below.

    // Fold the terminals in output statements like
    // "cout_ << 42 << '\n'" into a Fusion cons-list.
    struct FoldToList
      : proto::or_<
            // Don't add the ostream terminal to the list
            proto::when<
                proto::terminal< std::ostream & >
              , proto::_state
            >
            // Put all other terminals at the head of the
            // list that we're building in the "state" parameter
          , proto::when<
                proto::terminal<_>
              , fusion::cons<proto::_value, proto::_state>(
                    proto::_value, proto::_state
                )
            >
            // For left-shift operations, first fold the right
            // child to a list using the current state. Use
            // the result as the state parameter when folding
            // the left child to a list.
          , proto::when<
                proto::shift_left<FoldToList, FoldToList>
              , FoldToList(
                    proto::_left
                  , FoldToList(proto::_right, proto::_state)
                )
            >
        >
    {};

Before reading on, see if you can apply what you know already about object, callable and primitive transforms to figure out how this grammar works.

When you use the `FoldToList` function, you'll need to pass two arguments: the expression to fold, and the initial state: an empty list. Those two arguments get passed around to each transform. We learned previously that `proto::_value` is a primitive transform that accepts a terminal expression and extracts its value. What we didn't know until now was that it also accepts the current state /and ignores it/. `proto::_state` is also a primitive transform. It accepts the current expression, which it ignores, and the current state, which it returns.

When we find a terminal, we stick it at the head of the cons list, using the current state as the tail of the list. (The first alternate causes the `ostream` to be skipped. We don't want `cout` in the list.) When we find a shift-left node, we apply the following transform:

    // Fold the right child and use the result as
    // state while folding the right.
    FoldToList(
        proto::_left
      , FoldToList(proto::_right, proto::_state)
    )

You can read this transform as follows: using the current state, fold the right child to a list. Use the new list as the state while folding the left child to a list.

[tip If your compiler is Microsoft Visual C++, you'll find that the above transform does not compile. The compiler has bugs with its handling of nested function types. You can work around the bug by wrapping the inner transform in `proto::call<>` as follows:

``
    FoldToList(
        proto::_left
      , proto::call<FoldToList(proto::_right, proto::_state)>
    )
``

`proto::call<>` turns a callable transform into a primitive transform, but more on that later.
]

Now that we have defined the `FoldToList` function object, we can use it to turn output expressions into lists as follows:

    proto::terminal<std::ostream &>::type const cout_ = {std::cout};

    // This is the type of the list we build below
    typedef
        fusion::cons<
            int
          , fusion::cons<
                double
              , fusion::cons<
                    char
                  , fusion::nil
                >
            >
        >
    result_type;

    // Fold an output expression into a Fusion list, using
    // fusion::nil as the initial state of the transformation.
    FoldToList to_list;
    result_type args = to_list(cout_ << 1 << 3.14 << '\n', fusion::nil());

    // Now "args" is the list: {1, 3.14, '\n'}

When writing transforms, "fold" is such a basic operation that Proto provides a number of built-in fold transforms. We'll get to them later. For now, rest assured that you won't always have to stretch your brain so far to do such basic things.

[endsect]

[/================================================]
[section:data Passing Auxiliary Data to Transforms]
[/================================================]

In the last section, we saw that we can pass a second parameter to grammars with transforms: an accumulation variable or /state/ that gets updated as your transform executes. There are times when your transforms will need to access auxiliary data that does /not/ accumulate, so bundling it with the state parameter is impractical. Instead, you can pass auxiliary data as a third parameter, known as the /data/ parameter. Below we show an example involving string processing where the data parameter is essential.

[note All Proto grammars are function objects that take one, two or three arguments: the expression, the state, and the data. There are no additional arguments to know about, we promise. In Haskell, there is set of tree traversal technologies known collectively as _SYB_. In that framework, there are also three parameters: the term, the accumulator, and the context. These are Proto's expression, state and data parameters under different names.]

Expression templates are often used as an optimization to eliminate temporary objects. Consider the problem of string concatenation: a series of concatenations would result in the needless creation of temporary strings. We can use Proto to make string concatenation very efficient. To make the problem more interesting, we can apply a locale-sensitive transformation to each character during the concatenation. The locale information will be passed as the data parameter.

Consider the following expression template:

    proto::lit("hello") + " " + "world";

We would like to concatenate this string into a statically allocated wide character buffer, widening each character in turn using the specified locale. The first step is to write a grammar that describes this expression, with transforms that calculate the total string length. Here it is:

    // A grammar that matches string concatenation expressions, and
    // a transform that calculates the total string length.
    struct StringLength
      : proto::or_<
            proto::when<
                // When you find a character array ...
                proto::terminal<char[proto::N]>
                // ... the length is the size of the array minus 1.
              , mpl::prior<mpl::sizeof_<proto::_value> >()
            >
          , proto::when<
                // The length of a concatenated string is ...
                proto::plus<StringLength, StringLength>
                // ... the sum of the lengths of each sub-string.
              , proto::fold<
                    _
                  , mpl::size_t<0>()
                  , mpl::plus<StringLength, proto::_state>()
                >
            >
        >
    {};

Notice the use of _fold_pt_. It is a primitive transform that takes a sequence, a state, and function, just like `std::accumulate()`. The three template parameters are transforms. The first yields the sequence of expressions over which to fold, the second yields the initial state of the fold, and the third is the function to apply at each iteration. The use of `proto::_` as the first parameter might have you confused. In addition to being Proto's wildcard, `proto::_` is also a primitive transform that returns the current expression, which (if it is a non-terminal) is a sequence of its child expressions.

Next, we need a function object that accepts a narrow string, a wide character buffer, and a `std::ctype<>` facet for doing the locale-specific stuff. It's fairly straightforward.

    // A function object that writes a narrow string
    // into a wide buffer.
    struct WidenCopy : proto::callable
    {
        typedef wchar_t *result_type;

        wchar_t *
        operator()(char const *str, wchar_t *buf, std::ctype<char> const &ct) const
        {
            for(; *str; ++str, ++buf)
                *buf = ct.widen(*str);
            return buf;
        }
    };

Finally, we need some transforms that actually walk the concatenated string expression, widens the characters and writes them to a buffer. We will pass a `wchar_t*` as the state parameter and update it as we go. We'll also pass the `std::ctype<>` facet as the data parameter. It looks like this:

    // Write concatenated strings into a buffer, widening
    // them as we go.
    struct StringCopy
      : proto::or_<
            proto::when<
                proto::terminal<char[proto::N]>
              , WidenCopy(proto::_value, proto::_state, proto::_data)
            >
          , proto::when<
                proto::plus<StringCopy, StringCopy>
              , StringCopy(
                    proto::_right
                  , StringCopy(proto::_left, proto::_state, proto::_data)
                  , proto::_data
                )
            >
        >
    {};

Let's look more closely at the transform associated with non-terminals:

    StringCopy(
        proto::_right
      , StringCopy(proto::_left, proto::_state, proto::_data)
      , proto::_data
    )

This bears a resemblance to the transform in the previous section that folded an expression tree into a list. First we recurse on the left child, writing its strings into the `wchar_t*` passed in as the state parameter. That returns the new value of the `wchar_t*`, which is passed as state while transforming the right child. Both invocations receive the same `std::ctype<>`, which is passed in as the data parameter.

With these pieces in our pocket, we can implement our concatenate-and-widen function as follows:

    template<typename Expr>
    void widen( Expr const &expr )
    {
        // Make sure the expression conforms to our grammar
        BOOST_MPL_ASSERT(( proto::matches<Expr, StringLength> ));

        // Calculate the length of the string and allocate a buffer statically
        static std::size_t const length =
            boost::result_of<StringLength(Expr)>::type::value;
        wchar_t buffer[ length + 1 ] = {L'\0'};

        // Get the current ctype facet
        std::locale loc;