Re: [boost] [range/iterators/algorithms/phoenix/bind...] Coordinated Approach

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-07-02 06:25:04

On Wed, Jul 2, 2008 at 4:45 AM, Dean Michael Berris
<mikhailberis_at_[hidden]> wrote:
> On Tue, Jul 1, 2008 at 8:28 PM, Giovanni Piero Deretta
> <gpderetta_at_[hidden]> wrote:
>> On Tue, Jul 1, 2008 at 12:50 PM, Dean Michael Berris
>> <mikhailberis_at_[hidden]> wrote:
>>>
>>> Isn't the whole point of creating an expression template
>>> based-approach to create these (maybe using proto I guess) and allow:
>>>
>>> 1. The same placeholders used in Phoenix+Proto to be used in the pipe
>>> syntax in range_ex (or an imaginary new RangeEx implementation).
>>> 2. Allow for efficient (i.e., compiler optimized/assisted)
>>> implementations of the composition of these new
>>> views/ranges/iterators.
>>>
>>
>> Of course. My point is that you need very few beyond what is available
>> in Phoenix. Just the ability to have
>> a placeholder which doesn't make the whole expression lazy ( i.e.
>> foo(_) should be the same as unlambda(bind(foo, _1)) ).
>>
>
> When you say the whole expression lazy, do you mean even the for_each?
>
> Why don't you want the range generation functions (or the pipe syntax)
> return a lazy range? Perhaps something that only gets activated when
> begin(range) and end(range) are invoked?

Wait, there is a bit of confusion. There are two kind of lazyness: the
first kind are lazily evaluated ranges, like those that use
transform_iterator, filter_iterator, etc... the other kind are lazily
evaluated functions like those in Phoenix (i.e. higher order functions
that return other functions).

Let's take a map function. It can be lazy in two ways:

  map(range, mapper)    [1]

returns a lazy range (i.e. the moral equivalent of two transform_iterators).

  map(_1, mapper)          [2]

returns a lazy unary function that takes a range and returns another
(lazy range).
There is a third syntax that can be used:

  range | map(mapper)  [3]

Now, in the usual phoenix world, the 'map' in [1] and [2] would
actually be two different functions (functions in phoenix are always
lazy even if all arguments are provided). Map in [3] must be again a
different function. This means that a lazy range algorithm should
provide all three variants to satisfy all the use cases. Unless...

Maps in [1] and [2] can actually be the same function by adding
"lazyness on demand" (which is not hard to do). Also lazy functions
let's us implement the third syntax easily:
Let's assume that 'operator|(r, f)' is a global operator that returns
'f(r)'. This doesn't work quite right though:

  range | map(_1, mapper)

Because map(_1, mapper) doesn't simply return an unary function, but
it is actually an expression template, which will try to make
operator| 'its own'. You need to stop the expression template
machinery. In boost.lambda you use 'unlambda', in phoenix I think that
the magic keyword is 'lambda[]':

  range | lambda[ map(_1, mapper) ]

It should works, but the 'lambda' is a bit ugly. If we introduced a
new placeholder, like _, we could make the syntax more lightweight:

  range | map(_, mapper) [4]

I.e. _ instructs phoenix to automatically wrap the lazy function in a
lambda block. Note that this syntax is quite similar to the syntax in
[3].  if we followed FC++ lead and swapper the order of the range and
mapper argument in 'map', we could add a rule that says that any
missing argument is automatically substituted with a _ (in practice,
currying, in fact FC++ itself introduced the '_' syntax for
generalized currying):

  range | map(mapper, _)  -> range | map(mapper)   [5]

Nice! Unfortunately, automatic currying is (very arguably) error
prone, and most importantly, it makes it impossible to have variadic
functions (for example ,in sort(range), how do you know if this is a
curried expression or you are using the default comparator?).

I think that [4] is desirable, but [5] is not worth it.

>
>>> ?
>>>
>>> Although I do like how this looks granted that you are using C++0x's
>>> auto -- in today's C++, the reason I used the STL was to avoid having
>>> to compute the actual type produced by the pipe syntax.
>>
>> You need to know the result type of the reducer even in your example,
>> so it is not specific to the 'sugared' syntax :)
>>
>
> for_each ( range(source) | take(10) | map(mapper()), cout << arg1 <<
> endl ); // with Phoenix
>
> Assuming that there's a boost::for_each(range<T>, F) -- I don't think
> I need to know the result type of the reducer in that example. Am I
> missing something?

There is no reducer (i.e. a fold) in the above expression. If you want
to reduce a range you need to know the result type of the reducer
function if you want to actually save the final result (which is
usually the case :) ).

>
>>> Maybe this is
>>> why Dave is asking for a better BOOST_TYPEOF. ;-)
>>
>> Well, as long as the result type of the final fold has been
>> registered, it should work out of the box.
>>
>
> Of course, registered manually you mean? Or do you rely on
> compiler-specific 'typeof'?

manually if there is no native typeof available.

>
>>>
>>> Okay, but shouldn't this composition with transform_iterator be done
>>> with something that 'comes out of the box'?
>>
>> It is ok to provide a zip+transform in a single function, but it is
>> not a primitive. Let's call it zip_with, its result type should be
>> transformed_range<zipped_range<RangeTuple> , Mapper>, we do not need
>> an explicit zippedWith_range (and in fact it would make deforestation
>> harder).
>>
>
> Shouldn't the deforestation already have happened in the zipping and
> application of the function to yield another tuple?
>

let say you have the rewrite rule:
    map<map<Range,A>,B>  ->  map<Range, compose<A,B> >

If zip_with returns a map<zip<R1, R2>, A>,  you can simplify the
expression map(zip_with(r1, r2, a), b) as:

  map<map<zip<R1, R2>, A>, B> -> map<zip<R1, R2>, compose<A,B> >

without any other special rule. If zip_with were to return a special
zip<R1, R2, A>, you
need a specific rule to handle this case. I.e. zip_with shouldn't be a
primitive, but should be constructed on top of map and zip.

HTH,

-- 
gpd