Re: state of ranges
On Wed, Dec 13, 2017 at 03:33:51PM -0500, Steven Schveighoffer via
Digitalmars-d wrote:
> On 12/13/17 2:33 PM, Jonathan M Davis wrote:
[...]
> The best way I think to have ranges work is to only modify them in
> popFront/popBack, and the ctor.
[...]
I don't see anything wrong with doing work in .empty or .front, as long
as the overall result looks the same. Sometimes, if .front is expensive
to compute, you may want to defer the work until it's actually needed.
For this, a caching implementation of .front might work best, though at
the cost of slightly more complexity:
struct MyRange {
private WorkParams params;
private Nullable!T frontValue;
@property bool empty() { ... }
@property T front() {
if (frontValue.isNull)
{
frontValue = doExpensiveWork(params);
}
return frontValue;
}
void popFront() {
params = setupNextItemParams();
}
}
The use of Nullable here is just for illustration, of course. In an
actual implementation you can probably find cheaper ways of doing the
same thing.
T
--
My program has no bugs! Only undocumented features...
Re: state of ranges
On Wednesday, 13 December 2017 at 10:15:10 UTC, ag0aep6g wrote: `front` can't assume that `empty` has been called before. For a well-behaved range, `front` must work the same whether you've called `empty` or not (given that the range isn't actually empty). That last point is what I meant: it cannot assume empty() being called BUT it can assume that it WOULD have returned false it it were. So there is no problem with the program crashing when calling front() of an empty range. Therefore, there is no need to manually do stuff like if(inited) because if the elements are not initialized, the range would obviously be empty. Assuming I understood the intention of that code correctly.
Re: state of ranges
On 12/13/17 2:33 PM, Jonathan M Davis wrote: On Wednesday, December 13, 2017 11:33:35 Steven Schveighoffer via Digitalmars-d wrote: I don't think there's a requirement for empty not to do any work, it just has to return the same value each time. IIRC, when this was discussed previously, it was decided that you really couldn't do work in empty. The problem is that under some circumstances at least, it's perfectly legitimate to skip calls to empty The discussion before was whether empty was required to be called before calling front. It's perfectly acceptable to do work in empty, as long as you return the same value in 2 subsequent calls to empty without changing the range between those calls. The problem is, if you have work done in empty, that doesn't mean you don't have to do the equivalent work in front. Which is probably what Luís is after. The best way I think to have ranges work is to only modify them in popFront/popBack, and the ctor. -Steve
Re: state of ranges
On Wed, Dec 13, 2017 at 12:33:02PM -0700, Jonathan M Davis via Digitalmars-d
wrote:
> On Wednesday, December 13, 2017 11:33:35 Steven Schveighoffer via
> Digitalmars-d wrote:
> > I don't think there's a requirement for empty not to do any work, it
> > just has to return the same value each time.
>
> IIRC, when this was discussed previously, it was decided that you
> really couldn't do work in empty. The problem is that under some
> circumstances at least, it's perfectly legitimate to skip calls to
> empty (e.g. if you already know that there's plenty of elements left
> in the range, because you've called save previously and have iterated
> through at least that many elements in another copy of the range or
> because the range has length). it was decided that you really couldn't
> do work in empty. It might be legitimate if your range was not a
> forward range, but it would only work under cirmustances where it
> would be impossible to know whether there are elements left in the
> range or not without calling empty - which is not the case when
> dealing with forward ranges.
[...]
Basically, it comes down to (1) doing the least amount of work necessary
to get your job done; and (2) programming defensively, i.e., assume the
worst about user code, or, don't assume anything more than what the API
dictates.
(1) From the range user's POV, the range API essentially says that if
.empty is true, then you can call .front and .popFront. Doing the least
amount of work means you don't have to call .empty if you already know
beforehand it would have returned false. Similarly, it's legal to call
.popFront without calling .front (or .empty) in between, if you already
know beforehand .empty won't become true in the meantime.
(2) From the range author's POV, assuming the worst means not assuming
that user code will follow a particular sequence of calls to the range
API, other than what is required by the API itself. That is, if your
.empty would have returned false, then assume that somebody will call
.front or .popFront without calling .empty. Don't assume that someone
will always call .empty first.
(OTOH, the range API does require that .empty be false before .front and
.popFront are called, so you shouldn't need to check .empty yourself in
the implementation of .front and .popFront, i.e., avoid doing more work
than necessary.)
Whether you do work in .empty or .front is not really relevant, as long
as ANY sequence of valid range API calls will always produce the same
result. And by any sequence of valid calls, of course, I include
sequences that don't include .empty if somehow the user code already
knows beforehand when .empty will become true. I.e., the sequence
{ r.popFront; r.popFront; r.popFront; ... ; .front } ought to produce
the correct result, as long as .empty never becomes true in the meantime
(and .empty does not need to be called explicitly).
If you can do work in .empty (or .front) while still fulfilling this
requirement, then great. If not, perhaps you should find a different
implementation strategy.
Everything else is just pudding.
T
--
Guns don't kill people. Bullets do.
Re: state of ranges
On Wednesday, December 13, 2017 11:33:35 Steven Schveighoffer via Digitalmars-d wrote: > I don't think there's a requirement for empty not to do any work, it > just has to return the same value each time. IIRC, when this was discussed previously, it was decided that you really couldn't do work in empty. The problem is that under some circumstances at least, it's perfectly legitimate to skip calls to empty (e.g. if you already know that there's plenty of elements left in the range, because you've called save previously and have iterated through at least that many elements in another copy of the range or because the range has length). it was decided that you really couldn't do work in empty. It might be legitimate if your range was not a forward range, but it would only work under cirmustances where it would be impossible to know whether there are elements left in the range or not without calling empty - which is not the case when dealing with forward ranges. - Jonathan M Davis
Re: state of ranges
On 12/12/17 6:43 PM, Luís Marques wrote: On Tuesday, 12 December 2017 at 23:25:19 UTC, Neia Neutuladh wrote: Have you noticed performance problems or implementation side irregularities? Well, I was referring to things like in front() having to use code such as `if(!inited) ...; return value`, which was discussed here in the forum in the past. The proper place to generate the first element, IMO, is in the constructor. The performance side hasn't been too bad for me personally (so far...), but I started this thread exactly because I wanted to know if I could move some code to the empty() method of the range, as that would be more convenient and performant. So you could say I mostly noticed the "regularity" part. Note that there is no compile-time test to figure out when you perform your operations, so you can cheat if you want. I don't think there's a requirement for empty not to do any work, it just has to return the same value each time. -Steve
Re: state of ranges
On 12/13/2017 10:13 AM, Dukc wrote: front() can assume that something can be found, so it may as well fetch the value without checking and rely on built-in array bounds checking and null behaviour for memory safety. empty() is the one which should check those things manually. No. As Seb has quoted, `front` can't assume that `empty` has been called before. For a well-behaved range, `front` must work the same whether you've called `empty` or not (given that the range isn't actually empty).
Re: state of ranges
On Tuesday, 12 December 2017 at 23:43:19 UTC, Luís Marques wrote: Well, I was referring to things like in front() having to use code such as `if(!inited) ...; return value I think you only have to do that if you have some custom pointer arithmetic and you want to make sure it remains memory safe. However, in the general case you don't need to do that. front() can assume that something can be found, so it may as well fetch the value without checking and rely on built-in array bounds checking and null behaviour for memory safety. empty() is the one which should check those things manually.
Re: state of ranges
On Tuesday, 12 December 2017 at 23:25:19 UTC, Neia Neutuladh wrote: Have you noticed performance problems or implementation side irregularities? Well, I was referring to things like in front() having to use code such as `if(!inited) ...; return value`, which was discussed here in the forum in the past. The performance side hasn't been too bad for me personally (so far...), but I started this thread exactly because I wanted to know if I could move some code to the empty() method of the range, as that would be more convenient and performant. So you could say I mostly noticed the "regularity" part.
Re: state of ranges
On Tuesday, 12 December 2017 at 18:58:11 UTC, Luís Marques wrote: Ok, so the consensus was to make ranges easy to use. Was there any progress on mechanisms to avoid the possible performance penalties, and to make the implementation side more regular? Have you noticed performance problems or implementation side irregularities? It would be handy for us to make benchmarks (if nobody has done it yet?), but my feeling is that it doesn't have a measurable impact on performance in the context of a single iterator compared to opApply. Probably has a greater impact when you're stacking things together, since ranges can use design by introspection to do less work.
Re: state of ranges
On Tuesday, 12 December 2017 at 18:40:51 UTC, Seb wrote: Spec: "r.front can be legally evaluated if and only if evaluating r.empty has, or would have, equaled false." Spec: "r.front evaluated multiple times, without calling r.popFront, or otherwise mutating the range object or the underlying data, yields the same result for every evaluation." Ok, so the consensus was to make ranges easy to use. Was there any progress on mechanisms to avoid the possible performance penalties, and to make the implementation side more regular?
Re: state of ranges
On Tuesday, 12 December 2017 at 18:32:11 UTC, Luís Marques wrote: What's the current state of the range specification? -> https://dlang.org/phobos/std_range_primitives.html#isInputRange For instance, do we have to call empty before calling front? Spec: "r.front can be legally evaluated if and only if evaluating r.empty has, or would have, equaled false." Can front provide different answers each time (e.g. map)? Spec: "r.front evaluated multiple times, without calling r.popFront, or otherwise mutating the range object or the underlying data, yields the same result for every evaluation." Were these kinds of issues resolved or not? Is Phobos respecting some consensual protocol or are there still gotchas? Yes, otherwise please open a bug.
state of ranges
What's the current state of the range specification? For instance, do we have to call empty before calling front? Can front provide different answers each time (e.g. map)? Were these kinds of issues resolved or not? Is Phobos respecting some consensual protocol or are there still gotchas?
