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-14 02:08:56

On Wednesday 13 October 2010 22:46:40 Eric Niebler wrote:
> On 10/13/2010 11:54 AM, Thomas Heller wrote:
> > On Wednesday 13 October 2010 20:15:55 Eric Niebler wrote:
<snip>
See my other post about comments on this, I think we agree on the rest.
The only problem we are diverging right know seems to be that "visitor" I 
proposed. See another attempt to justify, and possibly explaining it better 
below.

> >>> 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.
> >> 
> >> I don't get that. There needs to be a phoenex grammar. One, and only
> >> one. I don't see why it's a template, what the tag type is for, or how
> >> one could use a tag to define a "better" phoenix grammar. Because
> >> there's only one. Either an expression is a Phoenix grammar or it
> >> isn't, right?
> > 
> > I disagree here.
> > End users might want to extend phoenix (the EDSL itself), by
> > introducing new expressions (right now by introducing a new tag). Now,
> > the user wants to specifiy what valid expressions look like that can
> > be formed with his new expression type. Here i currently can imagine
> > two different scenarios: First, the user just wants to extend our
> > "regular" grammar. This can be achieved by something like this:
> > 
> > template <>
> > struct phoenix_grammar<my_new_super_cool_tag>
> > 
> >   : // some proto grammar which specifies how valid expressions look
> >   : like
> > 
> > The second scenario i can imagine, that someone wants to build some
> > kind of other language reusing phoenix parts, imagine someone who is
> > so obsessed with functional programming, and doesn't like the current
> > approach and wants a pure functional programming EDSL. Thus he wants
> > to disallow certain expressions. The current visitor design makes that
> > perfectly possible! (I hope this makes things clearer)
> 
> No, I'm afraid it doesn't. Extending phoenix by introducing additional
> tags doesn't necessitate parameterizing the *whole* grammar on a tag.
> The old design handled that scenario just fine by using the openly
> extensible proto::switch_. Just one grammar, and users could hook it
> easily.
> 
> And the second scenario also doesn't suggest to me that the grammar
> needs parameterization. It suggests to me that someone who wants a
> radical customization of Phoenix grammar should make their domain a
> sub-domain of Phoenix, reuse the parts they want, and define the grammar
> of their new EDSL.

Yes, domains ... just after sending the post, subdomains came to my mind as 
well ... This might be the more desirable solution. I agree.

> >>> 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.
> >> 
> >> That made no sense to me. Care to try again?
> > 
> > Sure.If you look at my code, there is a construct like this:
> > 
> > template <template <typename> class Visitor> struct phoenix_visitor
> > 
> >     : proto::visitor<Visitor, phoenix_grammar> {};
> > 
> > phoenix_grammar now has the definitions on what a valid phoenix
> > expression is (defined by whoever through the tag dispatch). the only
> > part missing is the Visitor. But for validating visitors we don't
> > really care what transforms will be applied to our expression. Thus
> > the proto::_ placeholder for visitor.
> 
> (I'll ignore for now the fact that you can't use proto::_ as a template
> template parameter.)
> 
> This is all very convoluted. After days of looking and much discussion,
> I'm afraid I still don't get it. I think it's a bad sign that so far
> I've heard no simple, comprehensible, high-level description of the
> architecture of this design.
> 
> Diving once more into the code,

Sorry i couldn't come up with something that makes really sense to you.
I thought i might have convinced you with my last two usecases.
I am starting to think that naming it visitor in the first place is what 
troubles you most ;)

Let me try again ...
I tried to solve the problem that when writing a proto grammar+transform you 
might want to dispatch your transform based on tags. Additionally you would 
like to replace that particular transform which evaluates your expression by 
another one.
proto::switch_ allows you to dispatch grammar + transform based on a specific 
tag already, I think we agree that .
The major usecase i had in mind for this was phoenix.
First use case is, when defining some generic grammar like this:

struct phoenix_cases
{
      template <typename Tag>
      struct case_
           : proto::otherwise<evaluate<Tag>(proto::_, proto::_state)>
/*call the phoenix evaluator, how? My proposed solution is through tag 
dispatching! */
      {};
};

struct phoenix_grammar
   : switch_<phoenix_cases>
{};

So far so good. I hope we agree that this might be a good way to define the 
phoenix grammar. The need to further define how a valid phoenix grammar can 
look like is through specialising phoenix_cases::case_ (*).
Ok, I think this is a good solution already.

But now, think about, that people might want to evaluate a phoenix 
expression differently!
One example to this is that i want to generate a valid C++ string out of my 
phoenix expression, save it for later and compile it again with my native 
C++ compiler. I might even want to be able to evaluate a phoenix expression 
to openCL/cuda/glsl/hlsl whatever. Another thing i might want to add to the 
evaluation process is autoparallelization. I hope you agree that these might 
be valid usecases!

With the definition of the phoenix grammar above, this is not easily 
possible! I would have to repeat the phoenix grammar all over again (maybe 
this is the point where i am totally of the line).

The next, logical (IMHO) step is to parameterize our phoenix_grammar to 
allow an arbitrary transform to be dispatched on the tag basis (Again, there 
might be a different solution, I can't see any though).

Note: This is the step where the name "Visitor" came in, because it is what 
it does: it visits an expression and transforms it, somehow.

So, the design will change to this:

template <template <typename> Visitor>
struct phoenix_cases
{
      template <typename Tag>
      struct case_
           : proto::otherwise<Visitor<Tag>(proto::_, proto::_state)>
/*call the phoenix evaluator, how? My proposed solution is through tag 
dispatching! */
      {};
};

template <template <typename> Visitor>
struct phoenix_grammar
   : switch_<phoenix_cases<Visitor>
{};

// bring our default evaluator back into the game:
typedef phoenix_grammar<evaluate> evaluator;

I hope this still makes sense.

The next step involved the "problem" of defining what valid phoenix 
expressions look like (We discussed this in (*)). So for the sake of 
simplicity, why not parameterize our phoenix_grammar on a Grammar as well, 
so narrowing down the validity of phoenix expressions becomes the act of 
specializing one simple struct, instead of this phoenix_case beast.
So, the whole thing becomes:

template <template <typename> Visitor, template <typename> Grammar>
struct phoenix_cases
{
      template <typename Tag>
      struct case_
           : proto::when<Grammar<Tag>, Visitor<Tag>(proto::_, 
proto::_state)>
/*call the phoenix evaluator, how? My proposed solution is through tag 
dispatching! */
      {};
};

template <template <typename> Visitor, template <typename> Grammar>
struct phoenix_grammar
   : switch_<phoenix_cases<Visitor, Grammar>
{};

// bring our default evaluator back into the game:
typedef phoenix_grammar<evaluate, grammar> evaluator;

So, Visitor is now some transform that gets called with the expression and 
state. However, what if someone wants to have data as well or doesn't care 
about the current expression. No problem, let Visitor<Tag> be just like any 
other regular transform!
So the final design evolved to this:

template <template <typename> Visitor, template <typename> Grammar>
struct phoenix_cases
{
      template <typename Tag>
      struct case_
           : proto::when<Grammar<Tag>, Visitor<Tag> >
/*call the phoenix evaluator, how? My proposed solution is through tag 
dispatching! */
      {};
};

template <template <typename> Visitor, template <typename> Grammar>
struct phoenix_grammar
   : switch_<phoenix_cases<Visitor, Grammar>
{};

template <typename Tag>
struct evaluate : proto::_default {};

template <typename Tag>
struct grammar : proto::_ {};

// bring our default evaluator back into the game:
typedef phoenix_grammar<evaluate, grammar> evaluator;

This is where Joel Falcou came in and said: "Hey this is a nice abstraction 
of the stuff i already had done!" (paraphrasing here)

Thus I generalized what is now phoenix_grammar and called it proto::visitor. 
And proposed it to this very list.

I hope this makes more sense now. Please point out where I am missing 
something, or where you can not follow the line of thought.

If this still doesn't help I am sorry to have wasted your time. I couldn't 
think of another solution. I would be very happy to see an alternative 
approach to solve this very problem (I like what you did with the split 
example).