Hu Chunming / sip_server

[section An Expression Template Primer]

What are _ets_ anyway?  In short, _ets_ are templates that you write to
capture expressions so that they can be transformed and/or evaluated lazily.

An example of normal C++ expression is:

    std::sqrt(3.0) + 8.0f

The compiler sees this and creates some representation of that expression
inside the compiler.  This is typically an _ast_ (AST).  The AST for the
expression above might be:

[$yap/img/ast.png]

This tree structure captures all the elements of the original C++ code.  The
expression is a plus operation whose left side is a call to `std::sqrt(3.0)`
and whose right side is `8.0f`.  The call to `std::sqrt(3.0)` is its own
expression subtree consisting of a call node and its argument node.

A _yap_ version of this same tree is:

[$yap/img/expr.png]

The `operator+()` is represented by a _yap_ expression whose kind is
`yap::expr_kind::plus` and the call is represented by a _yap_ expression whose
kind is `yap::expr_kind::call`.  Notice that the call expression has two
terminals, one for the callable, and one for its single argument.

The type that holds this expression is:

[plus_sqrt_yap_type]

That looks like a big mess; let's unpack it.  You might notice that the
overall shape is the same as the expression tree diagram above.  We have
tree-like nesting of `boost::yap::expression` template instantiations.

Here's the top-level `boost::yap::expression` again with
its noisy guts removed:

[plus_sqrt_yap_top_level_1]

    // Left and right operand expressions ...

[plus_sqrt_yap_top_level_2]

It has an _kind_ of `plus` as its first template parameter (it's a non-type
parameter); this indicates what kind of "node" it is.  In this case, the top
level expression is analogous to our `operator+()` AST node.  Its operands are
the elements of its _tuple_ data member.

The left operand to the top-level plus operation is itself a _yap_ expression
representing `std::sqrt(3.0)`:

[plus_sqrt_yap_lhs]

This expression is a call expression.  The first operand to the call
expression is the callable entity, in this case a pointer to `std::sqrt`.  The
remaining operands are the arguments to pass to the callable; in this case,
there's only one operand after the callable, `3.0`.

The children of the `std::sqrt(3.0)` subexpression are terminals.  This means
that they are leaf nodes in our notional AST.

The right operand to the top-level plus operation is of course also a _yap_
expression.  It is also a terminal:

[plus_sqrt_yap_rhs]

Notice a couple of things here: 1) non-terminals (the top-level plus operation
and the call opertion in our example) have tuple elements that are *all* _yap_
expressions, and 2) terminals have tuple elements, *none of which* are _yap_
expressions (they're just normal types like `float` and `double (*)(double)`).

[note From here on, I'll use the terms "expression" and "node" interchangably,
and I'll also use the terms "subexpression" and "child" interchangably.  Even
though _ets_ are not identical to tree-based ASTs, they're close enough that
the terminology is interchangable without loss of meaning.]

[heading Capturing an Expression]

If we want to capture an expression using _yap_ we have to do something to let
the compiler know not just to eagerly evaulate our expression, as it does when
it sees `std::sqrt(3.0) + 8.0f`.

To do this, we create _terminal_ expressions out of one or more of the
terminals in the expression we want to capture and evaluate lazily.  Here,
I've declared a template alias to make that easier to type:

[plus_sqrt_term_alias]

And here is how I might use that alias to create the terminal containing
`std::sqrt`:

[plus_sqrt_yap_value]

The reason I can then just call the terminal with a `3.0` argument and add
`8.0f` to the result is that I'm taking a great big shortcut in this example
by using _yap_'s built-in example _et_, _expr_.  _expr_ is a template with all
the operator overloads defined, including the call operator.  Each operator
overload returns an _expr_, which is why the `+` in `std::sqrt(3.0) + 8.0f`
also works.

[note _expr_ is great for example code like what you see here, and it's great
for small _et_ use cases that are essentially implementation details.  You
should write your own _ets_ for anything that is to be used in any other
context.  The reason for this is that most of the time your _et_ system will
not want to support all combinations of all possible operators and function
calls.  For instance, code like this:

    (a + b) = c;

is at least unusual, if not outright wrong.  Where does `c` go?  Into `a`,
`b`, or into an expiring `a + b` temporary?  What if `a` is a `std::string`
and `b` is a `FILE *`?  _expr_ doesn't care.  You probably want to design
interfaces that are more carefully considered than the "everything goes" style
implied by using _expr_.  ]

_yap_ comes with a handy _print_ function.  Calling it like this:

[print_plus_sqrt_yap_value]

Gives this output:

    expr<+>
        expr<()>
            term<double (*)(double)>[=1]
            term<double>[=3]
        term<float>[=8]

This is a lot more readable.  I show this to you here to give you a more
concise view of the AST-like structure.

(In case you're wondering why `&std::sqrt` is printed as the value `1`, so was
I.  Apparently, that's just what GCC prints for that.  Weird.)

[heading Doing Something Useful With It]

Now we've seen a simple expression both described as a C++ AST and captured as
a _yap_ expression.  This just introduces the _et_ mechanism; what do we do
with it once we have an _et_?  Consider one of the examples from the intro:

    std::vector<int> v1 = {/* ... */};
    std::vector<int> v2 = sort(v) | unique;

The rest of the tutorial will explain in greater detail how _yap_ can be used
in situations like this, but the brief version is this:

* Use _yap_ to capture an expression.  In this case, something like `auto expr
  = sort(v) | unique;`.

* Use the _yap_ _xform_ algorithm to transform the expression into what you
  want.  In this case, something like `auto desired_expr =
  yap::transform(expr, my_transform);`, which turns the concise form `sort(v)
  | unique` into the more verbose calls required by the standard algorithm
  APIs.  Note that the resulting expression can be transformed repeatedly if
  this is desirable.

* Evauate the final expression, either using _eval_ or a call to _xform_ that
  transforms the final expression into an evaluated result.

[endsect]