Boost logo

Proto :

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

Eric Niebler wrote:

> On Mon, Oct 4, 2010 at 12:43 PM, Thomas Heller
> <thom.heller-gM/Ye1E23mwN+BqQ9rBEUg_at_[hidden]>wrote:
>> >
>> > 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:
> 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:

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

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

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.

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

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.
      Second, we create some constant expressions which are to be used as
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
   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.

That is basically what needed to be done to supply phoenix with a
placeholder. I also added the if/else statements to the prototype which
follows the same principles.

The lines 494 to 593 are just a test to check whether the phoenix
expressions really can be used as a proto grammar, and show how it could be
possible to introspect phoenix expressions.

The next big thing is probably the constant folder, which shows how 4) can
be realized and is an example of this customization point.

Another example which only influences one tag, and only that tag could be
the split example which could have been easily embedded into this phoenix
context, and the custom evaluation would have only influenced the split
expressions. Additionally, this is where this visitor plays out it strength:
With the ability to tag dispatch on both, the grammar and the evaluation,
one can easily restrict expression which should _not_ be inside a split

That is all for now, i hope i made this prototype a little clearer and sched
some light on my motivations.

> P.S. It would be great if you could repost this code along with your
> explanation to the proto list. I suspect this redesign is part of the
> motivation for the recent messages you posted there, right?
Right. Consider it done by this message ;)
>> Note that the phoenix grammar could end up growing very complex! But
>> users should still be able to add their own tags for their own
>> expressions. I decided to propose the visitor because Joel Falcou
>> showed interest in it (Because he invented something similiar for NT2,
>> remember one of the first prototypes for phoenix3? They were actually
>> based on the same concepts).
> We abandoned those early prototypes. Now I can't remember why. Can you?

As far as my memories go, we abandoned those prototypes because of several
reasons, one was that this early prototype was quite complex and not very
easy to follow, i guess this is true for my attempt to resurrect it. The
other thing was that people felt like we exposed too much of proto to users
who wanted to extend phoenix. Last but least, it differed too much from the
design of phoenix2. See my explanations above on my try to tackle the
criticism on all these points.

Proto list run by eric at