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

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-06-30 10:51:31

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.

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

>
>>> BOOST_TYPEOF
>
> * Doesn't coordinate with result_of

Should it? How?

>
>>> range_ex
>
> * Not in Boost.  Should have pipe syntax.  Maybe should use expression
> templates and be lazier.

Does it really need expression templates? 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]
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.

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?

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

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

>
>>> our own implementations of std::containers (in interprocess, IIRC)
>
> * Not well-known.
> * Not in a general place (bound to interprocess?)
> * Ought to support move semantics

Yes please. And segmented iterators support for deque, and the
guarantee that every deque subrange is contiguous in memory (it is
great for network programming). And inplace allocation, and...

<snip>
>>> Boost.Iterator
>
> * Needs an update (e.g. "new iterator concepts" have to go -- C++0x
> resolves that differently by simply allowing proxies everywhere)

What about older compilers? Also it would be interesting to have a
mapping between the C++0x solution and the "new iterator concepts".

<snip>

-- 
gpd