|
|
Proto : |
Subject: Re: [proto] Thoughts on traversing proto expressions and reusing grammar
From: Eric Niebler (eric_at_[hidden])
Date: 2010-10-14 15:27:02
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.
*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. 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...
> 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.
> 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.
> 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.
> 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.
> 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_.
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.
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?
-- Eric Niebler BoostPro Computing http://www.boostpro.com
Proto list run by eric at boostpro.com