Proto for Boost mailing list page: Re: [proto] [phoenix3] New design proposal

Subject: Re: [proto] [phoenix3] New design proposal
From: Thomas Heller (thom.heller_at_[hidden])
Date: 2010-10-20 13:09:57

On Wednesday 20 October 2010 05:19:17 Joel de Guzman wrote:
> On 10/20/2010 12:08 AM, Eric Niebler wrote:
> > On 10/19/2010 1:33 AM, Thomas Heller wrote:
> >> On Tue, Oct 19, 2010 at 6:21 AM, Joel de Guzman wrote:
> >>> Can we also focus on one very specific use-case that demonstrates
> >>> the motivation behind the need of such a refactoring and why the
> >>> old(er) design is not sufficient? I'd really want to sync up with
> >>> you guys.
> >> 
> >> With the old design (the one which is currently in the gsoc svn
> >> sandbox) I had problems with defining what phoenix expressions really
> >> are. We had at least two types of expressions. First were the ones we
> >> reused from proto (plus, multiplies, function and so on), Second were
> >> these proto::function constructs which had a funcwrap<T>  struct and
> >> an env placeholder. This env placeholder just wastes a valuable slot
> >> for potential arguments. The second point why this design is not
> >> good, is that data and behaviour is not separated. The T in funcwrap
> >> defines how the phoenix expression will get evaluated.
> >> 
> >> This design solves this two problems: Data and behaviour are cleanly
> >> separated. Additionally we end up with only one type of expressions:
> >> A expression is a structure which has a tag, and a variable list of
> >> children. You define what what a valid expression is by extending the
> >> phoenix_algorithm template through specialisation for your tag. The
> >> Actions parameter is responsible for evaluating the expression. By
> >> template parametrisation of this parameter we allow users to easily
> >> define their own evaluation schemes without worrying about the
> >> validity of the phoenix expression. This is fixed by the meta grammar
> >> class.
> > 
> > What Thomas said. We realized that for Phoenix to be extensible at the
> > lowest level, we'd need to document its intermediate form: the Proto
> > tree. That way folks have the option to use Proto transforms on it.
> > (There are higher-level customization points that don't expose Proto,
> > but I'm talking about real gear-heads here.)
> > 
> > There were ugly things about the intermediate form we wanted to clean
> > up before we document it. That started the discussion. Then the
> > discussion turned to, "Can a user just change a semantic actions here
> > and there without having to redefine the whole Phoenix grammar in
> > Proto, which is totally non-trivial?" I forget offhand what the use
> > case was, but it seemed a reasonable thing to want to do in general.
> > So as Thomas says, the goal is two-fold: (a) a clean-up of the
> > intermediate form ahead of its documentation, and (b) a way to easily
> > plug in user-defined semantic actions without changing the grammar.
> > 
> > I think these changes effect the way to define new Phoenix syntactic
> > constructs, so it's worth doing a before-and-after comparison of the
> > extensibility mechanisms. Thomas, can you send around such a
> > comparison? How hard is it to add a new statement, for instance?
> 
> Yes, exactly, that's what I want. Anyway, while I'd still want to see
> this, I looked at the code and I like it, except for some nits here
> and there (especially naming). More on that later.

I am very interested to here your naming suggestions. In the meantime, I 
haven't sit still.

Before discussing the extension mechanism for introducing new phoenix types, 
I want to take another step to justify why i think this design decision is a 
good idea, based on a hopefully good analogy, i will then explain the 
different steps necessary comparing to that analogy, both, the old mechanism 
and the new one.
Consider compilers for regular languages like C/C++/Java/you name it. How do 
they work? Well, at first, the textual representation is somehow transformed 
into an AST. This AST is built up basically by the rules based on the 
grammar of that language. The AST is one form of data the compiler works on.
After the AST creation the compiler usually wants to apply some other 
transformation to that tree. This can be easily done by using the visitor 
pattern. This means, everything a compiler does is expressed in some form of 
visitors. The visitor pattern is perfectly applicable here because a 
language has a fixed set of language constructs, and if someone adds new 
constructs, all visitors have to be adapted.
So far so good.
"How does phoenix and proto fit into that picture?" you might ask.
Phoenix is the language that we are trying to build, and proto is the 
language in which we are building our compiler to transform that language.
The AST creation part is done by our Expression template generators, being 
it operators, constant global objects (like the placeholders) or functions 
(like val, ref, cref ...).
"How does the AST of an phoenix expression actually look like?" is maybe the 
next question.
In the old design, the answer to that problem is tricky:
There are the regular proto expressions, and there is this funcwrap 
expression inside a proto function, but there are proto functions as well.
In this new design, the answer is simple:
The AST is a proto expression tree. The expression have unique tags, and 
every expression can be matched by "simple" proto grammars.
"How do i work with this AST?" is the ultimate question.
In the old design, there simply was no easy way to reuse existing proto 
facilities to work on the AST. period. There was the eval_grammar and that's 
it. Based on the design choice, that a phoenix expression carried its 
behavior along, there was no need for the visitation of the AST, because 
everything could be described in the proto grammar with an appropriate 
transform. This is fine until someone wants to do something else with the 
phoenix AST. Additionally, in the old design, there was no real evidence of 
what a valid phoenix lambda expression looks like. proto::matches matched 
all possible phoenix expressions.
In the new design all these limitations were addressed.
You can now visit based on rules, which are proto grammars, so this is 
equivalent of saying, the evaluator is a visitor of the phoenix expression 
tree that evaluates the expression.
By having this, it is only natural to separate the data (phoenix expression) 
from the algorithm (which is for example the evaluation)

I hope that clarifies the situation even more. I really would like to see 
phoenix as an actual language, and the library itself as the compiler.

With that being said, I want to go through the process of creating a new 
phoenix syntactic construct. As an example for this, i would like to take 
the for loop construct.

First, the old design (
https://svn.boost.org/svn/boost/sandbox/SOC/2010/phoenix3/boost/phoenix/statement/for.hpp 
)

What you do there is, you simply define how a for construct is evaluated, 
next you define a helper to create such an object. And finally, write a 
generator for that construct. That is all.

Second, the new design ( 
http://github.com/sithhell/boosties/blob/master/phoenix/boost/phoenix/statement/for.hpp 
)

I have to admit, creating new syntactic constructs is a bit more involved, 
however, I hope i made the benefit clear.

lines 18-28: The expression type itself is created. With this expression we 
gain the ability to reuse it in a proto context.

lines 41-53: We set up a rule which describes what a valid for expression 
looks like, and add it to the set of phoenix rules, enabling the use of the 
for construct. Without that line, creating a for_loop would lead to a 
compile error.

lines 56-85: We define how that for loop will be evaluated. That is basically 
the same as with the old design

line 88-99: We add this for loop evaluation to our default expression 
evaluator

The remaining lines are for generating foor loops, and are almost the same 
as with the old design

Cheers,
Thomas