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: Eric Niebler (eric_at_[hidden])
Date: 2010-10-16 18:51:00

On 10/16/2010 12:15 PM, Thomas Heller wrote:
> On Saturday 16 October 2010 03:45:45 Eric Niebler wrote:
>> On Fri, Oct 15, 2010 at 1:35 AM, Thomas Heller
>>
>> <thom.heller_at_[hidden]>wrote:
>>> On Wednesday 13 October 2010 07:10:15 Eric Niebler wrote:
>>>> 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.
>>>
>>> Ok, i put to together an alternative version. This hooks onto the
>>> already in
>>> place transform mechanism and works like this:
>>> Whenever the first argument to a transform is proto::vararg<Fun> it
>>> expands the child expressions and applies the Fun transform before the
>>> actual transform gets called, example:
>>>
>>> struct test
>>>   : proto::when<
>>>         proto::function<vararg<proto::_> >
>>>       , foo(vararg<proto::_>)
>>>     >
>>> {};
>>>
>>> this will call foo(a0, a1 ... aN) where aX are the children of the
>>> function expressions. Note that you can replace proto::_ by any
>>> transform you like. Thus making the call look like:
>>> foo(Fun(a0), Fun(a1), Fun(a2) ...)
>>
>> Ah, clever! I like it. I'd like to see this generalized a bit though. For
>> instance, if the transform were instead "foo(_state, vararg<_>)" the
>> intention is clear, but it doesn't sound like your implementation would
>> handle this.
> 
> Well, it could be done. Given that vararg expands to all children of the 
> current expression, 

Then IMO vararg is a really bad name. It's non-descriptive. The C++0x
term for unpacking a parameter pack is "pack expansion". That's
analogous to what this feature does, so IMO "unpack" or "expand" are the
logical choices.

> this is possible. Though it would add to compile time. 
> The current implementation is in O(N^2), 

Why?

> allowing to place vararg anywhere 
> in the transform call is tempting, but it would introduce O(N^3) 
> preprocessor iterations.

We should apply some big brains to see if there's a way to accomplish
this efficiently, maybe with a more efficient PP implementation and/or
function overloading. The last time I ran into a brick wall like this, I
posed it as a programming challenge to boost-devel and got several
really creative solutions. There are some smart folks out there.

> Let me add here, that i am planning on writing a boost.wave driver which 
> allows to preprocess headers (as MPL already does), expanding BOOST_PP 
> iteration constructs until a certain N. I believe this kind of preprocessing 
> will bring down compile times of proto, fusion and phoenix. (There must be a 
> reason why MPL does it, right?)

Very cool!

>> Actually, the semantics get somewhat tricky. And I fear it
>> would lead folks to believe that what gets unpacked by the vararg in the
>> transform corresponds exactly to the children that were matched by the
>> vararg in the grammar. That's not quite the case, is it?
> 
> No, that is not the case. Let me remind you of the implementation of the 
> pass_through transform for nary_expr or function. The semantics are almost 
> exactly the same. The little difference you have with vararg being part of 
> pass_through is that vararg is the last argument, expanding to the remaining 
> children.

Correct. So if you have:

when<
    function< This, vararg<That> >
  , call_this(vararg<That>)
>

you have a major whoops on your hands. Why? Because it will pass to That
something that matched This, which violates That's preconditions. You
really need to handle this case.

With unpack as I suggested it:

when<
    function< This, vararg<That> >
  , call_this(unpack(pop_front(_), That))
>

But I think a promising line of attack would be to study the syntax of
pack expansion and pack expansion patterns, and make it as similar as
possible. No concrete suggestions yet.

>> How about this ... an "unpack" placeholder that works essentially how
>> your vararg does, but with any Fusion sequence (including Proto
>> expressions), and the sequence has to be explicitly specified (like the
>> first parameter to proto::fold).
>>
>> So, instead of foo(vararg<_>), you'd have foo(unpack(_)), where _ means
>> "the sequence to unpack", not "the transform to apply to each element".
>> If you want to apply a transform to each element first, you could
>> specify the transform as a second parameter: foo(unpack(_, Fun)). (That
>> form would probably use fusion::transform_view internally.)
>>
>> The implementation of this would be very tricky, I think, because unpack
>> could appear in any argument position,not just the first. And you'd have
>> to be careful about compile times. But a fun little problem!
> 
> This sounds interesting as well, but i don't think adding another 
> placeholder really helps people in that case.

Have I changed your mind?

>>> Additionally, you can add whatever arguments you like to the transform.
>>  
>> Which transform? Example?
> 
> The foo transform. You can call it with whatever arguments you like, just 
> like a regular transform.

I'm looking at this:

struct test
  : proto::when<
        proto::function<vararg<proto::_> >
      , foo(vararg<proto::_>)
    >
{};

In this, foo doesn't look like a transform. It looks like an ordinary
callable function object. And if it were a transform, I don't see where
the transform arguments would go. Still confused.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com