yap/doc/tutorial.qbk

[section Expressions]

_yap_ consists of expressions and functions that operate on them.  Any type
that models the _Expr_ concept will work with any of the functions in _yap_
that takes an expression.

For a type `T` to model the _Expr_ concept, `T` must contain at least an
_kind_ (terminal, plus-operation, etc.) and a _tuple_ of values.  That's it.
This means that user-defined templates modeling _ExprTmpl_ are very
straightforward to make.

[note The _tuple_ of values is also constrained, based on the kind of the
expression; see the full _Expr_ documentation for details.]

Here's an example:

[minimal_template]

That's a template that models _ExprTmpl_.  Instantiated with the proper
template parameters, it produces _Exprs_.

Ok, so it's not that interesting by itself _emdash_ it has no operators.  But
we can still use it with the _yap_ functions that take an _Expr_.  Let's make
a plus-expression manually:

[minimal_template_manual_construction]

If we evaluate it using _eval_, it does what you would expect:

[minimal_template_evaluation]

[note There is a reference model of the _ExprTmpl_ concept that comes with _yap_:
_expr_.  It has all the member operators defined, and the nonmember operators
and the `if_else` pseudo-operator are defined in their respective headers.

_expr_ is great for prototyping, and for quick-and-dirty uses of _ets_, but
its use of every single operator makes it a suboptimal choice for most use
cases.]

[note Because _yap_ operates on _Exprs_, it is possible to mix and match
_Exprs_ that are instantiations of different templates.  Let's say we have a
_yap_ expression `E` that contains an _expr_ subexpression `s0` and
subexpressions instantiated from N other _ExprTmpls_ `s1`..`sN`.  `E` can be
passed as an argument to any _yap_ function that accepts a _Expr_ parameter
(this last _Expr_ is the concept, not the template).]

One more thing.  It is important to remember that _yap_ expressions are
all-lazy, all the time.  There is no auto-evaluation of a _yap_ expression
like there is with normal C++ expressions.  If you want your expressions to be
evaluated, you must call _eval_, or define non-lazy operations that force
evaluation where and when you want it.  This last approach is usually the
right one, and there are lots of examples of how to do this in the _examples_
section.  In particular, checkout the _lazy_vector_ and _tarray_ examples.

[endsect]


[section Kinds of Expressions]

There are three special kinds of expressions.

Most of the expression kinds are the overloadable operators (`operator+()`,
operator<<=()`, etc.), See _kind_ for the full list.

[variablelist Special Expression Kinds
    [[_terminal_] [A terminal contains a non-Expression value, and represents a leaf-node in an
expression tree.  A terminal may have a _placeholder_ value, in which case it acts as a placeholder. ]]
    [[_if_else_] [An `if_else` expression is analogous to the C++ ternary operator (`?:`), but
without the common-type conversion logic.  `if_else` doesn't check that the alternatives are compatible or interconvertible; that's up to you.]]
    [[_expr_ref_] [An `expr_ref` expression is one that acts as a (possibly `const`) lvalue reference to another expression.  It exists to prevent unnecessary copies of expressions.]]
]

[endsect]


[section Operators]

Let's see an expression template type with some operators:

[lazy_vector_decl]

Those macros are used to define operator overloads that return _Exprs_.  As
shown here, that sort of operator can be mixed with normal, non-lazy ones.

Use of the macros is not necessary (you can write your own operators that
return _Exprs_ if you like), but it is suitable 99% of the time.

Making the operators easy to define like this allows you to define custom
expression templates that have only the operators defined that are appropriate
for your use case.

Detailed documentation can be found later in the _operator_macros_ section.

[endsect]


[section Transforming Expressions]

Explicit transformations are the preferred way to work in _yap_.  They are
done using the _xform_ function.  See _calc3_ for an extended example.

Here's how _xform_ works.  Consider this call to _xform_:

    auto result = transform(expr, xform);

`result` is created by visiting each node in `expr`, in top-down,
depth-first order.  For one such node `N`, we compute a value that will be
placed into `result` at the corresponding place in `result`.  If `xform(N)` is
a well-formed C++ expression, that `xform(N)` is used, and no nodes under `N`
in `expr` are visited.  Otherwise, `N` is used, and visitation of nodes in
`expr` continues below `N`.

[note The code you write with _yap_ is likely going to be very generic,
especially when you're writing a transform.  To make transforms play nicer
with generic code, _xform_ `std::forward`s-through anything you give it that
is not a _yap_ expression.  In other words, it returns any non-_yap_ argument
completely unchanged.  In situations when you want to make sure that a
parameter you pass to _xform_ is always a _yap_ expression, use the _as_expr_
function.]

One common result of calling _xform_ is that you create a copy of `expr`, with
a few matching nodes transformed.  Note the use of "common"; transforms don't
always work out that way.

A _yap_ transformation is free-form; it must return a value, but may do just
about anything else.  It can transform an expression into anything _emdash_ a
new expression of any kind, or even a non-expression value (effectively
evaluating the expression).  For example, here is the `get_arity` transform
from the _calc3_ example:

[calc3_get_arity_xform]

Note there are a couple of different forms that _yap_ accepts for function
signatures on a transform.  In the example above, we use both the tag form and
the expression form.  There's a fuller explanation of how _yap_ matches
expressions to transform calls in [link
boost_yap__proposed_.manual.transform_matching Transform Matching].

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

[vector_take_nth_xform]

[tip Often when you create an expression, you will want to evaluate it in
different contexts, changing its evaluation _emdash_ or even entire meaning
_emdash_ in each context.  _eval_ is wrong for this task, since it only takes
values for substitution into placeholders.  In these situations, you should
instead use an explicit transform that evaluates your expression.]

[endsect]


[section Evaluating Expressions]

_yap_ expressions are evaluated explicitly _emdash_ _yap_ expressions are
explicitly evaluated by calling the _eval_ function.

[endsect]


[section Operator Macros]

There are macros that define binary operators as members and macros that
define them as nonmembers.  (If you got here without reading the _operators_
section, go read that first.)  For a given operator, the member-defining macro
will define an operator that accepts anything on the right (making a terminal
out of a non-_Expr_ operand); the nonmember-defining macro will define an
operator that will only accept a non-_Expr_ on the left and an _Expr_ on the
right.  This is to avoid creating ambiguous overload sets.  Here are the
macros and their uses:

[table Unary and Binary Operator-Defining Macros
    [[Macro] [Use] [First/Left Operand Type] [Right Operand Type] [Notes]]

    [[_unary_member_m_] [Unary member operators.] [`decltype(*this)`, an _Expr_.] [--] []]
    [[_binary_member_m_] [Binary member operators.] [`decltype(*this)`, an _Expr_.] [Any type.] []]
    [[_binary_free_m_] [Binary free operators.] [Any non-_Expr_.] [Any _Expr_.] []]
    [[_udt_unary_m_] [Free operators defined over non-_Expr_ types constrained by a type trait (e.g. all `std::map<>`s).] [Any non-_Expr_ that satisfies the given type trait.] [--] []]
    [[_udt_udt_binary_m_] [Free operators defined over non-_Expr_ types constrained by a pair of type traits (e.g. a `std::map<>` on the left, and a `std::vector<>` on the right).  Useful for type-asymmetric operators.] [Any non-_Expr_ that satisfies the left-hand type trait.] [Any non-_Expr_ that satisfies the right-hand type trait.] []]
    [[_udt_any_binary_m_] [Free operators defined over pairs of non-_Expr_ types, one constrained by a type trait and one not (e.g. a `std::list<>` on either side, and anything on the other).] [Any non-_Expr_.] [--] [At least one parameter must satisfy the given type trait.]]
]

[table The Other Operator-Defining Macros
    [[Macro] [Use] [Operands] [Notes]]

    [[_member_call_m_] [Member call operator.] [Any type.] []]
    [[_expr_if_else_m_] [Free `if_else()` function that requires at least one parameter to be an expression.] [Any type.] [At least one parameter must be an _Expr_.]]
    [[_udt_any_if_else_m_] [Free `if_else()` function for non-_Expr_ types that requires at least one parameter to satisfy the given type trait.] [Any non-_Expr_.] [At least one parameter must satisfy the given type trait.]]
]

[note Operands are handled in a uniform way across all functions defined by
all the macros listed here.  See _how_treated_ for details.]

[endsect]


[section How Expression Operands Are Treated]

For any _expr_ operator overload, or any function defined using one of the
function definition macros, operands are treated in a uniform way.

The guiding design principle here is that an expression built using _yap_
should match the semantics of a builtin C++ expression as closely as possible.
This implies that an rvalue be treated as if it were a temporary (as it may in
fact have initially been) throughout the building and transformation of an
expression, and that an lvalue should retain its connection to the underlying
named entity to which it refers.

For example, if you see

    auto expr = a + 1;

you should expect that `a` will be an lvalue reference to some object of type
`decltype(a)`, regardless of whether `a` is an _Expr_ or a builtin type.
Similarly, you should expect the `1` to be an rvalue, whether wrapped in a
terminal or not.

Let's take a quick look at _make_term_.  If you call it with a `T` rvalue, the
terminal's value type is a `T`, and the rvalue gets moved into it.  If you
call it with a `T [const]` lvalue, the value type is `T [const] &`, and the
reference refers to the lvalue (read `[const]` as "possibly
`const`-qualified").  This is important because you might write through the
terminal later in an assignment operation.  You don't want to lose the ability
to do this, or be forced to write some Baroque pile of code to do so _emdash_
it should be natural and easy.

And it is:

[assign_through_terminal]

Now, there is a wrinkle.  _yap_'s lazy expressions can be built piecemeal:

    auto subexpr = boost::yap::make_terminal(1) + 2;
    // This is fine, and acts more-or-less as if you wrote "1 / (1 + 2)".
    auto expr = 1 / subexpr;

whereas C++'s eager builtin expressions cannot:

    auto subexpr = 1 + 2;    // Same as "int subexpr = 3;".  Hm.
    auto expr = 1 / subexpr; // Same as "int expr = 0;" Arg.

Ok, so since you can build these lazy _yap_ expressions up from
subexpressions, how do we treat the subexpressions?  We treat them in exactly
the same way as _make_term_ treats its parameter.  Rvalues are moved in, and
lvalues are captured by (possibly `const`) reference.

[note If you want to subvert the capture-by-reference semantics of using
subexpressions, just `std::move()` them.  That will force a move _emdash_ or
copy of values for which move is not defined.]

The capture-by-reference behavior is implemented via a special _kind_,
_expr_ref_.  An `expr_ref` expression has a single data element: a (possibly
`const` (Can I stop saying that every time?  You get it, right? Ok, good.))
reference to an expression.  This additional level of indirection causes some
complications at times, as you can see in the examples.  Fortunately, the
complications are not overly cumbersome.

So, given the rules so far, here is a comprehensive breakdown of what happens
when an operand is passed to a _yap_ operator.  In this table, `expr_tmpl` is an
_ExprTmpl_, and `T` is a non-_Expr_ type.  `E` refers to any non-`expr_ref`
_Expr_.  _yap_ does a partial decay on non-_Expr_ operands, in which `cv` and
reference qualifiers are left unchanged, but arrays are decayed to pointers
and functions are decayed to function pointers. `PARTIAL_DECAY(T)` indicates
such a partial decay of `T`.

[table Operand Handling
    [[Operand] [Captured As] [Notes]]

    [[`T const &`] [`expr_tmpl<expr_kind::terminal, boost::hana::tuple<PARTIAL_DECAY(T)>>`] []]
    [[`T &`] [`expr_tmpl<expr_kind::terminal, boost::hana::tuple<PARTIAL_DECAY(T)>>`] []]
    [[`T &&`] [`expr_tmpl<expr_kind::terminal, boost::hana::tuple<PARTIAL_DECAY(T)>>`] [Operand moved.]]

    [[`E const &`] [`expr_tmpl<expr_kind::expr_ref, boost::hana::tuple<E const &>>`] []]
    [[`E &`] [`expr_tmpl<expr_kind::expr_ref, boost::hana::tuple<E &>>`] []]
    [[`E &&`] [`E`] [Operand moved.]]

    [[`expr_tmpl<expr_kind::expr_ref, ...> const &`] [`expr_tmpl<expr_kind::expr_ref, ...>`] []]
    [[`expr_tmpl<expr_kind::expr_ref, ...> &`] [`expr_tmpl<expr_kind::expr_ref, ...>`] []]
    [[`expr_tmpl<expr_kind::expr_ref, ...> &&`] [`expr_tmpl<expr_kind::expr_ref, ...>`] [Operand moved.]]
]

The partial decay of non-_Expr_ operands is another example of how _yap_
attempts to create expression trees that are as semantically close to builtin
expressions as possible.

[endsect]


[section Transform Matching]

In _yap_ a _XForm_ is a _Callable_ that has *zero or more* overloads that
model the _ExprXForm_ or _TagXForm_ concepts.

An _ExprXForm_ overload takes the expression to be transformed:

[expr_xform]

_ExprXForms_ 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 _TagXForm_ overload takes a tag that indicates the _kind_ of the expression
to be transformed, and then (loosely) the value of each operand of the
expression to be transformed:

[tag_xform]

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

[heading A More Rigorous Description of TagTransform Parameters]

That "(loosely)" before probably bothered you, right?  Me too.  Each non-tag
parameter is passed to a _TagXForm_ 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 _TagXForm_ 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_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_ref_
expressions, though.

`terminal_value()` differs from _value_ in one important way, though.  If it
simply extracted values out of terminal expressions, there would be no way to
apply `terminal_tag` transforms uniformly.  Consider this evaluating
transform:

    struct xform
    {
        // This transform negates terminals.
        auto operator() (boost::yap::terminal_tag, double x)
        { return -x; }

        // This transform removes negations.
        auto operator() (boost::yap::negate_tag, double x)
        { return x; }
    }

Now consider what happens when we use the transform like this:

    auto expr = -boost::yap::make_terminal(9);
    std::cout << boost::yap::transform(expr, xform{}); // Applies both transforms; prints -9.

If `terminal_value()` did *not* automatically apply terminal transforms, this
would be the result:

    // Thankfully, TagTransforms do *not* work like this!
    auto term = boost::yap::make_terminal(9);
    std::cout << boost::yap::transform(term, xform{}); // Only applies the terminal_tag transform; prints -9.
    std::cout << boost::yap::transform(-term, xform{}); // Only applies the negate_tag transform; prints 9.

[tip _TagXForm_ is intended to be the more terse and automatic form.  If you
don't want auto-application of terminal transforms for a certain transform's
arguments, use an _ExprXForm_.]

All of this means that you can effectively ignore the presence of _expr_ref_
expressions when writing a _TagXForm_.  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 _TagXForm_ 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.

[heading Mixing the Two Kinds of Transforms]

You can have two overloads in your transform that match an expression, one an
_ExprXForm_ and one a _TagXForm_, and there will not be any ambiguity.  The
_TagXForm_ is preferred, except in the case of a call expression, in which case
the _ExprXForm_ is preferred.  I know, I know.  You don't have to worry about
ambiguity, but save yourself some confusion and mix the two kinds of overloads
as little as possible.

[note The above only applies when you have an _ExprXForm_ and a _TagXForm_
that match *the same expression type*.  Having unrelated _ExprXForms_ and
_TagXForms_ within the same transform object is often quite useful.]

[endsect]


[section Printing]

_yap_ has a convenient _print_ function, that prints an expression tree to a
stream.  It is not intended for production work (for instance, it has no
formatting options), but it is excellent for debugging and instrumentation.

Since it is only a debugging aid, _print_ is found in a separate header not
included when you include _yap_ with

    #include <boost/yap/yap.hpp>

You must include `<boost/yap/print.hpp>` explicitly.

_print_ handles several patterns of expression specially, to allow a concise
representation of a given expression tree.  For example, given this
definition:

[print_decl]

and this expression:

[print_expr]

_print_ produces this output:

[pre
expr<->
    expr<+>
        term<boost::yap::placeholder<4ll>>[=4\]
        expr<*>
            term<double &>[=1\]
            term<thing>[=<<unprintable-value>>\] &
    term<char const*>[=lvalue terminal\] const &
]

As you can see, _print_ shows one node per line, and represents the tree
structure with indentation.  It abbreviates non-terminal nodes in the tree
`expr<op>`, where `op` is an operator symbol.  Terminal nodes are abbreviated
`term<T>`, where `T` is the type of value contained in the terminal; this may
be a reference type or a value.

A `term` node may not be a terminal node at all, but an _expr_ref_ expression
containing a terminal.  Such a _expr_ref_ node has a `&` or `const &` suffix,
to indicate that it is a mutable or `const` reference, respectively.

Each `term` node has a bracketed value near the end.  The format is `[=X]`
where `X` is the value the terminal contains.  If the terminal contains a
value for which no `operator<<(std::ostream &, ...)` overload exists (such as
the `thing` type above), `X` will be `<<unprintable-value>>`.

[endsect]