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-15 01:46:17

Eric Niebler wrote:

> On 10/13/2010 11:08 PM, Thomas Heller wrote:
>> 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.
> 
> You mean expression tags, right? First time I read this, I accepted this
> statement as fact. Now I wonder.

Right, when I mean tags, I refer to expression tags. sorry for the 
confusion.

> *Why* do you want to dispatch your transforms based on tags? You're
> thinking of proto::switch_, which dispatches grammars based on
> expression tags, right? But it doesn't follow that transforms are best
> dispatched on expression tags, too.

You are totally right here. Dispatching transforms *only* on expression tags 
is not enough.

> We are close to the bare
> requirements, but we're not there yet. In my understanding, the
> requirements are as I stated before (and which you agreed with):
> 
> A) Have an openly extensible grammar.
> B) Have an equally extensible set of transforms.
> C) Be able to substitute out a whole other (extensible) set of transforms.
> 
> I have an alternate solution that meets these requirements and doesn't
> dispatch to transforms based on expression tags. It dispatches to
> transforms using grammar rules. This has a number of nice properties.
> Keep reading...

I was waiting for it, as i saw the deficiencies of my design as well. I just 
couldn't get wrap head around another solution. The idea with dispatching on 
rules is great. I tend to forget that proto grammars are types as well :).

>> 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.
> 
> My solution works differently. Which one is better is still an open
> question.

So, one of your points of criticism was that my solution was overly verbose. 
I like to throw this ball back at you. I think both solutions are quite 
verbose. I guess verbosity is what it takes to get a solution meeting the 
requirements.

>> 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).
> 
> I'm with you here.
> 
>> 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).
> 
> Dispatch to transforms on grammar rules.

Great!

>> 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.
> 
> I have followed your logic this far, although our solutions have diverged.
> 
>> 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.
> 
> Here's where you lose me. I didn't know there was a problem with
> defining what a valid phoenix expression looks like. Proto::switch_
> seems to be good enough. To allow the phoenix grammar to be openly
> extensible.

Right, proto::switch_ is good enough for the grammar to be extensible. The 
thing i was striving for is extendability of the actions.

>> 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, you're allowing both the grammar and the semantic actions to float,
> and they both depend on expression tags. I get it. I see problems with
> this design (see below), but the largest is that the phoenix_grammar is
> now so flexible as to be meaningless. Anybody can change anything. The
> very simple question of "what is a valid phoenix expression?" now
> becomes *very* difficult to wrap your head around. But there's a more
> practical consideration that I'll discuss later.

I totally agree with you here.

>> 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 understand now. Thanks. "Visitor" is really a generalization of
> proto::switch_. Switch_ accepts one argument and treats it as a
> collection of grammars that are indexed on expression tag. Visitor
> accepts two arguments---a collection of grammars and another collection
> of transforms---both of which are indexed on expression tags. Really,
> visitor could just be a further generalization of switch_.

Agreed, it is nothing more.

> But I don't think that's a good idea. More below.
> 
>> 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).
> 
> First, let me say that everything you've done is perfectly reasonable,
> and I (finally!) understand what you've done and why you've done it. Whew!
> 
> Here's the fundamental problem with dispatching to transforms based on
> expression tags: the tags are insufficient to pick the right transform.
> Consider:
> 
> // Define an openly extensible grammar using switch_
> struct MyGrammar
>   : proto::switch_< struct MyCases >
> {};
> 
> struct MyCases
> {
>     template<typename Tag>
>     struct case_
>       : proto::not< proto::_ >
>     {};
> };
> 
> // OK, handle the terminals we allow:
> template<>
> struct MyCases::case_< proto::tag::terminal >
>   : proto::or_<
>         proto::when< proto::terminal<int>,  DoIntAction >
>       , proto::when< proto::terminal<char>, DoCharAction >
>     >
> {};
> 
> // ... define other case_ specializations ...
> 
> The important thing to note is that tag::terminal is not enough to
> determine whether a particular terminal is valid for MyGrammar, so we
> have to use proto::or_ to further specialize.
> 
> Also note that the int and char terminals have different semantic
> actions. In this case, dispatching to a transform based on expression
> tag is fundamentally too weak to pick the right one. AFAICT, there would
> be no way to use your visitor to handle this situation.

Point taken, I saw this weakness as well after you pointed you out the stuff 
with reference_wrapper and the placeholders.

> What's the alternative? Rather than dispatching to transforms based on
> expression tags, dispatch on grammar rules. Then document which rules in
> your grammar are customization points.
> 
> The above example becomes this:
> 
> // A collection of actions indexable by rules.
> struct MyActions
> {
>     template<typename Rule>
>     struct action;
> };
> 
> // A helper that finds the appropriate action by looking it
> // up by rule
> template<typename Rule, typename Actions>
> struct MyWhen
>   : proto::when< Rule, typename Actions::template action<Rule> >
> {};
> 
> // An easier way to dispatch to a tag-specific sub-grammar
> template<typename Tag, typename Actions>
> struct MyCases
>   : proto::not< proto::_ >
> {};
> 
> template<typename Actions>
> struct MyCasesImpl
> {
>     template<typename Tag>
>     struct case_
>       : MyCases<Tag, Actions>
>     {};
> };
> 
> // Define an openly extensible grammar using switch_
> template<typename Actions = MyActions>
> struct MyGrammar
>   : proto::switch_< MyCasesImpl<Actions> >
> {};
> 
> // Define a grammar rule for int terminals
> struct IntTerminalRule
>   : proto::terminal<int>
> {};
> 
> // Define a grammar rule for char terminals
> struct CharTerminalRule
>   : proto::terminal<char>
> {};
> 
> // OK, handle the terminals we allow:
> template<typename Actions>
> struct MyCases< proto::tag::terminal, Actions >
>   : proto::or_<
>         MyWhen< IntTerminalRule,  Actions >
>       , MyWhen< CharTerminalRule, Actions >
>     >
> {};
> 
> // Now, populate the MyActions metafunction class
> // with the default actions:
> 
> template<>
> struct MyActions::action< IntTerminalRule >
>   : DoIntAction
> {};
> 
> template<>
> struct MyActions::action< CharTerminalRule >
>   : DoCharAction
> {};
> 
> 
> Some things to note about this solution:
> 
> - MyGrammar can be parameterized by a set of actions.
> 
> - The actions are accessed by indexing via a well-defined
>   and openly extensible set of grammar rules.
> 
> - Although the grammar is extensible, it is not mutable.
>   That is, new constructs can be added, but existing ones
>   cannot be changed. That makes it easier to understand
>   what it means for an expression to match the grammar.
>   (If a different grammar is desired, a new one needs to be
>   defined. It can reuse parts of MyGrammar, but MyGrammar
>   itself remains unchanged. This, I think, is desirable.)
> 
> - The Actions parameter has *no* effect on what expressions
>   match the MyGrammar. MyGrammar<MyActions> and MyGrammar<
>   YourActions> both match exactly the same set of expressions.
> 
> - A new set of actions can be created easily by delegating
>   to MyActions::action by default, and specializing only those
>   rules that need custom handling.
> 
> I'm attaching the beginnings of a Phoenix implementation that is built
> using this technique. It is obviously just a shell. No nice actor
> wrappers or anything. This is just to demonstrate that the technique
> works. It builds an extensible core, handles placeholders, terminals
> (including reference_wrapped terminals), and if_/then_/else_ built as an
> extension to the core.
> 
> Comments?

I am amazed. You beat us again :)
Give me some more time to iron out your implementation, and bring it into 
"phoenix shape". I think I also need some time to experiment a little with 
this to see if it is truly what we were looking for.

I just wonder why didn't have that discussion earlier. I like the result!