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

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-07-01 14:26:49

On Tue, Jul 1, 2008 at 5:44 PM, David Abrahams <dave_at_[hidden]> wrote:
> Giovanni Piero Deretta wrote:
>> On Mon, Jun 30, 2008 at 3:37 PM, David Abrahams <dave_at_[hidden]> wrote:
>>>> On Thu, Jun 26, 2008 at 9:08 PM, David Abrahams <dave_at_[hidden]> wrote:
>>>>> Here are the parts and topics that I see as being in the category:
>>>>>
>>>>> result_of
>>> * Too hard to define result<> templates for polymorphic function objects.
>>
>> I use a simple adaptor that makes it possible to use  an mpl
>> expression to compute result types.
>
> Not publicly available in Boost

I'm doing a clean up right now and I'll put it in the vault, just in
case anybody wants to take a look.

>
>>> * A whole spate of questions that came up in
>>> http://article.gmane.org/gmane.comp.lib.boost.devel/173370 were not
>>> answered with a page of documentation, utility library, or other
>>> facility.  I still don't know what the upshot was
>>
>> The solution used by Eric is basically the same used by Egg::poly:
>>
>>   http://tinyurl.com/64k4k6
>>
>> I haven't really tried it so far, but it seems pretty good and simple.
>
> IIRC egg didn't pass its review.

No surprise, I did write the only review ;). Still some pieces could
find their way into boost.

>
>>>>> BOOST_TYPEOF
>>> * Doesn't coordinate with result_of
>>
>> Should it? How?
>
> We have this facility called result_of that is used to compute the
> result type of various "function" calls; it requires manual intervention
>  for each function.  We have this facility called BOOST_TYPEOF that
> works (or can be made to work) automatically on many important platforms
> and otherwise requires some manual intervention for each concrete
> user-defined type or template.  It seems obvious to me that the default
> implementation of result_of could use BOOST_TYPEOF, and it would "just
> work" in any environment where BOOST_TYPEOF has native support or where
> types/templates are being registered explicitly.

I still do not see how can you 'fix' BOOST_TYPEOF to deduce const
references correctly.
Without that, you can't implement result_of with boost typeof.

>
>> That is, given the range
>> builders make_*_view [1], it should return a *_view (for example a
>> filtered_view). Combining multiple views, you get for example:
>>
>>    filtered_view<mapped_view<taken_view<BaseRange> , Mapper>, Filter> >
>>
>> I.e.  a series of range views are already an expression templates.
>> Now, if you make some (reasonable, and hopefully documented)
>> assumptions about Filter and Mapper, you should be always able to
>> convert sequences of nested views that contains only views known to
>> range_ex in a normal form: for example:
>>
>>    taken_view<mapped_view<filtered_view<BaseRange, compose<Mapper,
>> Filter> >, Mapper> >
>>
>> You can of course collapse multiple mapped, filtered and taken range
>> in a single instance of each range. [2]
>
> Right, I was thinking of those kinds of optimizations, e.g.
>
>        strided(strided(it,2),10) == strided(it,20)
>
>> A top level boost::for_each could be able to unwind the normalized
>> expression and apply a simple iteration over the Base range instead of
>> relying on the compiler of eliminating the abstraction overhead of
>> four different iterators.
>
> Not sure what you have in mind, but adding smarts to for_each doesn't
> seem very smart to me :-).  You'd have to do the same for every other
> algorithm.

you can use rewrite rules to simplify ranges of ranges, but in the
end, you want to do a smarter traversal to eliminate all abstraction
overhead (exactly for the same reason you would use a segmented
iterator-aware for_each).

I shouldn't have called it for_each, but an optimizing range library
should provide an internal iteration interface that takes care of
eliminating as much abstraction as possible. It would in practice be a
boost::for_each. Any algorithm that can be implemented on top of it
(and I guess that there are many, consider that you can use lazy zip,
map and filter) would benefit from it.

>
>> I think that the basic ranges that should (at least) be supported are:
>>
>>    - mapped_range
>>    - filtered_range
>>    - taken_range (i.e. just the first n elements of a range)
>>    - taken_while_range (i.e. the first elements such as a predicate is true)
>>    - zipped_range
>>    - unfold_range (with which you can pretty much express any other
>> range, see http://tinyurl.com/5mus25)
>>
>> An eventual 'drop' (take all the elements after the first n) and
>> 'drop_while' (drop the first elements such as a predicate is true)
>> probably need strict evaluation anyway and aren't worth supporting
>> explicitly.
>>
>> Finally, what do you mean that range_ex views should be lazier? Lazier
>> than what?
>
> Lazier than they are.  If you avoid building the iterators until you
> have the whole chained view expression, you can do some optimizations
> like I mentioned above.  Again, though, this probably isn't really
> important.

Ah, ok. Would this just be a matter of deferring the iterator
construction only in at an explicit call to begin()/end() over, for
example, a strided_range, or you have in mind something more complex?
(I think the domain you are thinking of is numeric computations, mine
is text processing)

>
>> [1] Btw, I greatly dislike the verbose make_filtered_view,
>> make_transformed_view names. I use these builders a lot, and simply
>> call them 'map' and 'filter'.
>
> Agree.  Who's using the long names?

I think that those name have been proposed for range_ex, but I might
be mistaken.

>
>> [2] I think that this is quite similar to the deforestation technique
>> used by functional languages compilers. (see the wikipedia page and
>> the linked articles). In FP it is used mostly to eliminate
>> intermediate (lazily evaluated) lists, but the same technique can be
>> applied in c++. In fact the rewrite rules used map perfectly to c++
>> templates.
>
> Maybe we're talking about the same thing.

I guess so :)

-- 
gpd