isInfinite isInadequate

[Walter Bright]

On 10/17/2012 5:18 AM, Peter Alexander wrote:
> So, std.range.isInfinite checks if r.empty is a compile time boolean equal to
> false. This works most of the time, but not always. Some ranges are infinite,
> but cannot be determined to be so at compile time (or even run time!)
>
> cycle([1, 2, 3]).until(4);    // infinite, but not isInfinite
> cycle(new int[0]);            // not infinite, but isInfinite
> collatzSequence(n).until(1);  // infiniteness an open problem!
>
> In short, isInfinite does not -- and cannot -- work as a way of telling if a
> range is finite or infinite in general.

isInfinite tells you if it is statically determinable to be infinite, not if it 
might be at run time.


> On resolution is to take isInfinite at face value: it only tells you if a range
> is statically determined to be infinite. If isInfinite is false, it could still
> be infinite.

Right. isInfinite doesn't pretend to solve the halting problem.

> This leaves us with the tricky cases like cycle(new int[0]). There's three
> resolutions to this (as far as I can tell):
>
> 1. Change cycle to not be an infinite range.
> 2. Make cycle assert when the source range is empty.
> 3. Ignore this issue.
>
> Option 1 is sound, but kind of sucks, because generally cycle is infinite.
>
> Option 2 is sound, but I don't like the idea of asserting on logically valid
> input just because the problem is too hard.

It isn't just hard, it is impossible. Re the halting problem.