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

Subject: Re: [proto] proto-11 progress report
From: Eric Niebler (eric_at_[hidden])
Date: 2012-06-28 15:09:20

On 6/27/2012 2:11 PM, Mathias Gaunard wrote:
> 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.

OK.

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

After meditating on this for a bit, a thought occurred to me. Your
unpack function is a generalization of the pattern used by the _default
transform. The _default<X> transform unpacks an expression, transforms
each child with X, then recombines the result using the "C++ meaning"
corresponding to the expression's tag type. In other words,
_default<X>()(e) is unpack(e, f0, f1) where f1 is X and f0 is
hard-coded. I could very easily provide unpack as a fundamental
transform and then trivially implement _default in terms of that. I very
much like this idea.

Aside: The pass_through transform almost fits this mold too, except that
each child can get its own f1. Hmm.

Unpack doesn't sound like the right name for it, though. It reminds me a
bit of Haskell's fmap, but instead of always putting the mapped elements
back into a box of the source type, it lets you specify how to box
things on the way out.

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

Generators are intended to meet this need. What are they lacking for
you? Is it the lack of an "unpack" transform?

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

How is this relevant?

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

Transforms are not pure functional. The data parameter can be mutated
during evaluation. Even expressions themselves can be mutated by a
transform, as long as they're non-const.

> Finally it's also not practical to do anything
> involving nodes of arbitrary arity with them.

You know about proto::vararg, right? It lets you handle nodes of
arbitrary arity.

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

Once there is an unpack transform, will you still feel this way?

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com