123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162 |
- [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]
|