1 Jul
2008
1 Jul
'08
6:26 p.m.
On Tue, Jul 1, 2008 at 5:44 PM, David Abrahams <dave@boostpro.com> wrote: > Giovanni Piero Deretta wrote: >> On Mon, Jun 30, 2008 at 3:37 PM, David Abrahams <dave@boostpro.com> wrote: >>>> On Thu, Jun 26, 2008 at 9:08 PM, David Abrahams <dave@boostpro.com> 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