Boost logo

Proto :

Subject: Re: [proto] Thoughts on traversing proto expressions and reusing grammar
From: Eric Niebler (eric_at_[hidden])
Date: 2010-10-13 14:15:55

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.

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

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


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

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

    actor<proto::terminal<phoenix_placeholder<mpl::int_<0> > >::type>

  arg1_type const arg1 = {};

And then your default evaluator changes to handle placeholders:

    template <typename Tag>
    struct generic_evaluator
      : proto::or_<
                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

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

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

Eric Niebler
BoostPro Computing

Proto list run by eric at