Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Transforming the Expression Tree
PrevUpHomeNext

This example will show how to write Actions that transform the Phoenix AST.

"Lisp macros transform the program structure itself, with the full language available to express such transformations."

Wikipedia

What we want to do is to invert some arithmetic operators, i.e. plus will be transformed to minus, minus to plus, multiplication to division and division to multiplication.

Let's start with defining our default action:

struct invert_actions
{
    template <typename Rule>
    struct when
        : proto::nary_expr
              proto::_
            , proto::vararg
                  proto::when<proto::_, phoenix::evaluator(proto::_, phoenix::_context)
              >
          >
    {};
};

Wow, this looks complicated! Granted you need to know a little bit about Boost.Proto (For a good introduction read through the Expressive C++ series).

By default, we don't want to do anything, well, not exactly nothing, but just continue transformation into its arguments.

So, it is done by the following:

  • For each arguments are passed to evaluator (with the current context, that contains our invert_actions)
  • Create new expression using current expression tag, what is done by proto::_, with the result of evaluated arguments

So, after the basics are set up, we can start by writing the transformations we want to have on our tree:

// Transform plus to minus
template <>
struct invert_actions::when<phoenix::rule::plus>
    : proto::call<
        proto::functional::make_expr<proto::tag::minus>(
            phoenix::evaluator(proto::_left, phoenix::_context)
          , phoenix::evaluator(proto::_right, phoenix::_context)
        )
    >
{};

What is done is the following:

  • The left expression is passed to evaluator (with the current context, that contains our invert_actions)
  • The right expression is passed to evaluator (with the current context, that contains our invert_actions)
  • The result of these two Proto Transforms are passed to proto::functional::make_expr which returns the freshly created expression

After you know what is going on, maybe the rest doesn't look so scary anymore:

// Transform minus to plus
template <>
struct invert_actions::when<phoenix::rule::minus>
    : proto::call<
        proto::functional::make_expr<proto::tag::plus>(
            phoenix::evaluator(proto::_left, phoenix::_context)
          , phoenix::evaluator(proto::_right, phoenix::_context)
        )
    >
{};

// Transform multiplies to divides
template <>
struct invert_actions::when<phoenix::rule::multiplies>
    : proto::call<
        proto::functional::make_expr<proto::tag::divides>(
            phoenix::evaluator(proto::_left, phoenix::_context)
          , phoenix::evaluator(proto::_right, phoenix::_context)
        )
    >
{};

// Transform divides to multiplies
template <>
struct invert_actions::when<phoenix::rule::divides>
    : proto::call<
        proto::functional::make_expr<proto::tag::multiplies>(
            phoenix::evaluator(proto::_left, phoenix::_context)
          , phoenix::evaluator(proto::_right, phoenix::_context)
        )
    >
{};

That's it! Now that we have our actions defined, we want to evaluate some of our expressions with them:

template <typename Expr>
// Calculate the result type: our transformed AST
typename boost::result_of<
    phoenix::evaluator(
        Expr const&
      , phoenix::result_of::context<int, invert_actions>::type
    )
>::type
invert(Expr const & expr)
{
    return
        // Evaluate it with our actions
        phoenix::eval(
            expr
          , phoenix::context(
                int()
              , invert_actions()
            )
        );
}

Run some tests to see if it is working:

invert(_1);                    // --> _1
invert(_1 + _2);               // --> _1 - _2
invert(_1 + _2 - _3);          // --> _1 - _2 + _3
invert(_1 * _2);               // --> _1 / _2
invert(_1 * _2 / _3);          // --> _1 / _2 * _3
invert(_1 * _2 + _3);          // --> _1 / _2 - _3
invert(_1 * _2 - _3);          // --> _1 / _2 + _2
invert(if_(_1 * _4)[_2 - _3]); // --> if_(_1 / _4)[_2 + _3]
_1 * invert(_2 - _3));         // --> _1 * _2 + _3

The complete example can be found here: example/invert.cpp

Pretty simple ...


PrevUpHomeNext