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

From: David Abrahams (dave_at_[hidden])
Date: 2008-07-01 11:44:18

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

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

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

>>>> range_ex
>> * Not in Boost.  Should have pipe syntax.  Maybe should use expression
>> templates and be lazier.
> 
> Does it really need expression templates? 

No, that probably doesn't rise to the same level of importance as the
other things I've been mentioning. It was a bit of an idle thought.

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

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

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

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

>>>> 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 hash containers

> 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? 

What about them?

> Also it would be interesting to have a
> mapping between the C++0x solution and the "new iterator concepts".

I prefer not to haul that legacy around

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com