Okay. If I understand correctly, as it stands, a range type is either infinite or its not, and it's known at compile-time whether it's infinite or not. This appears to be done by checking for a static property empty of type bool which is known at compile-time. The question is do we _need_ to know at compile-time whether a range is infinite? Or it would it be possible to make it so that that can be determined at runtime?

My guess is that the algorithms that care need to know at compile-time, but if that's the case, it poses a definite problem for me.

I have been working on a date/time module for potential inclusion in Phobos. Part of that includes a time interval which represents a period of time starting at one point of time and extending to another point of time which is not included in the interval. So, for example [2010-07-04 - 2010-08-03). I'm working on creating ranges to iterate over a time interval. The problem is that an interval can be infinite, but you don't know at compile time whether it's infinite. You could have an interval such as [2010-07-04 - positive infinity), and a range over that interval would be infinite. However, whether a given interval (and thus its range) is infinite depends on the runtime arguments that created the interval. So, I have no way of creating an infinite range for which isInfinite(Range) will return true.

Would it be reasonable to make it possible to have infinite ranges which were determined to be infinite at runtime rather than compile-time? Or is there a better solution? Or is it simply tough luck, and the range may be effectively infinite but can't be treated that way by algorithms using isInfinite(Range)?

- Jonathan M Davis

On Sunday 05 September 2010 17:58:16 Jonathan M Davis wrote:
> Okay. If I understand correctly, as it stands, a range type is either infinite or its not, and it's known at compile-time whether it's infinite or not. This appears to be done by checking for a static property empty of type bool which is known at compile-time. The question is do we _need_ to know at compile-time whether a range is infinite? Or it would it be possible to make it so that that can be determined at runtime?
> 
> My guess is that the algorithms that care need to know at compile-time, but if that's the case, it poses a definite problem for me.
> 
> I have been working on a date/time module for potential inclusion in Phobos. Part of that includes a time interval which represents a period of time starting at one point of time and extending to another point of time which is not included in the interval. So, for example [2010-07-04 - 2010-08-03). I'm working on creating ranges to iterate over a time interval. The problem is that an interval can be infinite, but you don't know at compile time whether it's infinite. You could have an interval such as [2010-07-04 - positive infinity), and a range over that interval would be infinite. However, whether a given interval (and thus its range) is infinite depends on the runtime arguments that created the interval. So, I have no way of creating an infinite range for which isInfinite(Range) will return true.
> 
> Would it be reasonable to make it possible to have infinite ranges which were determined to be infinite at runtime rather than compile-time? Or is there a better solution? Or is it simply tough luck, and the range may be effectively infinite but can't be treated that way by algorithms using isInfinite(Range)?
> 
> - Jonathan M Davis

It seems to me that a particularly large problem will be walkLength(). Thanks to its upTo parameter, it won't result in an infinite loop, and odds are that the values that the range is producing will overflow, wrap around, and end up throwing an exception before upTo is hit, but still, you're going to end up with it looping until it blows up when if there were some standard way to indicate at runtime that the range was infinite, then walkLength() could throw up front. I can see why ideally it would be known at compile-time whether a range were infinite or not (e.g. presumably walkLength's template constraints won't allow it to be called with a range type for which isInfinite(Range) is true), but it's pretty easy to have infinite ranges which can't be known at compile-time. At the moment, I'm just putting an isInfinite() on the range itself, and the programmer can worry about it, but I expect that it wouldn't be that hard for them to try and use an algorithm in std.algorithm which called walkLength() without them knowing it.

- Jonathan M Davis

On Monday 06 September 2010 16:06:23 Jonathan M Davis wrote:
> On Sunday 05 September 2010 17:58:16 Jonathan M Davis wrote:
> > Okay. If I understand correctly, as it stands, a range type is either infinite or its not, and it's known at compile-time whether it's infinite or not. This appears to be done by checking for a static property empty of type bool which is known at compile-time. The question is do we _need_ to know at compile-time whether a range is infinite? Or it would it be possible to make it so that that can be determined at runtime?
> > 
> > My guess is that the algorithms that care need to know at compile-time, but if that's the case, it poses a definite problem for me.
> > 
> > I have been working on a date/time module for potential inclusion in Phobos. Part of that includes a time interval which represents a period of time starting at one point of time and extending to another point of time which is not included in the interval. So, for example [2010-07-04 - 2010-08-03). I'm working on creating ranges to iterate over a time interval. The problem is that an interval can be infinite, but you don't know at compile time whether it's infinite. You could have an interval such as [2010-07-04 - positive infinity), and a range over that interval would be infinite. However, whether a given interval (and thus its range) is infinite depends on the runtime arguments that created the interval. So, I have no way of creating an infinite range for which isInfinite(Range) will return true.
> > 
> > Would it be reasonable to make it possible to have infinite ranges which were determined to be infinite at runtime rather than compile-time? Or is there a better solution? Or is it simply tough luck, and the range may be effectively infinite but can't be treated that way by algorithms using isInfinite(Range)?
> > 
> > - Jonathan M Davis
> 
> It seems to me that a particularly large problem will be walkLength(). Thanks to its upTo parameter, it won't result in an infinite loop, and odds are that the values that the range is producing will overflow, wrap around, and end up throwing an exception before upTo is hit, but still, you're going to end up with it looping until it blows up when if there were some standard way to indicate at runtime that the range was infinite, then walkLength() could throw up front. I can see why ideally it would be known at compile-time whether a range were infinite or not (e.g. presumably walkLength's template constraints won't allow it to be called with a range type for which isInfinite(Range) is true), but it's pretty easy to have infinite ranges which can't be known at compile-time. At the moment, I'm just putting an isInfinite() on the range itself, and the programmer can worry about it, but I expect that it wouldn't be that hard for them to try and use an algorithm in std.algorithm which called walkLength() without them knowing it.
> 
> - Jonathan M Davis

Okay. Maybe the issues with isInfinite(Range) just show that dealing with infinity in the same manner as Boost is a bad idea. They have it set up so that a time point can be positively infinite, negatively infinite, invalid, or normal. A time interval can then be infinite by having one of its end points be an infinity. You can then have an infinite range (though they're using iterators rather than ranges). I have been following essentially that design. However, having infinite and invalid time points complicates things a fair bit, and the only real value that I see is allowing for infinite intervals and ranges. So, perhaps it would be better to get rid of the idea of infinite and invalid time points in favor of having separate interval types (and thus separate range types) for finite and infinite intervals. The ability to have infinite ranges would still be there but with a lot less cruft, and you could then use isInfnite(Range).

So, perhaps I'll go and refactor my code so that infinity is strictly kept to intervals and ranges and not time points or time durations. It would certainly reduce the number of runtime checks and reduce the amount of code. Of course, making those changes will make it take that much longer to complete the date/time module, but better later than poorly designed.

- Jonathan M Davis

On 09/06/2010 06:42 PM, Jonathan M Davis wrote:
[snip]
> So, perhaps I'll go and refactor my code so that infinity is strictly kept to intervals and ranges and not time points or time durations. It would certainly reduce the number of runtime checks and reduce the amount of code. Of course, making those changes will make it take that much longer to complete the date/time module, but better later than poorly designed.

Infinity must be known during compilation. Otherwise RandomAccessRange must be a refinement of BidirectionalAccessRange, and bidirectional access is obviously not supported by infinite range. That closes the door to infinite random access ranges, of which there are many.

Andrei