Proto for Boost mailing list page: Re: [proto] Thoughts on traversing proto expressions and reusing grammar

Subject: Re: [proto] Thoughts on traversing proto expressions and reusing grammar
From: Thomas Heller (thom.heller_at_[hidden])
Date: 2010-10-13 02:06:36

On Wednesday 13 October 2010 07:10:15 Eric Niebler wrote:
> On 10/4/2010 11:51 PM, Thomas Heller wrote:
> > Eric Niebler wrote:
> >> On Mon, Oct 4, 2010 at 12:43 PM, Thomas Heller
> > 
> >> <thom.heller-gM/Ye1E23mwN+BqQ9rBEUg_at_[hidden]>wrote:
> > <snip>
> > 
> >>>> I'll also point out that this solution is FAR more verbose that the
> >>>> original which duplicated part of the grammar. I also played with
> >>>> such visitors, but every solution I came up with suffered from this
> >>>> same verbosity problem.
> >>> 
> >>> Ok, the verbosity is a problem, agreed. I invented this because of
> >>> phoenix, actually. As a use case i wrote a small prototype with a
> >>> constant folder:
> >>> 
> >>> http://github.com/sithhell/boosties/blob/master/proto/libs/proto/test
> >>> /phoenix_test.cpp
> >> 
> >> Neat! You're getting very good at Proto. :-)
> > 
> > Thanks :)
> > Let me comment on your request:
> > 
> > On Tuesday 05 October 2010 03:15:27 Eric Niebler wrote:
> >> I'm looking at this code now, and perhaps my IQ has dropped lately
> >> (possible), but I can't for the life of me figure out what I'm looking
> >> at. I'm missing the big picture. Can you describe the architecture of
> >> this design at a high level? Also, what the customization points are
> >> and how they are supposed to be used? I'm a bit lost. :-(
> > 
> > First, let me emphasize that I try to explain this code:
> > http://github.com/sithhell/boosties/blob/master/proto/libs/proto/test/p
> > hoenix_test.cpp
> > 
> > Ok, i feared this would happen, forgive me the low amount of comments
> > in the code and let me start with my considerations for this new
> > prototype.
> > 
> > During the last discussions it became clear that the current design
> > wasn't as good as it seems to be, it suffered from some serious
> > limitations. The main limitation was that data and algorithm wasn't
> > clearly separated meaning that every phoenix expression intrinsically
> > carried it's behavior/"how to evaluate this expression".
> 
> Correct. IIRC, in the old scheme, the tags were actually function
> objects that implemented the default "phoenix" evaluation behavior
> associated with the tag. That didn't preclude other Proto algorithms
> being written that ignored the behavior associated with the tags and
> just treated them as tags. But it was not as stylistically clean.

Correct. The old scheme had one tag only, proto::tag::function, the "type" 
of the expression was the first argument to that "function", which implicitly 
"knew" how to evaluate the expression.

> > This was the main motivation behind this new design, the other
> > motivation was to simplify certain other customization points.
> > One of the main requirements i set myself was that the major part of
> > phoenix3 which is already written and works, should not be subject to
> > too much change.
> 
> Right.
> 
> > Ok, first things first. After some input from Eric it became clear that
> > phoenix expressions might just be regular proto expressions, wrapped
> > around the phoenix actor carrying a custom tag.
> 
> Not sure I understand this. From the code it looks like it's the other
> way around: phoenix expressions wrap proto expressions (e.g. the actor
> wrapper).

Sorry, got mixed up in naming the things i wrote. Your phrasing is correct.

> > This tag should determine that it
> > really is a custom phoenix expression, and the phoenix evaluation
> > scheme should be able to customize the evaluation on these tags.
> 
> OK.
> 
> > Let me remind you that most phoenix expressions can be handled by
> > proto's default transform, meaning that we want to reuse that wherever
> > possible, and just tackle the phoenix parts like argument
> > placeholders, control flow statements and such.
> > Sidenote: It also became clear that phoenix::value and
> > phoenix::reference can be just mere proto terminals.
> 
> Right. But it's not clear to me from looking at your code how the
> evaluation of reference_wrapped terminals is accomplished, though.
> Indeed, evaluating "cref(2)(0)" returns a reference_wrapper<int const>,
> not and int. And in thinking about it, this seems to throw a bit of a
> wrench in your design, because to get special handling (as you would
> need for reference_wrapper), your scheme requires unary expressions with
> special tags, not plain terminals.

Correct, i went for reference_wrapper here, because no matter how hard i 
tried, the object did not get stored by reference in the terminal, but by 
value. This might be directly related to phoenix_domain::as_child<T>. Not 
sure.

> > Having that said, just having "plain" evaluation of phoenix expressions
> > seemed to me that it is wasting of what could become possible with the
> > power of proto. I want to do more with phoenix expressions, let me
> > remind you that phoenix is "C++ in C++" and with that i want to be
> > able to write some cool algorithms transforming these proto
> > expressions, introspect these proto expression and actively influence
> > the way these phoenix expressions get evaluated/optimized/whatever.
> > One application of these custom evaluations that came to my mind was
> > constant folding, so i implemented it on top of my new prototype. The
> > possibilities are endless: A proper design will enable such things as
> > multistage programming: imagine an evaluator which does not compute
> > the result, but translate a phoenix expression to a string which can
> > be compiled by an openCL/CUDA/shader compiler. Another thing might be
> > auto parallelization of phoenix expression (of course, we are far away
> > from that, we would need a proper graph library for that).
> > Nevertheless, these were some thoughts I had in mind.
> 
> All good goals, but IIUC nothing about the older design precluded that.
> Phoenix expressions were still Proto expressions, and users could write
> Proto algorithms to manipulate them (so long as the intermediate form
> was sensible and well-documented).

You are correct. The only difference now is that it seems to me that the 
expressions in my new schemes are not as polluted with other stuff as it was 
in the old scheme (like this env dummy, everything is a function ...). This 
means it is actually a simplification of the expression itself allowing the 
user to spot the type of the expression a little bit easier.

> > This is the very big picture.
> > 
> > Let me continue to explain the customization points I have in this
> > design:
> > 
> > First things first, it is very easy to add new expression types by
> > 
> > specifying:
> >    1) The new tag of the expression.
> >    2) The way how to create this new expression, and thus building up
> >    the
> >    
> >       expression template tree.
> >    
> >    3) Hook onto the evaluation mechanism
> >    4) Write other evaluators which just influence your newly created
> >    tag
> >    
> >       based expression or all the other already existing tags
> > 
> > Let me guide you through this process in detail by explaining what has
> > been done for the placeholder "extension" to proto (I reference the
> > line numbers of my prototype).
> 
> Nit: placeholders make for an interesting exploration of the design
> space, but placing them outside the core seems futile to me. I've
> discussed this before: the placeholders are special, the core needs to
> know about them (nullary actor::operator() must calculate the arity of
> the Phoenix expression, which depends on the placeholders). Given that
> the core must know about the placeholders, pretending they are a layer
> on top of an extensible core is really a sham. But an interesting sham.
> :-)

Agree. But, there is nothing wrong with defining the placeholders as being 
part of the core ;)

> > 1) define the tag tag::argument: line 307
> > 2) specify how to create this expression: line 309 to 315
> > 
> >       First, define a valid proto expression line 309 through
> >       phoenix_expr which had stuff like proto::plus and such as
> >       archetypes. The thing it does, it creates a valid proto grammar
> >       and transform which can be reused in proto grammars and
> >       transforms, just like proto::plus.
> 
> I don't yet see the purpose of having phoenix_expr be a grammar and a
> transform. Looks like the transform associated with phoenix_expr is just
> the identity transform; it just returns the expression passed in. Is
> this useful?

Yes, it can be useful. Look at the grammars i defined to check for certain 
phoenix expressions (line 493 to 502). instead of writing 
binary_expression<phoenix::tag::if_then, Cond, Else> you can just write
phoenix::if_then<Cond, Else>.
The code for phoenix_expr is almost identical to that of proto::plus, 
proto::minus, proto::function and so on.
 
> >       Second, we create some constant expressions which are to be used
> >       as placeholders
> 
> Looks like in this design, _1 is actually a unary expression, not a
> terminal. Once we get over trying to make the placeholders an extension
> and move it back into the core, I think _1 can go back to being just a
> terminal as it was before. This seems less surprising to me.

The placeholders were unary expressions in the old scheme as well. I don't 
understand how you could turn it into plain terminals.

> > 3) Hook onto the evaluation mechanism: line 321 to 361
> > 
> >    Note: i created a unpack transform which is boilerplate code for the
> >    
> >          extraction of the children of the current node. So what it
> >          does is, that it calls the proto::callable passed as first
> >          template parameter and is applies an optional transform to
> >          the children prior to passing it to the callable,
> >          additionally it is able to forward the data and state to the
> >          transform
> 
> I had a really hard time grokking unpack. In Proto, function-types are
> used to represent function invocation and object construction. The type
> "X(A,B,C)" means either call "X" with three arguments, or construct "X"
> with three arguments. In "unpack< X(A, B, C) >" X does *not* get called
> with three arguments. It gets called like "X( A(_0), A(_1), A(_2), ...B,
> C )", where _0, _1 are the child nodes of the current expression. This
> will confuse anyone familiar with Proto. I'd like to replace this with
> something a little more transparent.

I agree, i am not entirely happy with unpack either. It just seemed to be so 
convenient. Perhaps it can follow the concepts as nary_expr and vararg as 
transforms do?

> >    in line 320 to 323 we define the specialization of our
> >    generic_evaluator which dispatches the call to argument_eval
> >    through the unwrap transform. The remaining part (line 325 to 361)
> >    does not differ too much from the current design.
> 
> <snip>
> 
> This is as far as I made it today. I haven't yet grokked the
> generic_evaluator or the visitor. I also can't see where the grammar for
> valid Phoenix expressions is defined in this design. How can I check
> whether an expression is a Phoenix lambda?

Currently, everything is a valid phoenix lambda. I agree, this is probably 
not a good behavior.
However, it can be easily added (this is actually where the visitor plays 
out its strength :)).
In line 47 i defined phoenix_grammar, which can be specialized on tags to 
define a better grammar for one specific tag.
You can then check with (admitting this doesn't work yet, but i plan to 
implement this soon):
proto::matches<phoenix_visitor<proto::_>, some_expr>
If an expression is a valid lambda. Note, that you don't really have to care 
about the algorithm (or transform) and just check that the data you are 
passing is valid.

> I'm back on the case tomorrow.
Thanks for the feedback so far.