Proto for Boost mailing list page: Re: [proto] proto-11 progress report

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 
recursively.

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.