Boost logo

Proto :

Subject: Re: [proto] proto-11 progress report
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2012-06-27 17:11:50

On 25/06/2012 23:30, Eric Niebler wrote:
> On 6/25/2012 12:21 PM, Mathias Gaunard wrote:

>> There is a function which is very simple and that I found to be very
>> useful when dealing with expression trees.
>> unpack(e, f0, f1) which calls
>> f0(f1(e.child0), f1(e.child1), ..., f1(e.childN))
>> I can do recursion or not with the right f1, and I can 'unpack' an
>> expression to an n-ary operation f0.
>> Here f0 is typically a function that uses its own overloading-based
>> dispatching mechanism.
> OK, thanks for the suggestion. Where have you found this useful?

For example I can use this to call

functor<tag::plus>()(functor<tag::multiplies>()(a, b), c);

from a tree like

expr<tag::plus, list2< expr<tag::multiplies, list2< expr<tag::terminal>,
expr<tag::terminal> >, expr<tag:terminal> > >

NT2 uses a mechanism like this to evaluate expressions.

For element-wise expressions (i.e. usual vector operations), the f1 is
the run(expr, pos) function -- actually more complicated, but there is
no need to go into details -- which by default simply calls unpack

What the f0 does is simply unpack the expression and call a functor
associated to the tag (i.e. run(expr, i) with expr<tag::pow, list2<foo,
bar> > calls pow(run(foo, i), run(bar, i)) ).

The important bit is that it is also possible to overload run for a
particular node type.

On terminals, the run is defined to do a load/store at the given
position. This means run(a + b * sqrt(c) / pow(d, e), i) calls
plus(a[i], multiplies(b[i], divides(sqrt(c[i]), pow(d[i], e[i]))))

Each function like plus, multiplies, sqrt, pow, etc. is overloaded so
that if any of the arguments is an expression, it does a make_expr. If
the values are scalars, it does the expected operations on scalars. If
they're SIMD vectors, it does the expected operations on vectors.

run is also overloaded for a variety of operations that depend on the
position itself, such as restructuring, concatenating or repeating data;
the position is modified before running the children or different things
may be run depending on a condition.

A simple example is the evaluation of cat(a, b) where run(expr, i) is
defined as something a bit like i < size(child0(expr)) ?
run(child0(expr), i) : run(child1(expr), i-size(child0(expr))

unpack is also used for expression rewriting: before expressions are
run, the expression is traversed recursively and reconstructed. Whenever
operations that are not combinable are found, those sub-expressions are
evaluated and the resulting terminal is inserted in their place in the
tree. In NT2 this is done by the schedule function.

Similarly we have a phase that does the same kind of thing to replace
certain patterns of combinations by their optimized counterparts
(optimize). We'd like to do this at construction time but it's currently
not very practical with the way Proto works.

Both optimize and schedule require containing children by value to
function correctly.

Transforms are not used much since they're only useful for the most
simple operations due to their pseudo-DSL pure functional nature. It's
especially problematic when performance sensitive code, which needs to
be stateful, is involved. Finally it's also not practical to do anything
involving nodes of arbitrary arity with them.

Unfortunately I cannot say transforms are good enough for the kind of
thing NT2 does.

Proto list run by eric at