Transformations in Boost.YAP are done using the transform() function.

Let's take another look at the example expression from the intro:

Consider a call to transform(), operating on that expression:

auto result = boost::yap::transform(expr, xform);

Boost.YAP's transform() first looks at the top level expression, which in this case is a + expression. If the transform object xform matches the + expression, transform() is done; it just returns xform(expr). If xform does not match the + expression, transform() transforms all its operands (which for operator+() is just the left and right operands), and returns a new + expression with those transformed operands. What I mean by "match" is covered in detail below.

The overall effect of this is that transform() effectively copies an expr node that does not match xform, and returns a transformed node for an expr node that does match xform.

transform() can also take multiple transform objects. If you call it with N transform objects, it will attempt to match each of the N transforms to a given expression, one at a time and in their given order. Only if no transform matches an expression does the copy-and-recurse behavior kick in.

One common result of calling transform() is that you create a copy of expr, with a few matching nodes transformed. But this does not have to be the result of calling transform(), because a Boost.YAP transformation is free-form; it must return a value, but may do just about anything else. It can transform an expression into anything — a new expression of any kind, or even a non-expression value (effectively evaluating the expression). As before, here is the get_arity transform from the Calc3 example. It returns a value, not an Expression:

struct get_arity
{
    // Base case 1: Match a placeholder terminal, and return its arity as the
    // result.
    template <long long I>
    boost::hana::llong<I> operator() (boost::yap::expr_tag<boost::yap::expr_kind::terminal>,
                                      boost::yap::placeholder<I>)
    { return boost::hana::llong_c<I>; }

    // Base case 2: Match any other terminal.  Return 0; non-placeholders do
    // not contribute to arity.
    template <typename T>
    auto operator() (boost::yap::expr_tag<boost::yap::expr_kind::terminal>, T &&)
    {
        using namespace boost::hana::literals;
        return 0_c;
    }

    // Recursive case: Match any expression not covered above, and return the
    // maximum of its children's arities.
    template <boost::yap::expr_kind Kind, typename... Arg>
    auto operator() (boost::yap::expr_tag<Kind>, Arg &&... arg)
    {
        return boost::hana::maximum(
            boost::hana::make_tuple(
                boost::yap::transform(
                    boost::yap::as_expr(std::forward<Arg>(arg)),
                    get_arity{}
                )...
            )
        );
    }
};

Also, note that in this case the transform is stateless, but you could also give your transform objects data members containing contextual state:

struct take_nth
{
    template <typename T>
    auto operator() (boost::yap::expr_tag<boost::yap::expr_kind::terminal>,
                     std::vector<T> const & vec)
    { return boost::yap::make_terminal(vec[n]); }

    std::size_t n;
};

When transform() Recurses

As described above, transform() only recurses when it does not find a match. This means that if you want to transform a nonterminal, say an expr_kind::call expression we'll call C, and also C's subexpressions, you must explicitly call transform() yourself in your transform that matches C. You can see this kind of explicit transform() call in the recursive case of get_arity in the example code above.

Transform Matching

In Boost.YAP a Transform is a Callable that has zero or more overloads that model the ExpressionTransform or TagTransform concepts.

An ExpressionTransform overload takes a single parameter whose type is the expression to be transformed. Here's one from a transform object in the Future Group example:

// Transform left || right -> transform(left).
template <typename T, typename U>
auto operator() (
    future_expr<
        boost::yap::expr_kind::logical_or,
        boost::hana::tuple<T, U>
    > const & or_expr
) {
    // Recursively transform the left side, and return the result.
    // Without the recursion, we might return a terminal expression here
    // insead of a tuple.
    return boost::yap::transform(boost::yap::left(or_expr), *this);
}

ExpressionTransforms are most useful when you want to transform a narrow set of expression types (perhaps only one). In particular, you can distinguish between const and non-const, reference and non-reference, etc., in the expression and its operands in a way that you have less control over with the other kind of transform.

A TagTransform overload takes a tag that indicates the expr_kind of the expression to be transformed, and then (loosely) the value of each operand of the expression to be transformed. This looseness prevents you from needing to write out the full type of the matched expression. Here's one from the Pipable Algorithms example:

template<typename Range>
auto operator()(
    boost::yap::expr_tag<boost::yap::expr_kind::call>,
    algorithm_t a,
    Range & r)
{
    return call_algorithm(a, r);
}

TagTransforms are most useful when the transform needs to match an expression without regard to whether its operands are expr_kind::expr_ref expressions, or — if they are terminals — whether they contain or refer to their values. TagTransforms tend to be far more concise.

A More Rigorous Description of TagTransform Parameters

That "(loosely)" before probably bothered you, right? Me too. Each non-tag parameter is passed to a TagTransform by calling an operand accessor appropriate to expr's kind, and then calling a terminal-specific version of value() (terminal_value()) on the result. For example, consider a plus expression expr. The TagTransform on a transform object xform would be called like this:

xform(plus_tag, terminal_value(left(expr)), terminal_value(right(expr)))

The operand accessors (left() and right() in this example) all dereference expr_kind::expr_ref expressions before operating on them, and terminal_value() does the same.

terminal_value() works much like value(), except that it does not take the value of a nonterminal unary expression; it just forwards a nonterminal through. It still takes values out of terminals and unwraps expr_kind::expr_ref expressions, though.

The auto-unwrapping of terminals means that you can effectively ignore the presence of expr_kind::expr_ref expressions when writing a TagTransform. You can also just deal with the values inside terminals, and not the terminals themselves. Also, you can match all terminal value qualifiers (const or not, lvalue or rvalue) uniformly with a T const & parameter. Finally, you can write TagTransform parameter types that can catch conversions; for instance, you can match any negation expression containing a terminal, or a reference to one, containing a value convertible to double like this:

struct xform
{
    auto operator() (boost::yap::negate_tag, double x)
    { return /* ... */; }
}

That will match a negation of a terminal containing an unsigned int, unsigned int &, int const &, float &&, etc. It will also match a negation of a reference to such a terminal.

Mixing the Two Kinds of Transforms

You can have two overloads in your transform that match an expression, one an ExpressionTransform and one a TagTransform, and there will not be any ambiguity. The TagTransform is matched first, and the ExpressionTransform is matched only if the TagTransform did not. You don't have to worry about ambiguity, but save yourself some confusion and mix the two kinds of overloads as little as possible.

Multiple Transform Objects

In the case that multiple transform objects are being used in transform(), the above logic applies to each one independently before the next one is used. In other words, in the call boost::yap::transform(expr, a, b), transform() tries to match any TagTransform from a to an expression first, then any ExpressionTransform from a, then any TagTransform from b, and finally any ExpressionTransform from b.

YAP-Supplied Transforms

Boost.YAP comes with a couple of functions that return ready-made transforms, replacements() and evaluation().

The transforms returned by replacements() replace only placeholder terminals. Placeholder I is replaced by the I-1-th argument passed to replacements(). Placeholders are 1-based for consistency with other Boost and std placeholders.

There are also a couple of specialty transform functions, replace_placeholders() and evaluate(). These are convenience functions that just call transform() on an expression using replacements() or evaluation() as the transform, respectively.

The behavior of evaluation() is covered in the next section, Evaluating Expressions.