Hi Neil, I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one: 2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.) boost::find[_f,_e]( range, x ) boost::find[_f+1,_e]( range, x ) He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete. I was wondering if you had given any thought to making use of his insights? Especially considering that RangeEx hasn't been used to fully cover a generic domain (I think), it might make sense. -- David Abrahams BoostPro Computing http://boostpro.com
Hi Dave, On Thu, Jul 23, 2009 at 1:48 PM, David Abrahams <dave@boostpro.com> wrote:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
The current syntax that was proposed is not like this. In fact one need do no more than boost::find(range, x) for the default behaviour, but for obtaining a non-default range then something like boost::find<find_end>(range, x) is used. I don't find this very ugly and if one is going to allow a selection of differing return types then the choice needs to be made via a parameter somewhere whether one supports different Range concepts or not. I have briefly considered Alexandrescu's proposal, I am very excited to see a concrete proposal to make Range Concepts first class citizens, but on first glance they appear to introduce a coupling between traversal and access.Having a front() accessor member function as part of a Range Concept means that generic algorithms that are passed a range would need to know they were extracting from the front() or the back(). I haven't had time to think this through completely but it isn't clear to me at least that everything that is currently possible can be done with the suggested concepts. I'm also not sure how to fix the (imagined?) issue. Wouldn't a change of this magnitude require a fresh review? I'm not against doing this. In fact, if Andrei has already an implementation it may be best all around if his version is proposed instead. The current RangeEx is far more modest in it's aims, and perhaps this is simply not going far enough in the light of recent advances. I'd be happy to work with anyone that is interested in thrashing out superior Range Concepts. Also I think it only sensible to offer stepping down in the light of the very heavy weight names that now may be interested in taking this over if this would speed the progress along. I would very much prefer to continue and assist if at all possible without hindering things.
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete. I was wondering if you had given any thought to making use of his insights? Especially considering that RangeEx hasn't been used to fully cover a generic domain (I think), it might make sense.
I have used Boost.RangeEx not just to implement algorithms, but also to implement applications using the algorithms. I'm not really sure this counts for much however. Probably other people using the code would be far more valuable.
-- David Abrahams BoostPro Computing http://boostpro.com
Regards, Neil Groves
on Thu Jul 23 2009, Neil Groves <neil-AT-grovescomputing.com> wrote:
Hi Dave,
On Thu, Jul 23, 2009 at 1:48 PM, David Abrahams <dave@boostpro.com> wrote:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
The current syntax that was proposed is not like this. In fact one need do no more than boost::find(range, x) for the default behaviour, but for obtaining a non-default range then something like boost::find<find_end>(range, x) is used. I don't find this very ugly and if one is going to allow a selection of differing return types then the choice needs to be made via a parameter somewhere whether one supports different Range concepts or not.
At the moment, I'm not really concerned with the specific syntax choice so much as the whole idea that the system composes much better with a ranges-in/ranges-out interface.
I have briefly considered Alexandrescu's proposal, I am very excited to see a concrete proposal to make Range Concepts first class citizens, but on first glance they appear to introduce a coupling between traversal and access.Having a front() accessor member function as part of a Range Concept means that generic algorithms that are passed a range would need to know they were extracting from the front() or the back().
? Sorry, I don't see how that is any different from having an iterator range whose begin iterator can be dereferenced, as the current STL algorithms do. Anyway, front() and back() can always be interchanged by reverse(). I encourage you to consider his work a bit more than briefly.
I haven't had time to think this through completely but it isn't clear to me at least that everything that is currently possible can be done with the suggested concepts. I'm also not sure how to fix the (imagined?) issue.
I don't think it needs fixing, but maybe I'm missing something.
Wouldn't a change of this magnitude require a fresh review?
No; once a library passes review, the maintainer can make arbitrary changes. It's important to be conscientious about that, of course.
I'm not against doing this. In fact, if Andrei has already an implementation it may be best all around if his version is proposed instead.
IIRC he did his work in D, and that his library doesn't exactly have all the features we may want from RangeEx. But it would be a very good idea to discuss what he learned with him and attempt to benefit from it.
The current RangeEx is far more modest in it's aims, and perhaps this is simply not going far enough in the light of recent advances. I'd be happy to work with anyone that is interested in thrashing out superior Range Concepts. Also I think it only sensible to offer stepping down in the light of the very heavy weight names that now may be interested in taking this over if this would speed the progress along. I would very much prefer to continue and assist if at all possible without hindering things.
I don't think any "heavy weight names" have the time to take this over. You got this library accepted; it's your baby. Please don't be intimidated just because I'm suggesting you look at some new ideas.
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete. I was wondering if you had given any thought to making use of his insights? Especially considering that RangeEx hasn't been used to fully cover a generic domain (I think), it might make sense.
I have used Boost.RangeEx not just to implement algorithms, but also to implement applications using the algorithms. I'm not really sure this counts for much however.
It counts for something, but generic programming starts by collecting and surveying *all* the algorithms in a domain and then clustering the requirements of those algorithms into concepts. I'm not sure if your applications demand enough use cases to really prove the Range concept, so to speak. Since the STL started with a complete survey (of a certain class of algorithms), concepts that can be used to implement its algorithms have extra credibility.
Probably other people using the code would be far more valuable.
Always. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams skrev:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete.
If I remember correctly, he claims that his return of find() is the "correct" one. I think that is plain wrong, as the syntax above shows that there are many useful return ranges, perhaps with an obvious default. So the above is not an "issue" IMO, but a usable feature. -Thorsten
Thorsten Ottosen wrote:
David Abrahams skrev:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete.
If I remember correctly, he claims that his return of find() is the "correct" one. I think that is plain wrong, as the syntax above shows that there are many useful return ranges, perhaps with an obvious default.
(Thanks Dave for pointing out this thread to me.) I can think of four useful subranges you might want to look at when searching linearly: the range before the found element (including it or not) and the one after the found element (including it or not). If find() is to work on most ranges, it needs to return the range starting with the found element. Then it's easy to derive the range after the found element by simply popping one element off the range. There remains the case when the range preceding the found element is needed. Requiring find to be able to do that reduces the generality of find(), so the principled approach is to confine that task to a different function. Without having looked at RangeEx, I infer from the code above that for example find[_b, _f] would only work on forward iterators and better, whereas find[_f, _e] would also work on input iterators. During my talk at Boost this same issue was brought again, so after thinking some more about it I found what I think is the principled solution: define a different function that returns the range before the found element. That function is called until(). Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination. So one design is to define find[_b, _f] that works with forward ranges and find[_f, _e] that works with input ranges. With the design proposed above we have until that works with input ranges and find that works with input ranges. That is a net expressiveness win, and the cost is the necessity of defining a new type of range (the one returned by until). Again, I haven't looked at find[] and RangeEx so please apologize if I mis-inferred how it works. Andrei
Andrei Alexandrescu skrev:
I can think of four useful subranges you might want to look at when searching linearly: the range before the found element (including it or not) and the one after the found element (including it or not).
Right. I think more general adjustments might also be useful in some cases.
If find() is to work on most ranges, it needs to return the range starting with the found element. Then it's easy to derive the range after the found element by simply popping one element off the range.
Right.
There remains the case when the range preceding the found element is needed. Requiring find to be able to do that reduces the generality of find(), so the principled approach is to confine that task to a different function. Without having looked at RangeEx, I infer from the code above that for example find[_b, _f] would only work on forward iterators and better, whereas find[_f, _e] would also work on input iterators.
I don't see why that is a problem; it seems like an inherent limitation of input iterators, not of the algorithm.
During my talk at Boost this same issue was brought again, so after thinking some more about it I found what I think is the principled solution: define a different function that returns the range before the found element. That function is called until().
Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination.
Seems useful. But how does this work if you want to have the range [_b,_f) as opposed to [_b,_f+1) ? -Thorsten
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
I can think of four useful subranges you might want to look at when searching linearly: the range before the found element (including it or not) and the one after the found element (including it or not).
Right. I think more general adjustments might also be useful in some cases.
If find() is to work on most ranges, it needs to return the range starting with the found element. Then it's easy to derive the range after the found element by simply popping one element off the range.
Right.
There remains the case when the range preceding the found element is needed. Requiring find to be able to do that reduces the generality of find(), so the principled approach is to confine that task to a different function. Without having looked at RangeEx, I infer from the code above that for example find[_b, _f] would only work on forward iterators and better, whereas find[_f, _e] would also work on input iterators.
I don't see why that is a problem; it seems like an inherent limitation of input iterators, not of the algorithm.
During my talk at Boost this same issue was brought again, so after thinking some more about it I found what I think is the principled solution: define a different function that returns the range before the found element. That function is called until().
Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination.
Seems useful. But how does this work if you want to have the range
[_b,_f)
as opposed to
[_b,_f+1)
?
That sounds like a function before() (or an overload of find() with enough syntactic frosting to be distinguished from other find() functions) that works for forward ranges. (It can't work on input ranges.) I think I'll add before() to D's standard library. Andrei
Andrei Alexandrescu skrev:
Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination.
Is until lazy for all types of ranges? Being lazy is often good, but it's so nice to compose a lazy range with other types of ranges. -Thorsten
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination.
Is until lazy for all types of ranges? Being lazy is often good, but it's so nice to compose a lazy range with other types of ranges.
Yes, until is lazy. I think it couldn't be implemented any other way for input ranges. Andrei
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination.
Is until lazy for all types of ranges? Being lazy is often good, but it's so nice to compose a lazy range with other types of ranges.
A "not" slipped here.
Yes, until is lazy. I think it couldn't be implemented any other way for input ranges.
Ok, but the problem with lazy ranges is that when you compose it with range adaptors, then it greatly limits the adaptors that you can subsequently apply. -Thorsten
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Surprisingly, until() also works on input ranges! It works because it finds the element lazily - it returns a range that tests for termination condition in its .empty() test. So until() returns a range that iterates the original passed-in range until the sought element is found, at which time until() reports termination.
Is until lazy for all types of ranges? Being lazy is often good, but it's so nice to compose a lazy range with other types of ranges.
A "not" slipped here.
Yes, until is lazy. I think it couldn't be implemented any other way for input ranges.
Ok, but the problem with lazy ranges is that when you compose it with range adaptors, then it greatly limits the adaptors that you can subsequently apply.
Why is that the case? Andrei
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
A "not" slipped here.
Yes, until is lazy. I think it couldn't be implemented any other way for input ranges.
Ok, but the problem with lazy ranges is that when you compose it with range adaptors, then it greatly limits the adaptors that you can subsequently apply.
Why is that the case?
because some adapters require random aceesss ranges e.g. rng | stride_view and some requires bidirectionsal ranges e.g. rng | reverse_view -Thorsten
Thorsten Ottosen skrev:
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
A "not" slipped here.
Yes, until is lazy. I think it couldn't be implemented any other way for input ranges.
Ok, but the problem with lazy ranges is that when you compose it with range adaptors, then it greatly limits the adaptors that you can subsequently apply.
Why is that the case?
because some adapters require random aceesss ranges e.g.
rng | stride_view
and some requires bidirectionsal ranges e.g.
rng | reverse_view
And also many later operations are usually more efficient when e.g. random access is preserved. -Thorsten
AMDG Thorsten Ottosen wrote:
Thorsten Ottosen skrev:
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
Ok, but the problem with lazy ranges is that when you compose it with range adaptors, then it greatly limits the adaptors that you can subsequently apply.
Why is that the case?
because some adapters require random aceesss ranges e.g.
rng | stride_view
and some requires bidirectionsal ranges e.g.
rng | reverse_view
And also many later operations are usually more efficient when e.g. random access is preserved.
If only one form of the range adapters is provided, then the lazy form is better, because it is possible to implement the greedy version in terms of the lazy one, but not vice versa. In Christ, Steven Watanabe
Steven Watanabe skrev:
AMDG
Thorsten Ottosen wrote:
Why is that the case?
and some requires bidirectionsal ranges e.g.
rng | reverse_view
And also many later operations are usually more efficient when e.g. random access is preserved.
If only one form of the range adapters is provided, then the lazy form is better, because it is possible to implement the greedy version in terms of the lazy one, but not vice versa.
I think almost all the adaptors are lazy. But that is a somewhat different issue than until() being lazy because until() will be used to form the initial range that adaptors adapt. If until() returns a single-pass range, then the example above fails to work. -Thorsten
Thorsten Ottosen skrev:
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
A "not" slipped here.
Yes, until is lazy. I think it couldn't be implemented any other way for input ranges.
Ok, but the problem with lazy ranges is that when you compose it with range adaptors, then it greatly limits the adaptors that you can subsequently apply.
Why is that the case?
because some adapters require random aceesss ranges e.g.
rng | stride_view
Hm. I don't think stride_view requires rar afterall. Anyway, I think it preserves random access which is nice. -Thorsten
on Thu Jul 23 2009, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:
David Abrahams skrev:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete.
If I remember correctly, he claims that his return of find() is the "correct" one. I think that is plain wrong, as the syntax above shows that there are many useful return ranges, perhaps with an obvious default.
Regardless, there could still be a single correct answer from the standpoint of aesthetics, purity, and orthogonality. If drop_front(find(range, x)) does the same thing as find[_f+1,_e]( range, x ) then you don't need the complicated meta-goop in there.
So the above is not an "issue" IMO, but a usable feature.
Whether or not it's a feature and/or usable isn't relevant to the issue I'm raising. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams skrev:
Regardless, there could still be a single correct answer from the standpoint of aesthetics, purity, and orthogonality. If
drop_front(find(range, x))
does the same thing as
find[_f+1,_e]( range, x )
then you don't need the complicated meta-goop in there.
Then how would you safely implement find[_f-1,_e]( range, x ); ? -Thorsten
on Fri Jul 24 2009, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:
David Abrahams skrev:
Regardless, there could still be a single correct answer from the standpoint of aesthetics, purity, and orthogonality. If
drop_front(find(range, x))
does the same thing as
find[_f+1,_e]( range, x )
then you don't need the complicated meta-goop in there.
Then how would you safely implement
find[_f-1,_e]( range, x );
At first glance, you can't. Is there a known use case for that? If not, it's moot. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams skrev:
on Fri Jul 24 2009, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:
David Abrahams skrev:
Regardless, there could still be a single correct answer from the standpoint of aesthetics, purity, and orthogonality. If
drop_front(find(range, x))
does the same thing as
find[_f+1,_e]( range, x )
then you don't need the complicated meta-goop in there.
So how do we evaluate that aesthetics, purity and orthogonality of the two different approaches? The find interface is one interface with goop, and the other alternative is now at least 5 different functions: find, until, before, drop_front, drop_back.
Then how would you safely implement
find[_f-1,_e]( range, x );
At first glance, you can't. Is there a known use case for that? If not, it's moot.
Who knows. Maybe you want the element before the found one to be there for some reason. -Thorsten
on Sat Jul 25 2009, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:
David Abrahams skrev:
on Fri Jul 24 2009, Thorsten Ottosen <thorsten.ottosen-AT-dezide.com> wrote:
David Abrahams skrev:
Regardless, there could still be a single correct answer from the standpoint of aesthetics, purity, and orthogonality. If
drop_front(find(range, x))
does the same thing as
find[_f+1,_e]( range, x )
then you don't need the complicated meta-goop in there.
So how do we evaluate that aesthetics, purity and orthogonality of the two different approaches?
Lots of hard thinking.
The find interface is one interface with goop, and the other alternative is now at least 5 different functions: find, until, before, drop_front, drop_back.
No, that's not a fair assessment. drop_front and drop_back are useful on their own and in fact I think Andrei is already calling them pop_front and pop_back(?) So we're left with "find, until, and before." What's "before?"
Then how would you safely implement
find[_f-1,_e]( range, x );
At first glance, you can't. Is there a known use case for that? If not, it's moot.
Who knows. Maybe you want the element before the found one to be there for some reason.
"Maybe, for some reason" arguments don't hold much water with me, especially in a library design context. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams <dave <at> boostpro.com> writes:
Then how would you safely implement
find[_f-1,_e]( range, x );
At first glance, you can't. Is there a known use case for that? If not, it's moot.
Who knows. Maybe you want the element before the found one to be there for some reason.
"Maybe, for some reason" arguments don't hold much water with me, especially in a library design context.
Say I have an array of prices active now on exchange. In my algorithm, I come up with some price, and now I want to place my orders 5 levels above and 5 levels below the price I need. With iterators (omitting boundary cases) this would be: it = find( prices.begin(), prices.end(), desired_price ); desired_levels = boost::range( it-5, it+5 ); place_orders( desired_levels ); With the syntax above, what I need is find[_f-5, _f+5](range, x). There can be more examples if this kind, say fancy smoothing an image, when you need to find a pixel and then smooth it over neighbor pixels. Same in numerical calculations on grids - you often take neighbors of what you found into account. Thanks, Maxim (to reply in private, use FirstName.LastName@gmail.com)
On 27 Jul 2009, at 12:39, Maxim Yanchenko wrote:
David Abrahams <dave <at> boostpro.com> writes:
[...]
Same in numerical calculations on grids - you often take neighbors of what you found into account.
In general these are known as 'stencils' http://en.wikipedia.org/wiki/Stencil_(numerical_analysis) In the example above, would it be straightforward to represent the Crank-Nicolson stencil as a range? Or is this not an appropriate application of the concept? Of course this kind of requirement has been tackled before, http://www.oonumerics.org/blitz/manual/blitz04.html Just my, €0.014. ------------------------------------------------ "No more boom and bust." -- Dr. J. G. Brown, 1997
on Mon Jul 27 2009, Maxim Yanchenko <maximyanchenko-AT-yandex.ru> wrote:
David Abrahams <dave <at> boostpro.com> writes:
Then how would you safely implement
find[_f-1,_e]( range, x );
At first glance, you can't. Is there a known use case for that? If not, it's moot.
Who knows. Maybe you want the element before the found one to be there for some reason.
"Maybe, for some reason" arguments don't hold much water with me, especially in a library design context.
Say I have an array of prices active now on exchange. In my algorithm, I come up with some price, and now I want to place my orders 5 levels above and 5 levels below the price I need. With iterators (omitting boundary cases) this would be:
it = find( prices.begin(), prices.end(), desired_price ); desired_levels = boost::range( it-5, it+5 ); place_orders( desired_levels );
With the syntax above, what I need is find[_f-5, _f+5](range, x).
There can be more examples if this kind, say fancy smoothing an image, when you need to find a pixel and then smooth it over neighbor pixels. Same in numerical calculations on grids - you often take neighbors of what you found into account.
My point is not that there are no use cases, it's that there may be reasonably simple ways of expressing these less-common use cases that don't intrude on the interface of find itself, but instead combine find with some orthogonal components. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams skrev:
No, that's not a fair assessment. drop_front and drop_back are useful on their own and in fact I think Andrei is already calling them pop_front and pop_back(?)
So we're left with "find, until, and before." What's "before?"
Andrei said he would be adding before() to support the range [_b,_f) as until() only support [_b,_f+1) -Thorsten
David Abrahams skrev:
No, that's not a fair assessment. drop_front and drop_back are useful on their own and in fact I think Andrei is already calling them pop_front and pop_back(?)
So we're left with "find, until, and before." What's "before?"
Andrei said he would be adding before() to support the range [_b,_f) as until() only support [_b,_f+1) -Thorsten
David Abrahams skrev:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
Of the issues that it does seem to solve are the following: - begin and end iterator does not need to be the same (because there is not two iterators) - simpler specification, better error messages (iterators are somewhat painfull) This has a some irritating implications, like forcing us to store two predicates etc. I haven't done any benchmarking to see how much this is actually a problem. However, I donøt think RangeEx should try to do this design. That's a job for Boost.RangeExEx, or some GSOC project. Also note that with the new C++0x features, we should be able to handle that the begin and end iterator are different types. -Thorsten
Thorsten Ottosen wrote:
However, I donøt think RangeEx should try to do this design. That's a job for Boost.RangeExEx, or some GSOC project.
To be honest, I'd really love to see a ground-up redesign of the STL that uses ranges and takes advantage of some of the other niceties that modern C++ (especially 0x) can provide us. The loss of concepts makes this lose its luster a bit, but perhaps a complete redesign of the STL with concepts in mind (as opposed to trying to put concepts into the current STL) would help to give some insight on how concepts *should* work. I've hesitated on doing much with this, since I'm still trying to figure out a place for multidimensional containers in all this, and they don't map quite so easily onto the concept of ranges (especially with respect to for loops, which are by definition a one-dimensional sequence). - Jim
James Porter wrote:
To be honest, I'd really love to see a ground-up redesign of the STL that uses ranges and takes advantage of some of the other niceties that modern C++ (especially 0x) can provide us. The loss of concepts makes this lose its luster a bit, but perhaps a complete redesign of the STL with concepts in mind (as opposed to trying to put concepts into the current STL) would help to give some insight on how concepts *should* work. This is also a pet peeve of mine. Rebuilding STL w/r to all the thin we know how to do in a proper way now comapred to 198x. Maybe some effort could be put on these.
I've hesitated on doing much with this, since I'm still trying to figure out a place for multidimensional containers in all this, and they don't map quite so easily onto the concept of ranges (especially with respect to for loops, which are by definition a one-dimensional sequence). What about saying that such containers can be walked using a set fo ranges, one per dimension and let then generate nested for loop for each range ?
David Abrahams wrote:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete. I was wondering if you had given any thought to making use of his insights? Especially considering that RangeEx hasn't been used to fully cover a generic domain (I think), it might make sense.
First-class ranges would still need to be convertible to iterator pairs, since iterators are useful on their own as a mean to express positions. For example, let's say I write a simple algorithm that takes three bidirectional iterators: the begin of the sequence, the end of the sequence, and a position anywhere in between. That algorithm then returns whether the position in between lies on a word boundary by reading what is left and right of it. How would I express such an algorithm with ranges only? If we agree that we need iterators anyway, first class ranges would be nothing more than an optimized version of iterator pairs that can only be applied in certain cases; so dealing with iterator pairs as ranges remains needed (and not only for legacy purposes).
Mathias Gaunard wrote:
First-class ranges would still need to be convertible to iterator pairs, since iterators are useful on their own as a mean to express positions.
For example, let's say I write a simple algorithm that takes three bidirectional iterators: the begin of the sequence, the end of the sequence, and a position anywhere in between. That algorithm then returns whether the position in between lies on a word boundary by reading what is left and right of it.
How would I express such an algorithm with ranges only?
Ranges can be collapsed to represent a single element or no elements. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Mathias Gaunard wrote:
Stewart, Robert wrote:
Ranges can be collapsed to represent a single element or no elements.
Yet they would still lack the ability to compare positions.
A one element range represents a position in a container. Ranges can be compared. What am I missing? _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Stewart, Robert wrote:
A one element range represents a position in a container. Ranges can be compared.
Hmm, comparison of ranges is not within the slides I've seen. That would be quite game changing already. Still, can I use std::distance to see how far two positions in a bidirectional range are from each other? Not really.
Mathias Gaunard wrote:
David Abrahams wrote:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.)
boost::find[_f,_e]( range, x )
boost::find[_f+1,_e]( range, x )
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete. I was wondering if you had given any thought to making use of his insights? Especially considering that RangeEx hasn't been used to fully cover a generic domain (I think), it might make sense.
First-class ranges would still need to be convertible to iterator pairs, since iterators are useful on their own as a mean to express positions.
That would limit ranges because there are ranges that are not pairs of iterators.
For example, let's say I write a simple algorithm that takes three bidirectional iterators: the begin of the sequence, the end of the sequence, and a position anywhere in between. That algorithm then returns whether the position in between lies on a word boundary by reading what is left and right of it.
How would I express such an algorithm with ranges only?
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes. Andrei
Andrei Alexandrescu wrote:
That would limit ranges because there are ranges that are not pairs of iterators.
All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything. The issue is that expressing a range as a pair of iterators may not always be optimal.
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive?
Mathias Gaunard skrev:
Andrei Alexandrescu wrote:
That would limit ranges because there are ranges that are not pairs of iterators.
All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything. The issue is that expressing a range as a pair of iterators may not always be optimal.
But in C++0x there should be no problem in having different types of the begin and the end iterator. -Thorsten
That would limit ranges because there are ranges that are not pairs of iterators.
All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything.
Not true. Some ranges can be generated on the fly based upon a predicate (either provided or built into the range type). Ranges in the Boost.Range library are what you've described, but those in Andrei's scheme are not.
The issue is that expressing a range as a pair of iterators may not always be optimal.
Expressing a range as a pair of iterators is not always possible. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Stewart, Robert wrote:
That would limit ranges because there are ranges that are not pairs of iterators. All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything.
Not true. Some ranges can be generated on the fly based upon a predicate (either provided or built into the range type). Ranges in the Boost.Range library are what you've described, but those in Andrei's scheme are not.
I don't see how your message disproves what I said (nor actually, how it is related at all). Boost.Range is just a set of tools to make it more practical to manipulate iterators pairs, which can represent ranges. Alexandrescu offers to ditch iterators and directly define first-class ranges. Yet, in terms of expressiveness, a pair of iterators is not less expressive than Alexandrescu's ranges (discuss below). The only gains there might be are ease-of-defining (but then, if you accept my argument iterators are needed anyway, that gain is moot) and efficiency (which becomes moot too if you allow the two iterators of the pair to be of different types).
The issue is that expressing a range as a pair of iterators may not always be optimal.
Expressing a range as a pair of iterators is not always possible.
They actually seem to be mostly equivalent, except Alexandrescu ranges lack the ability to compare positions. Do you have a single example of a range that can be expressed with Alexandrescu's concepts but not with iterators pairs? Not that unlike what the "Iterators must go" slides claim, iterators can implement the Stride operation just fine.
Mathias Gaunard wrote:
Stewart, Robert wrote:
That would limit ranges because there are ranges that are not pairs of iterators. All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything.
Not true. Some ranges can be generated on the fly based upon a predicate (either provided or built into the range type). Ranges in the Boost.Range library are what you've described, but those in Andrei's scheme are not.
I don't see how your message disproves what I said (nor actually, how it is related at all).
You said all ranges can be expressed as a pair of iterators. I claimed some ranges don't have a predetermined end, so can't be expressed as a pair of iterators. Dave Abrahams correctly noted that it is possible to make an iterator that takes a predicate and, I infer, becomes the end iterator once the range indicated by the predicate has been traversed. Reversing said iterator might be a bit harder. How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs?
Boost.Range is just a set of tools to make it more practical to manipulate iterators pairs, which can represent ranges. Alexandrescu offers to ditch iterators and directly define first-class ranges. Yet, in terms of expressiveness, a pair of iterators is not less expressive than Alexandrescu's ranges (discuss below). The only gains there might be are ease-of-defining (but then, if you accept my argument iterators are needed anyway, that gain is moot) and efficiency (which becomes moot too if you allow the two iterators of the pair to be of different types).
Andrei is far better able to defend his notion of Ranges than I, given the time he's spent working on the idea. However, I don't yet accept as axiomatic that all ranges can be expressed as a pair of iterators. The bottom line is if ranges can be made to very reasonably support all use cases, their other benefits (ease of specification, implementation, and composition) make supplanting iterators with ranges highly desirable. Your questions are good, and must be asked before accepting another system that may prove to make certain things impossible rather than simply difficult or awkward. It may be that keeping both is the only viable choice, but that is not nearly as clean and would permit awkward omissions and overlaps, not to mention making education harder still. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
AMDG Stewart, Robert wrote:
You said all ranges can be expressed as a pair of iterators. I claimed some ranges don't have a predetermined end, so can't be expressed as a pair of iterators. Dave Abrahams correctly noted that it is possible to make an iterator that takes a predicate and, I infer, becomes the end iterator once the range indicated by the predicate has been traversed. Reversing said iterator might be a bit harder.
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs?
Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work. In Christ, Steven Watanabe
Steven Watanabe wrote:
Stewart, Robert wrote:
You said all ranges can be expressed as a pair of iterators. I claimed some ranges don't have a predetermined end, so can't be expressed as a pair of iterators. Dave Abrahams correctly noted that it is possible to make an iterator that takes a predicate and, I infer, becomes the end iterator once the range indicated by the predicate has been traversed. Reversing said iterator might be a bit harder.
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs?
Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work.
That may well work, but the range version would certainly be more straightforward and, as you noted, efficient. Of course, once you permit the iterators to have different types, you also increase the opportunity for mixing them incorrectly, which won't happen with an Alexandrescu range. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Stewart, Robert skrev:
Steven Watanabe wrote:
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs? Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work.
That may well work, but the range version would certainly be more straightforward and, as you noted, efficient. Of course, once you permit the iterators to have different types, you also increase the opportunity for mixing them incorrectly, which won't happen with an Alexandrescu range.
I think we all agree that Alexandrescu ranges are conceptually simpler to implement and specify; however, from a user perspective the two approaches should be be similar. I don't see how having a different type for the end iterator could make incorrect usage easier; for of all we still want to work on ranges as much as possible, and second the type should be uniquely defined for each iterator type such that any misuse is detected at compile time. -Thorsten
Thorsten Ottosen wrote:
Stewart, Robert skrev:
Steven Watanabe wrote:
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs? Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work.
That may well work, but the range version would certainly be more straightforward and, as you noted, efficient. Of course, once you permit the iterators to have different types, you also increase the opportunity for mixing them incorrectly, which won't happen with an Alexandrescu range.
I think we all agree that Alexandrescu ranges are conceptually simpler to implement and specify; however, from a user perspective the two approaches should be be similar.
Well ranges seem to make functional composition easier because one object represents what you need, not two. Andrei P.S. True story: the entire range thing, which is actually painfully obvious, occurred to me when I was finishing D's iterator-based STL. I was dissatisfied with it and was looking for a more expressive abstraction. Somehow an information I got all the way back from 2003 popped up into consciousness. Back then, a visitor gave a talk at University of Washington about a static code analysis tool they had developed at Microsoft Research. Now, the guy said that that tool, whenever it sees a function taking a pointer followed by a size_t, it assumes the size_t is supposed to encode the length of the array pointed to by the pointer. Although the heuristic seems rather wobbly, it turns to be right for virtually all of Microsoft's APIs. (I think they had a way to encode exceptions so as to avoid false positives.) So then the static analysis tool would look at all call sites and make sure the passed arguments would satisfy this constraint. Turns out they found a ton of bugs in Microsoft Office that way - callers would pair pointer and size improperly. During the talk, he mentioned that of course the problem would have been obviated if the APIs used a little abstraction that packaged the pointer and the size together. This information, corroborated with positive experience with built-in slices in D, prompted me to look into an abstraction that encapsulates the iteration limits, not makes them separate entities.
Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
During the talk, he mentioned that of course the problem would have been obviated if the APIs used a little abstraction that packaged the pointer and the size together.
for what it worth I came to exactly the same conclusion while ago and introduced basic_cstring template (in Boost.Test code and in all my day life projects), which is is tiny abstract that wraps two pointers or pointer and size to model any buffers in C like interfaces. I must say it's still one of the most useful little thing I am using in my code. Gennadiy
Gennadiy Rozental a écrit :
Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
During the talk, he mentioned that of course the problem would have been obviated if the APIs used a little abstraction that packaged the pointer and the size together.
for what it worth I came to exactly the same conclusion while ago and introduced basic_cstring template (in Boost.Test code and in all my day life projects), which is is tiny abstract that wraps two pointers or pointer and size to model any buffers in C like interfaces.
Why not use iterator_range, which even works for any iterator? Arguably, it doesn't support pointer + size, only pointer + pointer.
Mathias Gaunard <mathias.gaunard <at> ens-lyon.org> writes:
for what it worth I came to exactly the same conclusion while ago and introduced basic_cstring template (in Boost.Test code and in all my day life projects), which is is tiny abstract that wraps two pointers or pointer and size to model any buffers in C like interfaces.
Why not use iterator_range, which even works for any iterator? Arguably, it doesn't support pointer + size, only pointer + pointer.
basic_cstring predates iterator range by several years. It also have semantic of actual string, unlike iterator_range. Gennadiy
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
Stewart, Robert skrev:
Steven Watanabe wrote:
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs? Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work.
That may well work, but the range version would certainly be more straightforward and, as you noted, efficient. Of course, once you permit the iterators to have different types, you also increase the opportunity for mixing them incorrectly, which won't happen with an Alexandrescu range.
I think we all agree that Alexandrescu ranges are conceptually simpler to implement and specify; however, from a user perspective the two approaches should be be similar.
Well ranges seem to make functional composition easier because one object represents what you need, not two.
By the other approach I meant what Boost.Range and RangeEx is offering. Not the iterator approach. -Thorsten
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
Stewart, Robert skrev:
Steven Watanabe wrote:
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs? Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work.
That may well work, but the range version would certainly be more straightforward and, as you noted, efficient. Of course, once you permit the iterators to have different types, you also increase the opportunity for mixing them incorrectly, which won't happen with an Alexandrescu range.
I think we all agree that Alexandrescu ranges are conceptually simpler to implement and specify; however, from a user perspective the two approaches should be be similar.
Well ranges seem to make functional composition easier because one object represents what you need, not two.
By the other approach I meant what Boost.Range and RangeEx is offering. Not the iterator approach.
Oh, I see. Sorry. I think with Boost::Range you can indeed do what you can do with a primitive range. The downsides that I see are (a) you need to mind the occasional wart, e.g. defining dummy iterators; (b) given that users can always tease out the iterators, you need to define iterators anyway, with the occasional loss in safety or efficiency; (c) you may occasionally waste some space by holding an extra iterator when not needed. The upside is that you have access to a few idioms that are gauche with primitive ranges. One possible way to combine the advantages of the two is to define a flexible interface for Boost::Range(Ex). Say for example that Boost::RangeEx defines empty, front, pop_front, and optionally the obvious extensions for bidir and random-access (back, pop_back, and operator[]). So far so good. People who only need these operations will find them convenient. Now here comes an interesting possibility. Boost::RangeEx also defines a typename Boost::RangeEx::iterator, and begin() and end() that return iterators. But it makes them optional! Meaning, as much as there are forward vs. bidirectional ranges, there are ranges that cloak iterators versus ranges that don't. Then algorithms that do use begin() and end() can only work with "iterator ranges" and those that don't can work with iterator ranges but also with "primitive ranges". Then, whoever wants to define a range either goes through the iterator route or just defines the range primitives. Andrei
On Tue, Jul 28, 2009 at 5:54 PM, Andrei Alexandrescu < andrei@metalanguage.com> wrote:
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Thorsten Ottosen wrote:
Stewart, Robert skrev:
Steven Watanabe wrote:
How about another try: traversing a range with changing criteria?
> A particular range class can take a predicate or some other > traversal influencing argument that can change with each > advance. How would you express that with iterator pairs? > Easily. First of all, consider what's possible if the two iterators are allowed to be different types. Then all the actual state can be put in the first iterator and comparison to the second iterator can just check whether the range is empty. Once you have that, you can use boost::variant to store both iterators as the same type. This will not be efficient, but it will work.
That may well work, but the range version would certainly be more straightforward and,
as you noted, efficient. Of course, once you permit the iterators to have different types, you also increase the opportunity for mixing them incorrectly, which won't happen with an Alexandrescu range.
I think we all agree that Alexandrescu ranges are conceptually simpler to implement and specify; however, from a user perspective the two approaches should be be similar.
Well ranges seem to make functional composition easier because one object represents what you need, not two.
By the other approach I meant what Boost.Range and RangeEx is offering. Not the iterator approach.
Oh, I see. Sorry. I think with Boost::Range you can indeed do what you can do with a primitive range. The downsides that I see are (a) you need to mind the occasional wart, e.g. defining dummy iterators; (b) given that users can always tease out the iterators, you need to define iterators anyway, with the occasional loss in safety or efficiency; (c) you may occasionally waste some space by holding an extra iterator when not needed. The upside is that you have access to a few idioms that are gauche with primitive ranges.
One possible way to combine the advantages of the two is to define a flexible interface for Boost::Range(Ex). Say for example that Boost::RangeEx defines empty, front, pop_front, and optionally the obvious extensions for bidir and random-access (back, pop_back, and operator[]). So far so good. People who only need these operations will find them convenient.
This is what I have prototyped in the Boost.RangeEx code that should be in the trunk soon.
Now here comes an interesting possibility. Boost::RangeEx also defines a typename Boost::RangeEx::iterator, and begin() and end() that return iterators. But it makes them optional! Meaning, as much as there are forward vs. bidirectional ranges, there are ranges that cloak iterators versus ranges that don't. Then algorithms that do use begin() and end() can only work with "iterator ranges" and those that don't can work with iterator ranges but also with "primitive ranges". Then, whoever wants to define a range either goes through the iterator route or just defines the range primitives.
I'm unsure what the Boost::RangeEx::iterator would be, and why we need such a thing. Since we have non-member functions for boost::begin(end), boost::end(rng) we can have ranges that model the newer concepts not implement the begin(), end() ,member functions. It seems that the pop_front(), pop_back(), operator[] map onto advance_begin(), advance_end() on our existing implementation of iterator_range. Currently it appears that the non-member functions already in Boost.RangeEx make the support for both the Boost.Range-esque ranges and the Alexandrescu-esque ranges possible, if not necessarily simple. Why can't we use an iterator adaptor around the range primitive to keep the capability for algorithms based on begin() and end() to work with the new Range primitives? I think this would maintain backward compatibility, while allowing us to define new algorithms taking advantage of the newer concepts.
Andrei
I greatly appreciate your significant time and contributions in helping the C++ and Boost community learn from the work you have done in D. Warmest Regards, Neil Groves
Neil Groves wrote:
I'm unsure what the Boost::RangeEx::iterator would be, and why we need such a thing.
Without having perused either Boost::Range or Boost::RangeEx, I think it's customary to give named access to the underlying iterator type, just like containers e.g. define iterator, size_type etc.
Since we have non-member functions for boost::begin(end), boost::end(rng) we can have ranges that model the newer concepts not implement the begin(), end() ,member functions.
Oh, I see (s/(end)/(rng)/ I guess). That makes sense.
It seems that the pop_front(), pop_back(), operator[] map onto advance_begin(), advance_end() on our existing implementation of iterator_range. Currently it appears that the non-member functions already in Boost.RangeEx make the support for both the Boost.Range-esque ranges and the Alexandrescu-esque ranges possible, if not necessarily simple.
Perfect. But for ranges to catch up, I guess an easier to spell name would be in order... Andrei
On Tue, Jul 28, 2009 at 9:25 PM, Andrei Alexandrescu < andrei@metalanguage.com> wrote:
Neil Groves wrote:
I'm unsure what the Boost::RangeEx::iterator would be, and why we need such a thing.
Without having perused either Boost::Range or Boost::RangeEx, I think it's customary to give named access to the underlying iterator type, just like containers e.g. define iterator, size_type etc.
Oh I see, we have something that achieves a similar goal, I think. We have the iterator type in a typedef within the range classes currently. The prefered manner to write a range algorithm though uses a type generator class: range_iterator< Rng >::type to allow access to the underlying iterator type. This allows extension and support for ranges non-intrusively so we have been able to add range algorithm support seamlessly to even MFC containers, for example. Does this appear optimal to you, or can we improve this arrangement? I have to confess I'm still studying the proposals to have different iterator types for begin and end, and I have yet to fully understand the impact. Hence I will apologise in advance for my ignorance.
Since we have non-member functions for boost::begin(end),
boost::end(rng) we can have ranges that model the newer concepts not implement the begin(), end() ,member functions.
Oh, I see (s/(end)/(rng)/ I guess). That makes sense.
It seems that the
pop_front(), pop_back(), operator[] map onto advance_begin(), advance_end() on our existing implementation of iterator_range. Currently it appears that the non-member functions already in Boost.RangeEx make the support for both the Boost.Range-esque ranges and the Alexandrescu-esque ranges possible, if not necessarily simple.
Perfect. But for ranges to catch up, I guess an easier to spell name would be in order...
You are completely correct. I will probably be plagurising your work for these, if that is acceptable.
Andrei
Regards, Neil Groves
on Tue Jul 28 2009, Neil Groves <neil-AT-grovescomputing.com> wrote:
On Tue, Jul 28, 2009 at 9:25 PM, Andrei Alexandrescu < andrei@metalanguage.com> wrote:
Neil Groves wrote:
I'm unsure what the Boost::RangeEx::iterator would be, and why we need such a thing.
Without having perused either Boost::Range or Boost::RangeEx, I think it's customary to give named access to the underlying iterator type, just like containers e.g. define iterator, size_type etc.
Oh I see, we have something that achieves a similar goal, I think. We have the iterator type in a typedef within the range classes currently. The prefered manner to write a range algorithm though uses a type generator class: range_iterator< Rng >::type to allow access to the underlying iterator type. This allows extension and support for ranges non-intrusively so we have been able to add range algorithm support seamlessly to even MFC containers, for example. Does this appear optimal to you, or can we improve this arrangement?
That's basic state-of-the-art for C++03 generic libraries, so I doubt there's much room for improvement within the current language. Well, you could use the concept check library to define the associated types within the concept classes; that's a slightly more forward-looking approach. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Neil Groves skrev:
On Tue, Jul 28, 2009 at 9:25 PM, Andrei Alexandrescu <
I have to confess I'm still studying the proposals to have
different iterator types for begin and end, and I have yet to fully understand the impact. Hence I will apologise in advance for my ignorance.
I don't it is worth doing right now, but could be done with a new range_end_iterator<Rng>::type . But let's wait with this stuff. -Thorsten
Neil Groves wrote:
I have to confess I'm still studying the proposals to have different iterator types for begin and end, and I have yet to fully understand the impact.
There is a probably a design that would allow to keep compatibility with older Boost.Range-based code. If the end type is convertible to the begin type, it should probably be enough. iterator_range could take an optional second parameter, and the range_end_iterator meta-function would give the real type of the end iterator while range_iterator would still give the type of the begin one. The only fundamental thing that would change behavior is boost::end, since it could potentially return a different type, but it being convertible should be enough not to break compatibility. So it's not too much work: - Add range_end_iterator meta-function, which by default is the same as range_iterator - Update pair<T1, T2> to provide that meta-function - Change end to return the type defined by range_end_iterator - Update iterator_range and potentially sub_range (I don't know how the latter is implemented) so that they take into account a possible different type for the end, define range_end_iterator correctly, and make them use compressed_pair in case the end is empty. Then you can go and optimize the various algorithms and Boost.Foreach, albeit they would still work without being modified. What would be really interesting, however, is a mechanism similar to that of iterator_facade to define ranges with an empty end iterator painlessly.
Mathias Gaunard wrote:
The only fundamental thing that would change behavior is boost::end, since it could potentially return a different type, but it being convertible should be enough not to break compatibility.
Actually no, my bad, it doesn't work. template<typename Iterator> void do_something(Iterator begin, Iterator end); do_something(begin(range), end(range)); would fail. boost::end must remain conservative, while boost::real_end (for lack of a better name) can return a different type.
Andrei Alexandrescu wrote:
Now here comes an interesting possibility. Boost::RangeEx also defines a typename Boost::RangeEx::iterator, and begin() and end() that return iterators. But it makes them optional! Meaning, as much as there are forward vs. bidirectional ranges, there are ranges that cloak iterators versus ranges that don't.
Would there be any reason for a range not to provide iterators except those iterators being hard to write? In case there is none, I don't think it's such a good idea to use concept refining for a non conceptual difference, but rather an implementation difficulty.
Mathias Gaunard wrote:
Andrei Alexandrescu wrote:
Now here comes an interesting possibility. Boost::RangeEx also defines a typename Boost::RangeEx::iterator, and begin() and end() that return iterators. But it makes them optional! Meaning, as much as there are forward vs. bidirectional ranges, there are ranges that cloak iterators versus ranges that don't.
Would there be any reason for a range not to provide iterators except those iterators being hard to write?
In case there is none, I don't think it's such a good idea to use concept refining for a non conceptual difference, but rather an implementation difficulty.
It's not only implementation difficulty. I have many ranges that make next no sense as iterators. For example I have a range that spits out random numbers. The notion is very easy to fathom as a range, but forcing it into the iterator framework would be forced for the designer as well as the user of the notion. The design would be a net loss for everybody if it were required to define an iterator. Andrei
on Tue Jul 28 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Mathias Gaunard wrote:
Andrei Alexandrescu wrote:
Now here comes an interesting possibility. Boost::RangeEx also defines a typename Boost::RangeEx::iterator, and begin() and end() that return iterators. But it makes them optional! Meaning, as much as there are forward vs. bidirectional ranges, there are ranges that cloak iterators versus ranges that don't.
Would there be any reason for a range not to provide iterators except those iterators being hard to write?
In case there is none, I don't think it's such a good idea to use concept refining for a non conceptual difference, but rather an implementation difficulty.
I'm very sympathetic to that point of view.
It's not only implementation difficulty. I have many ranges that make next no sense as iterators. For example I have a range that spits out random numbers. The notion is very easy to fathom as a range, but forcing it into the iterator framework would be forced for the designer as well as the user of the notion. The design would be a net loss for everybody if it were required to define an iterator.
Despite your first sentence above, it sounds exactly like you're saying it's just an implementation difficulty. Generator iterators are well-known, just like istream and ostream "iterators," and we have libraries that can help with implementation. However, not using refinement doesn't imply forcing ranges into the iterator framework Thinking in terms of (deferred) C++0x concepts, I'd write the Range concept that has no iterators, then write the IteratorRange concept that has iterators, then I'd provide a concept_map template that maps Range onto IteratorRange by providing default implementations. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Stewart, Robert wrote:
Andrei is far better able to defend his notion of Ranges than I, given the time he's spent working on the idea. However, I don't yet accept as axiomatic that all ranges can be expressed as a pair of iterators.
The bottom line is if ranges can be made to very reasonably support all use cases, their other benefits (ease of specification, implementation, and composition) make supplanting iterators with ranges highly desirable.
Good points (also those I snipped too, I just have a high-level response). I'm pretty sure most of what ranges do, iterators can be made to do with enough effort and attention because iterators are lower level. The problem is, the effort in defining and manipulating such abstractions is just too high. (And programmers voted with their code: there just aren't that many awesome iterators out there.) For one, the designs feel off-key - for example, std::istream_iterator, with its useless "end" iterator, just hurts. Or if you want to express a random number generator or a mathematical series, how naturally are they modeled with iterators? And then how easy is it to manipulate all of the above? One secondary issue is that designs with iterators are so unduly complex, we got used to the idea that a container offers ONE iterator (and one const_iterator). This is just odd if you look at it with a fresh eye. How about multidimensional containers? Should there really be only one way to span them? Ranges eliminate enough of the unneeded complexity to allow you to define several ranges that work on a container type. Conversely, there are designs that are more efficient with iterators. I think those are few and far apart enough to not render me worried. Andrei
2009/7/24 Stewart, Robert <Robert.Stewart@sig.com>:
How about another try: traversing a range with changing criteria? A particular range class can take a predicate or some other traversal influencing argument that can change with each advance. How would you express that with iterator pairs?
At worst, it seems like you could always define a range_iterator<R> that holds a shared_ptr<R> and just forward to the range operations, with a null shared_ptr representing the "end" iterator. I agree it's inefficient, but I don't think that ranges can represent anything that iterators cannot (given sufficient contortion).
2009/7/24 Mathias Gaunard <mathias.gaunard@ens-lyon.org>:
The only gains there might be are ease-of-defining (but then, if you accept my argument iterators are needed anyway, that gain is moot) and efficiency (which becomes moot too if you allow the two iterators of the pair to be of different types).
Ranges are safer than iterators, and fully checked versions are much more efficient. Simpler templates will result in faster compiles and nicer error messages - especially without concepts. Daniel
on Fri Jul 24 2009, "Stewart, Robert" <Robert.Stewart-AT-sig.com> wrote:
That would limit ranges because there are ranges that are not pairs of iterators.
All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything.
Not true. Some ranges can be generated on the fly based upon a predicate (either provided or built into the range type).
It's possible to create an iterator type that can express the same range. However, it may be ugly and less efficient than necessary. The fundamental constraint is that a range built of iterators must be expressed as two copies of the same datatype, and some ranges don't fit that paradigm well. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Mathias Gaunard wrote:
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive?
To be clearer, let's suppose I want to do the following with Alexandresuc ranges. range r = myrange; for(range r = myrange; !r.empty(); r.popFront()) { if(is_word_boundary(???, r)) { // ... } } "???" could be something like complement(myrange, r) but I don't see how to implement that generically other than linearly, and still that would require a primitive to compare ranges. the iterator solution, however, is straightforward: for(iterator it = myrange.begin(); it != myrange.end(); ++it) { if(is_word_boundary(myrange.begin(), it, myrange.end()) { // ... } }
on Fri Jul 24 2009, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:
To be clearer, let's suppose I want to do the following with Alexandresuc ranges.
range r = myrange; for(range r = myrange; !r.empty(); r.popFront()) { if(is_word_boundary(???, r)) { // ... } }
"???" could be something like complement(myrange, r) but I don't see how to implement that generically other than linearly, and still that would require a primitive to compare ranges.
the iterator solution, however, is straightforward:
for(iterator it = myrange.begin(); it != myrange.end(); ++it) { if(is_word_boundary(myrange.begin(), it, myrange.end()) { // ... } }
That's a good question. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG David Abrahams wrote:
on Fri Jul 24 2009, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:
To be clearer, let's suppose I want to do the following with Alexandresuc ranges.
range r = myrange; for(range r = myrange; !r.empty(); r.popFront()) { if(is_word_boundary(???, r)) { // ... } }
"???" could be something like complement(myrange, r) but I don't see how to implement that generically other than linearly, and still that would require a primitive to compare ranges.
the iterator solution, however, is straightforward:
for(iterator it = myrange.begin(); it != myrange.end(); ++it) { if(is_word_boundary(myrange.begin(), it, myrange.end()) { // ... } }
That's a good question.
Looking at the D documentation, it looks like it can only be done with a random access range, which supports index based slicing. In Christ, Steven Watanabe
Mathias Gaunard wrote:
Andrei Alexandrescu wrote:
That would limit ranges because there are ranges that are not pairs of iterators.
All ranges can be expressed as pairs of iterators, so I hardly see how that limits anything. The issue is that expressing a range as a pair of iterators may not always be optimal.
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive?
There's no such need (a range could define it though). A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside. So when you move one direction it would be difficult to grow one range (shrinking the other is easy). That design would benefit from letting the iterator abstraction exposed. Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit. I'm sure there are other designs that would be similarly problematic. That's expected because, again, ranges are a higher level abstraction and there's always an inevitable loss. What is encouraging is that most iterator-based designs (including STL) benefit when converted to ranges, and that ranges simplify matters enough to open the mind to new possibilities. Andrei
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)?
You can, but that doubles the memory eaten by the index. Andrei
On Sat, Jul 25, 2009 at 7:11 AM, Andrei Alexandrescu < andrei@metalanguage.com> wrote:
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Another example of an iterator-based design that's not easy to
replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)?
You can, but that doubles the memory eaten by the index.
Isn't it possible to create single element ranges from every iterator by slightly modifying its interface to fulfill a range concept (without additional memory requirements)? -Kai
on Sat Jul 25 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)?
You can, but that doubles the memory eaten by the index.
I'm not seeing that. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)?
How would you implement popFront() without storing two iterators, an iterator and a bool, or something? In Christ, Steven Watanabe
Steven Watanabe wrote:
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)?
How would you implement popFront() without storing two iterators, an iterator and a bool, or something?
I guess an iterator you can set to some special value might do the trick. For example, that special value may be an iterator to a static instance of a dummy element, or in the case of pointers 0.
on Sat Jul 25 2009, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Can't you handle that by storing a range that always contains only one element: [iterator,iterator+1)?
How would you implement popFront() without storing two iterators, an iterator and a bool, or something?
popFront needs to be allowed to return a different range type, I guess. OK, that complicates the abstraction. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Andrei Alexandrescu skrev:
Mathias Gaunard wrote:
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive?
There's no such need (a range could define it though).
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside. So when you move one direction it would be difficult to grow one range (shrinking the other is easy). That design would benefit from letting the iterator abstraction exposed.
Couldn't it be done with a special range that stores three iterators? -Thorsten
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside. So when you move one direction it would be difficult to grow one range (shrinking the other is easy). That design would benefit from letting the iterator abstraction exposed.
Couldn't it be done with a special range that stores three iterators? You could introduce SplittableRange, which has four additional primitives:
splitpoint_advance: Move split point one step towards end. Throw/abort/nasal demons if it's already there. splitpoint_retreat: Move split point one step towards begin. See above. front: Return the range between begin and split point. rear: Return the range between split point and end. A special range that stores three iterators would be an implementation possibility. For random-access iterators, you can also use two iterators and an index, and there should be a range adapter that converts any random-access range into a splittable range. Sebastian
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Mathias Gaunard wrote:
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive?
There's no such need (a range could define it though).
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside. So when you move one direction it would be difficult to grow one range (shrinking the other is easy). That design would benefit from letting the iterator abstraction exposed.
Couldn't it be done with a special range that stores three iterators?
Yes, but not within the current primitive set. Sebastian's suggested interface extension should work. Andrei
on Sat Jul 25 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Mathias Gaunard wrote:
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes.
Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive?
There's no such need (a range could define it though).
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside. So when you move one direction it would be difficult to grow one range (shrinking the other is easy). That design would benefit from letting the iterator abstraction exposed.
Couldn't it be done with a special range that stores three iterators?
Yes, but not within the current primitive set. Sebastian's suggested interface extension should work.
That isn't necessarily a good idea, though. Complicating the Range abstraction undermines one of the best arguments in favor of the Range abstraction. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Sat Jul 25 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Thorsten Ottosen wrote:
Andrei Alexandrescu skrev:
Mathias Gaunard wrote:
You would pass two adjacent ranges, like D's bringToFront (a generalization of STL's rotate, see http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html) takes. Nice idea, that could work. But how can I generate those two adjacent ranges in the first place at reasonable costs? Do ranges requires to provide a constant time "complement" primitive? There's no such need (a range could define it though).
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside. So when you move one direction it would be difficult to grow one range (shrinking the other is easy). That design would benefit from letting the iterator abstraction exposed. Couldn't it be done with a special range that stores three iterators? Yes, but not within the current primitive set. Sebastian's suggested interface extension should work.
That isn't necessarily a good idea, though. Complicating the Range abstraction undermines one of the best arguments in favor of the Range abstraction.
True, but I was expecting that. The thing is, I started with the absolutely minimal interface that could have ever worked (three functions: empty, front, popFront). I'd expected I'll need some more primitives, but I wanted to postpone defining them until the need arises. Turns out a great deal of useful stuff can be done with those three functions alone (plus the obvious addenda for bidirectional and random access). I was still expecting that at some point more primitives would be needed (without being clear on what those primitives should look like), so I'm glad that this discussion is underway because it helps crystalizing those primitives. To me, finding that the range abstraction has shortcomings is therefore not a sign that we need to forgo it and get back to iterators, or that we need to have both iterators and ranges; it's simply an acknowledgment that the range design still needs completion. Andrei
Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index. (Thanks Emil Dotchevski for pointing that out during my talk. (Marshall Clow promised the video will be available Real Real Soon Now(tm).)) In Multi-Index, indexes store iterators; storing ranges would often waste twice the space for little or no benefit.
Hi, I'm afraid I'm lacking the background to understand the discussion, but why is Boost.MultiIndex any different to other STL containers? What's the particular functionality that's posing the problem? Maybe I can answer this to myself if you could refer me to some material I can read in order to fully understand your proposals. Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside.
I don't see a problem with this case. The limits are a range, and the internal bidirectional iterator is a subrange of that range. There's no reason why a subrange couldn't be allowed to grow since we know its enclosing range.
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index.
Right. Suffix arrays are a similar case (indeed, suffix arrays can be represented straightforwardly with Boost.MultiIndex). However, I suspect that the overwhelming majority of uses of Boost.MultiIndex are better thought of as permutations rather than a containers-of-iterators. If there was an abstract notion of permutation that was just as high-level as ranges, most of these problems may go away. I say "most". I've used a containter-of-iterators to represent inverted indexes, and they are definitely not permutations. Andrew Bromage
Andrew Bromage wrote:
Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
A design that has a bidirectional iterator walking freely up and down between two limits would be difficult to port to ranges. (If the iterator is random-access, things are trivial.) Ranges can only shrink, they never grow unless assigned from the outside.
I don't see a problem with this case. The limits are a range, and the internal bidirectional iterator is a subrange of that range. There's no reason why a subrange couldn't be allowed to grow since we know its enclosing range.
Another example of an iterator-based design that's not easy to replicate with ranges is Boost Multi-Index.
Right. Suffix arrays are a similar case (indeed, suffix arrays can be represented straightforwardly with Boost.MultiIndex).
However, I suspect that the overwhelming majority of uses of Boost.MultiIndex are better thought of as permutations rather than a containers-of-iterators. If there was an abstract notion of permutation that was just as high-level as ranges, most of these problems may go away.
I say "most". I've used a containter-of-iterators to represent inverted indexes, and they are definitely not permutations.
Incidentally I've implemented an inverted index as a random-access range of input ranges, and found it an extremely satisfying design. Probably it's the best range-based design I put together so far. The random-access range is maintained as a binary heap so you can always extract the smallest entity from the inverted index. You popFront that entity from the top inverted list and then reestablish the heap property if needed. Doing that is cheap because you swap input ranges (small). Whenever one of the inverted lists gets exhausted, it is eliminated from the random-access range. The search ends when the random-access range is exhausted. Andrei
G'day all. Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
Incidentally I've implemented an inverted index as a random-access range of input ranges, and found it an extremely satisfying design. Probably it's the best range-based design I put together so far.
I'm sure it was very easy to design and code (and from your description, it does indeed sound neat), but I'm guessing that it suffers from the same memory usage problem as Boost.MultiIndex. Andrew Bromage
Andrew Bromage wrote:
G'day all.
Andrei Alexandrescu <andrei <at> metalanguage.com> writes:
Incidentally I've implemented an inverted index as a random-access range of input ranges, and found it an extremely satisfying design. Probably it's the best range-based design I put together so far.
I'm sure it was very easy to design and code (and from your description, it does indeed sound neat), but I'm guessing that it suffers from the same memory usage problem as Boost.MultiIndex.
What is the memory usage problem you're referring to? Thanks, Andrei
AMDG David Abrahams wrote:
He says he's implemented a superset of the STL algorithms with it so we know the expressive power is fairly complete. I was wondering if you had given any thought to making use of his insights? Especially considering that RangeEx hasn't been used to fully cover a generic domain (I think), it might make sense.
One thing that I'm not entirely sure how to implement using ranges alone is regex_search. The basic problem is that in order to implement match_results, we need to create a sub-range delimited by two iterators *both of which are derived from the begin iterator* Ranges effectively make the begin and end iterators completely disjoint. In Christ, Steven Watanabe
On Thu, Jul 23, 2009 at 13:48, David Abrahams<dave@boostpro.com> wrote:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
That looks very interesting. Is there any documentation on this out there? I found the slides: http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/... and documentation for a D implementation: http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html http://www.digitalmars.com/d/2.0/phobos/std_range.html I'm wondering why "popFront()" is mutable and edits the range rather than return a range without the first element. The latter might allow compile-time heterogeneous sequences (like boost::fusion::vector) to conform to this range concept as well. I just realised you could then write a foreach function that works on both homogeneous and heterogeneous sequences basically like: template <class Range, class Function> void foreach (Range range, Function function) { if (!range.empty()) { function (range.front()); foreach (range.popFront(), function); } } Is popFront() mutable just for efficiency? Or is there something else I'm missing? Cheers, Rogier
Rogier van Dalen wrote:
On Thu, Jul 23, 2009 at 13:48, David Abrahams<dave@boostpro.com> wrote:
Hi Neil,
I'm sure someone already spoke to you about this, but just in case: Andrei Alexandrescu gave a very interesting presentation at BoostCon that was based on a "ranges only" approach that should eliminate issues like this one:
That looks very interesting. Is there any documentation on this out there? I found the slides:
http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/...
and documentation for a D implementation: http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html http://www.digitalmars.com/d/2.0/phobos/std_range.html
I'm wondering why "popFront()" is mutable and edits the range rather than return a range without the first element. The latter might allow compile-time heterogeneous sequences (like boost::fusion::vector) to conform to this range concept as well. I just realised you could then write a foreach function that works on both homogeneous and heterogeneous sequences basically like:
template <class Range, class Function> void foreach (Range range, Function function) { if (!range.empty()) { function (range.front()); foreach (range.popFront(), function); } }
Is popFront() mutable just for efficiency? Or is there something else I'm missing?
It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient. Andrei
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Is popFront() mutable just for efficiency? Or is there something else I'm missing?
It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient.
Could you describe the efficiency problem in more detail? I think it might be solvable. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Is popFront() mutable just for efficiency? Or is there something else I'm missing? It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient.
Could you describe the efficiency problem in more detail? I think it might be solvable.
Well a simple example is that a range in a contiguous array is a fat pointer, e.g. (begin,end). To bump a range in-place you need to change one pointer; returning a new range would have you copy two pointers. It turns out that the difference is sensible for some loops. In the general case, an unbounded amount of state would have to be returned from r.next. Now, here's what I think you might be thinking. The idiomatic use is r = r.next(). Since there is reassignment, a possibility is to: (a) have r.next() return a small proxy type Proxy that saves a reference to the range (b) have Range::operator=(Proxy) detect reassignment from itself and only operate the minimum update. (c) also define Range::Range(Proxy) for completeness. After all has been said and done, the overhead is one word copied and one more test. I hadn't thought of that. Andrei
on Mon Jul 27 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Is popFront() mutable just for efficiency? Or is there something else I'm missing? It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient.
Could you describe the efficiency problem in more detail? I think it might be solvable.
Well a simple example is that a range in a contiguous array is a fat pointer, e.g. (begin,end). To bump a range in-place you need to change one pointer; returning a new range would have you copy two pointers. It turns out that the difference is sensible for some loops.
If compilers can't optimize that overhead away, I'm disappointed in them ;-( Did you check?
In the general case, an unbounded amount of state would have to be returned from r.next.
Now, here's what I think you might be thinking. The idiomatic use is r = r.next(). Since there is reassignment, a possibility is to:
(a) have r.next() return a small proxy type Proxy that saves a reference to the range
(b) have Range::operator=(Proxy) detect reassignment from itself and only operate the minimum update.
(c) also define Range::Range(Proxy) for completeness.
After all has been said and done, the overhead is one word copied and one more test. I hadn't thought of that.
Yep, those are the lines along which I was thinking. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Mon Jul 27 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Is popFront() mutable just for efficiency? Or is there something else I'm missing? It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient. Could you describe the efficiency problem in more detail? I think it might be solvable. Well a simple example is that a range in a contiguous array is a fat pointer, e.g. (begin,end). To bump a range in-place you need to change one pointer; returning a new range would have you copy two pointers. It turns out that the difference is sensible for some loops.
If compilers can't optimize that overhead away, I'm disappointed in them ;-(
Did you check?
I did, but not the trick with the proxy. One other source of concern was that people would write r.next() instead of r = r.next() (expecting that r.next modifies r in place) and then get confused that they got an infinite loop. In contrast, writing r = r.popBack() is a compile-time error because popBack returns void, so there's no doubt that r.popBack() is the expected way to bump a range. Andrei
On Mon, Jul 27, 2009 at 7:42 PM, Andrei Alexandrescu<andrei@metalanguage.com> wrote:
David Abrahams wrote:
on Mon Jul 27 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Is popFront() mutable just for efficiency? Or is there something else I'm missing?
It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient.
Could you describe the efficiency problem in more detail? I think it might be solvable.
Well a simple example is that a range in a contiguous array is a fat pointer, e.g. (begin,end). To bump a range in-place you need to change one pointer; returning a new range would have you copy two pointers. It turns out that the difference is sensible for some loops.
If compilers can't optimize that overhead away, I'm disappointed in them ;-(
Did you check?
I did, but not the trick with the proxy.
FWIW, I did a test today: with plain pointers, vector iterators and lists there is no overhead in the non mutating next; in fact the compiler (a recent GCC, at O3 optimization level) generate exactly the same object code for a for loop using the non mutating next and the inplace next. In fact it generates the exact same code of an hand written loop using plain pointers. Other containers are another story though, while I'm not surprised by the inefficiency of map and set iterators (it generates calls to non inlined functions), deque is a sore thumb: every copy constructor and assignment in the source code is explicitly translated to a copy in the generated assembler. Maybe it is because deque iterators are fairly large and GCC gives up optimizing away moves to and from memory. Tomorrow I will do some tests with boost iterator adapters. -- gpd
On Mon, Jul 27, 2009 at 22:39, Giovanni Piero Deretta<gpderetta@gmail.com> wrote:
Other containers are another story though, while I'm not surprised by the inefficiency of map and set iterators (it generates calls to non inlined functions), deque is a sore thumb: every copy constructor and assignment in the source code is explicitly translated to a copy in the generated assembler. Maybe it is because deque iterators are fairly large and GCC gives up optimizing away moves to and from memory.
BTW, are you using pairs of iterators for each of those? But is that always the best way of implementing a range in a red-black tree (e.g., a set or a map)? I don't know whether this goes for all conceivable implementations, but when I implemented a red-black tree long ago, its iterator would know its end. In that case, ranges until the end of the container would require only one iterator, and possibly a pointer to the container. This would require, however, that r.pop_back() (whatever its spelling) is allowed to return a different type than r itself is. So I think one-way iteration over a map or set could actually be faster with ranges than with iterators, if the implementation of the ranges knows the container's innards. Cheers, Rogier
On Mon, Jul 27, 2009 at 18:42, Andrei Alexandrescu<andrei@metalanguage.com> wrote:
David Abrahams wrote:
on Mon Jul 27 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
David Abrahams wrote:
on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
Is popFront() mutable just for efficiency? Or is there something else I'm missing?
It's only efficiency. I was very attracted to popFront returning the new range (100% functional interface!) but I gave up for efficiency reasons. I didn't want iteration with ranges to be cool and iteration with other means to be efficient.
Could you describe the efficiency problem in more detail? I think it might be solvable.
Well a simple example is that a range in a contiguous array is a fat pointer, e.g. (begin,end). To bump a range in-place you need to change one pointer; returning a new range would have you copy two pointers. It turns out that the difference is sensible for some loops.
If compilers can't optimize that overhead away, I'm disappointed in them ;-(
Did you check?
I did, but not the trick with the proxy.
I just tried iteration with a (begin, end) range and immutable bump without the proxy trick. I see no performance difference with using raw pointers. This is gcc 4.3 and -O3.
One other source of concern was that people would write r.next() instead of r = r.next() (expecting that r.next modifies r in place) and then get confused that they got an infinite loop. In contrast, writing r = r.popBack() is a compile-time error because popBack returns void, so there's no doubt that r.popBack() is the expected way to bump a range.
I started writing a prototype implementation of something like this over the weekend. It currently uses a free function to bump a range. "r = bump_front(r)" may be less confusing than a method. (My motivation for using free functions was independent of this: the interface of range adaptors seems to become cleaner.) I would be very interested in unifying interfaces of homogeneous and heterogeneous containers, and I'm now starting to believe that that is actually possible. My interest is not entirely frivolous, because I've started to need this recently. Cheers, Rogier
participants (20)
-
Andrei Alexandrescu -
Andrew Bromage -
Daniel James -
David Abrahams -
Edward Grace -
Gennadiy Rozental -
Giovanni Piero Deretta -
James Porter -
Joaquin M Lopez Munoz -
Joel Falcou -
Kai Schroeder -
Mathias Gaunard -
Maxim Yanchenko -
Neil Groves -
Rogier van Dalen -
Scott McMurray -
Sebastian Redl -
Steven Watanabe -
Stewart, Robert -
Thorsten Ottosen