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! _______________________________________________ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto