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-13 14:54:54

On Wednesday 13 October 2010 20:15:55 Eric Niebler wrote:
> On 10/12/2010 11:06 PM, Thomas Heller wrote:
> > On Wednesday 13 October 2010 07:10:15 Eric Niebler wrote:
> >> On 10/4/2010 11:51 PM, Thomas Heller wrote:
> >>> During the last discussions it became clear that the current design
> >>> wasn't as good as it seems to be, it suffered from some serious
> >>> limitations. The main limitation was that data and algorithm wasn't
> >>> clearly separated meaning that every phoenix expression intrinsically
> >>> carried it's behavior/"how to evaluate this expression".
> >> 
> >> Correct. IIRC, in the old scheme, the tags were actually function
> >> objects that implemented the default "phoenix" evaluation behavior
> >> associated with the tag. That didn't preclude other Proto algorithms
> >> being written that ignored the behavior associated with the tags and
> >> just treated them as tags. But it was not as stylistically clean.
> > 
> > Correct. The old scheme had one tag only, proto::tag::function, the
> > "type" of the expression was the first argument to that "function",
> > which implicitly "knew" how to evaluate the expression.
> 
> Oh, that's the OLD, old scheme. I had suggested a NEW old scheme where
> the tags themselves were function objects and the dummy env argument was
> done away with, but that never got implemented. It's probably best to
> leave it that way.

Finally something we can agree on :)

> <snip>
> 
> >> Right. But it's not clear to me from looking at your code how the
> >> evaluation of reference_wrapped terminals is accomplished, though.
> >> Indeed, evaluating "cref(2)(0)" returns a reference_wrapper<int
> >> const>, not and int. And in thinking about it, this seems to throw a
> >> bit of a wrench in your design, because to get special handling (as
> >> you would need for reference_wrapper), your scheme requires unary
> >> expressions with special tags, not plain terminals.
> > 
> > Correct, i went for reference_wrapper here, because no matter how hard
> > i tried, the object did not get stored by reference in the terminal,
> > but by value. This might be directly related to
> > phoenix_domain::as_child<T>. Not sure.
> 
> Possibly. But now, you're explicitly constructing a terminal with a
> reference_wrapper as a value. Proto doesn't know how to treat
> reference_wrapper when evaluating Phoenix expression because you haven't
> told it how. You'll need to fit this into your evaluation strategy
> somehow. It will be a good test to see how truly extensible your
> proposed mechanism is.

Ok, i have to admit, it gets a little messy here. We probably would like to 
specialize our generic evaluator based on the terminal tag.
Which takes care of: a) regular terminals (as in captured by value) b) 
things like reference wrapper c) placeholders as you suggested them.
I don't have a good solution to that problem. Anyone else?

The only thing i can think of right know is to introduce a special tag for a 
reference. It would be great if we could make proto::terminals with different 
tags, or let's not call them terminals but nullary expressions.

> >>> Having that said, just having "plain" evaluation of phoenix
> >>> expressions seemed to me that it is wasting of what could become
> >>> possible with the power of proto. I want to do more with phoenix
> >>> expressions, let me remind you that phoenix is "C++ in C++" and with
> >>> that i want to be able to write some cool algorithms transforming
> >>> these proto
> >>> expressions, introspect these proto expression and actively influence
> >>> the way these phoenix expressions get evaluated/optimized/whatever.
> >>> One application of these custom evaluations that came to my mind was
> >>> constant folding, so i implemented it on top of my new prototype. The
> >>> possibilities are endless: A proper design will enable such things as
> >>> multistage programming: imagine an evaluator which does not compute
> >>> the result, but translate a phoenix expression to a string which can
> >>> be compiled by an openCL/CUDA/shader compiler. Another thing might be
> >>> auto parallelization of phoenix expression (of course, we are far
> >>> away from that, we would need a proper graph library for that).
> >>> Nevertheless, these were some thoughts I had in mind.
> >> 
> >> All good goals, but IIUC nothing about the older design precluded
> >> that. Phoenix expressions were still Proto expressions, and users
> >> could write Proto algorithms to manipulate them (so long as the
> >> intermediate form was sensible and well-documented).
> > 
> > You are correct. The only difference now is that it seems to me that
> > the expressions in my new schemes are not as polluted with other stuff
> > as it was in the old scheme (like this env dummy, everything is a
> > function ...). This means it is actually a simplification of the
> > expression itself allowing the user to spot the type of the expression
> > a little bit easier.
> 
> Agreed.
> 
> >>> This is the very big picture.
> >>> 
> >>> Let me continue to explain the customization points I have in this
> >>> design:
> >>> 
> >>> First things first, it is very easy to add new expression types by
> >>> 
> >>> specifying:
> >>>    1) The new tag of the expression.
> >>>    2) The way how to create this new expression, and thus building up
> >>>    the expression template tree.
> >>>    3) Hook onto the evaluation mechanism
> >>>    4) Write other evaluators which just influence your newly created
> >>>    tag based expression or all the other already existing tags
> >>> 
> >>> Let me guide you through this process in detail by explaining what
> >>> has been done for the placeholder "extension" to proto (I reference
> >>> the line numbers of my prototype).
> >> 
> >> Nit: placeholders make for an interesting exploration of the design
> >> space, but placing them outside the core seems futile to me. I've
> >> discussed this before: the placeholders are special, the core needs to
> >> know about them (nullary actor::operator() must calculate the arity of
> >> the Phoenix expression, which depends on the placeholders). Given that
> >> the core must know about the placeholders, pretending they are a layer
> >> on top of an extensible core is really a sham. But an interesting
> >> sham.
> >> 
> >> :-)
> > 
> > Agree. But, there is nothing wrong with defining the placeholders as
> > being part of the core ;)
> 
> If it's not clear, that's exactly what I was arguing for.
> 
> >>> 1) define the tag tag::argument: line 307
> >>> 2) specify how to create this expression: line 309 to 315
> >>> 
> >>>       First, define a valid proto expression line 309 through
> >>>       phoenix_expr which had stuff like proto::plus and such as
> >>>       archetypes. The thing it does, it creates a valid proto grammar
> >>>       and transform which can be reused in proto grammars and
> >>>       transforms, just like proto::plus.
> >> 
> >> I don't yet see the purpose of having phoenix_expr be a grammar and a
> >> transform. Looks like the transform associated with phoenix_expr is
> >> just the identity transform; it just returns the expression passed
> >> in. Is this useful?
> > 
> > Yes, it can be useful. Look at the grammars i defined to check for
> > certain phoenix expressions (line 493 to 502). instead of writing
> > binary_expression<phoenix::tag::if_then, Cond, Else> you can just write
> > phoenix::if_then<Cond, Else>.
> 
> Ah! I love it. But IMO the default transforms that come with these new
> phoenix grammars are useless. Instead of the identity transform, they
> should be the pass_through transform, just like with proto::plus and
> friends. Just my $0.02.

Agreed, this should be changed.

> > The code for phoenix_expr is almost identical to that of proto::plus,
> > proto::minus, proto::function and so on.
> > 
> >>>       Second, we create some constant expressions which are to be
> >>>       used as placeholders
> >> 
> >> Looks like in this design, _1 is actually a unary expression, not a
> >> terminal. Once we get over trying to make the placeholders an
> >> extension and move it back into the core, I think _1 can go back to
> >> being just a terminal as it was before. This seems less surprising to
> >> me.
> > 
> > The placeholders were unary expressions in the old scheme as well. I
> > don't understand how you could turn it into plain terminals.
> 
> Simple. They become:
> 
>   typedef
>     actor<proto::terminal<phoenix_placeholder<mpl::int_<0> > >::type>
>   arg1_type;
> 
>   arg1_type const arg1 = {};
> 
> And then your default evaluator changes to handle placeholders:
> 
>     template <typename Tag>
>     struct generic_evaluator
> 
>       : proto::or_<
> 
>             proto::when<
>                 proto::terminal<phoenix_placeholder<proto::_> >
>               , fusion_at(proto::_value, proto::_state)
> 
>           , proto::_default<eval_grammar>
> 
>     {};
> 
> or something. If placeholder are part of the core, there's nothing
> stopping you from doing this. You can also handle reference_wrappers
> here, but that feels like a hack to me. There should be a way for
> end-users to customize how Phoenix handles terminal types like
> reference_wrapper.

The problem i am having with approach to tackle placeholders, is that i 
still can't see how this would solve the grand "placeholder unification" 
problem

> >>> 3) Hook onto the evaluation mechanism: line 321 to 361
> >>> 
> >>>    Note: i created a unpack transform which is boilerplate code for
> >>>    the
> >>>    
> >>>          extraction of the children of the current node. So what it
> >>>          does is, that it calls the proto::callable passed as first
> >>>          template parameter and is applies an optional transform to
> >>>          the children prior to passing it to the callable,
> >>>          additionally it is able to forward the data and state to the
> >>>          transform
> >> 
> >> I had a really hard time grokking unpack. In Proto, function-types are
> >> used to represent function invocation and object construction. The
> >> type "X(A,B,C)" means either call "X" with three arguments, or
> >> construct "X" with three arguments. In "unpack< X(A, B, C) >" X does
> >> *not* get called with three arguments. It gets called like "X( A(_0),
> >> A(_1), A(_2), ...B, C )", where _0, _1 are the child nodes of the
> >> current expression. This will confuse anyone familiar with Proto. I'd
> >> like to replace this with something a little more transparent.
> > 
> > I agree, i am not entirely happy with unpack either. It just seemed to
> > be so convenient. Perhaps it can follow the concepts as nary_expr and
> > vararg as transforms do?
> > 
> >>>    in line 320 to 323 we define the specialization of our
> >>>    generic_evaluator which dispatches the call to argument_eval
> >>>    through the unwrap transform. The remaining part (line 325 to 361)
> >>>    does not differ too much from the current design.
> >> 
> >> <snip>
> >> 
> >> This is as far as I made it today. I haven't yet grokked the
> >> generic_evaluator or the visitor. I also can't see where the grammar
> >> for valid Phoenix expressions is defined in this design. How can I
> >> check whether an expression is a Phoenix lambda?
> > 
> > Currently, everything is a valid phoenix lambda. I agree, this is
> > probably not a good behavior.
> 
> No, not good.
> 
> > 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)

> > 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.