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

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-07-07 05:43:20

On Mon, Jul 7, 2008 at 6:29 AM, Dean Michael Berris
<mikhailberis_at_[hidden]> wrote:
> Sorry this took a while.
>
> On Thu, Jul 3, 2008 at 9:20 PM, Giovanni Piero Deretta
> <gpderetta_at_[hidden]> wrote:
>> On Thu, Jul 3, 2008 at 2:32 PM, Dean Michael Berris
>>>
>>> Now that allows you to chain operator|(r, f) infinitely, just making
>>> sure that along the way you create an instance of a specific type
>>> (lazy_range) which when applied a begin(...) or end(...) function will
>>> yield the appropriately constructed iterator.
>>
>> what is the advantage with respect to having 'f' construct the lazy
>> range instead? It just complicates the implementation of operator|.
>>
>
> The advantage would be that if operator| constructed the type by
> itself compared to having 'f' construct the type at runtime, then the
> compiler can (and usually would) perform optimizations on the code it
> generates for the type created by operator|.

Which optimizations cannot be performed by an 'f' that returns a lazy range?

>This is the same reason
> why expression templates work very well for Blitz++ and the ublas
> library IIRC.

<snip blitz example>

>
> If you use expression templates in this situation, you would do away
> with the temporary object(s) created in the intermediate
> multiplication -- and have the compiler optimize the code it creates
> for you because at compile time you're dealing first with types rather
> than values deferred at runtime. The final assignment in the above
> line would perform the necessary traversal(s) and assignments with the
> benefit of the compiler having optimized already everything it would
> have had optimized.
>
> In the case of implementing operator| in this way, we are then able to
> compose/combine the chained lazy range implementation by building the
> type at compile time

This is not a property of operator|(). Any lazy range library I have
seen does it.

> -- where at runtime, the code would have
> benefitted from compiler opimizations.
>
> More concretely, if 'f' created the lazy range, then you'd be passing
> the instance of the temporary range to the next 'f' in the chain, then
> the next, then the next... Then the temporaries you'd be creating are
> wasteful which you would avoid when using expression templates.

The lazy range temporaries returned by the various 'f' are the
equivalent expression templates. Lazy ranges are meant to be very
lightweight (little more that two iterators). I see 0 advantages to
adding another level of complication.

> Having
> a 'lazy_range' allows you to apply your own re-write rules (like what
> you mention below) when the nested 'type' class is accessed to yield a
> real instance of the range.

You can do rewrite rules any way.

<snip>
>
>> Also, how is the above different from
>> mapped_range<filtered_range<taken_range<range_type>, Filter>,Mapper>
>> which is still lazy?
>>
>
> Not much except the actual type yielded by 'lazy_range<T>::type' can
> be what mapped_range<filtered_range<taken_range<range_type>,
> Filter>,Mapper>.

The advantage is?

>
>>>
>>> An instance of this is returned by the whole expression template (the
>>> argument to the construction of the instance would be the original
>>> source range), which we can call begin(...) or end(...) against, and
>>> get the correct iterator type. If we have the above typedefed as
>>> 'some_lazy_range', doing:
>>>
>>> begin(some_lazy_range(source)) -> the beginning of the lazy range
>>> end(some_lazy_range()) -> the 'end' iterator given the lazy range
>>>
>>
>> How this is an unique property of lazy_range? This would work with all
>> the range_ex proposals I have seen so far.
>>
>
> Without expression templates, you'll need extra temporaries (which is
> wasteful) to achieve things with merely lamda's.

Why the extra temporaries will be wasteful? They will be the
equivalent of iterator pairs. In fact they will be exactly the same
thing as a node in an expression template.
<snip>
>>> [...] zip_with can return a range: map<map<zip<transform<R1, F1>,
>>> transform<R2, F2> > >, A>, B> which can still be re-written.
>>>
>>
>> eh? What is transform there? What are F1 and F2?
>>
>
> Given that zipped_with can result a zipped transform iterator, and F1
> and F2 are the types of the functions used/provided with zip_with.

I do not understand. Why you have both map and transform in the same
expression? Map and transform are the same thing, why do you use two
different names?

IMHO zipWith(r1, r2, f) should return

   mapped_range< zipped_range<R1, R2>, F >

Which is the same as map(zip(r1, r2), f).

>
>>> BTW, are the rewrite rules already there, or will this have to be
>>> something that has to still be written using Boost.MPL?
>>
>> Of course not, for now this is just 'wouldn't it be great if...' :)
>>
>
> Which is precisely what can be implemented with lazy_range<...>. :D

See attached for rewrite rules implemented *without* lazy_range.

-- 
gpd