View mode: basic / threaded / horizontal-split · Log in · Help
October 17, 2012
isInfinite isInadequate
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.

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.

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.

Option 3 is not sound, but may be practical. Perhaps these 
edge-case, fake, infinite sequences are not worth worrying about 
-- just let it slide and make other people worry about the 
consequences.

This Phobos pull request is relevant: 
https://github.com/D-Programming-Language/phobos/pull/871

Thoughts?
October 17, 2012
Re: isInfinite isInadequate
On Wednesday, 17 October 2012 at 12:18:32 UTC, 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.
>
> 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.
>
> 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.
>
> Option 3 is not sound, but may be practical. Perhaps these 
> edge-case, fake, infinite sequences are not worth worrying 
> about -- just let it slide and make other people worry about 
> the consequences.
>
> This Phobos pull request is relevant: 
> https://github.com/D-Programming-Language/phobos/pull/871
>
> Thoughts?

> cycle(new int[0]);            // not infinite, but isInfinite
> 2. Make cycle assert when the source range is empty.

Technically, while cycle does not assert, it will fail on the 
first call to front, either because of a divide by 0 (RA: 
index%length), or because of a call to an empty front.

We should add an assert. IMO.

--------
TBH, I do not see either as being a problem:

Technically, cycle([]) *is* isInfinite, but the program will 
assert because of a run-time error due to the user's logic. 
Nobody said that just because a range is infinite, that it can't 
ever fail...

Ranges that go on forever, but are not *isInfinite*. My stance on 
this point is that it is not a *big* problem either. I see it 
more as a runtime "infinite loop", rather than an compile time 
"infinite range". It's like a for loop where the run-time end 
condition will always be true.

That said, if the user *does* know the range will be infinite, I 
wouldn't be against having an "assumeInfinite" template function, 
that can take any range, and transform into an (assumed) compile 
time infinite range.
October 17, 2012
Re: isInfinite isInadequate
On Wednesday, 17 October 2012 at 12:33:54 UTC, monarch_dodra 
wrote:
> Technically, cycle([]) *is* isInfinite, but the program will 
> assert because of a run-time error due to the user's logic. 
> Nobody said that just because a range is infinite, that it 
> can't ever fail...

cycle([]) is not infinite. A infinitely repeated empty range is 
the empty range.
October 17, 2012
Re: isInfinite isInadequate
On Wednesday, 17 October 2012 at 12:45:07 UTC, Peter Alexander 
wrote:
> On Wednesday, 17 October 2012 at 12:33:54 UTC, monarch_dodra 
> wrote:
>> Technically, cycle([]) *is* isInfinite, but the program will 
>> assert because of a run-time error due to the user's logic. 
>> Nobody said that just because a range is infinite, that it 
>> can't ever fail...
>
> cycle([]) is not infinite. A infinitely repeated empty range is 
> the empty range.

I'd argue that cycle should be redefined as "Repeats the 
*content* of the given forward range ad infinitum." From there, 
passing it an empty range would be a logic error, since said 
range didn't have any content.
October 17, 2012
Re: isInfinite isInadequate
On 10/17/12 8:18 AM, Peter Alexander wrote:
> 2. Make cycle assert when the source range is empty.

I think this is sensible.

Andrei
March 12, 2013
Re: isInfinite isInadequate
I want to resurrect that thread. Can someone explains the 
benefices of isInfinite ? I fail to see how it really benefit the 
code.
March 12, 2013
Re: isInfinite isInadequate
On Tuesday, 12 March 2013 at 10:01:38 UTC, deadalnix wrote:
> I want to resurrect that thread. Can someone explains the 
> benefices of isInfinite ? I fail to see how it really benefit 
> the code.

The advantage of "enum empty = false" is that algorithms gain a 
great performance boost by optimizing out any "if (r.empty)". 
This can be exploited for things like take, or anything that 
iterates as a matter of fact. I don't think anybody will argue 
that this is a bad approach.

The trait itself checks if empty can be evaluated at compile time 
(to false). The advantage for the *coder* to know if the range is 
infinite is less obvious.

One of the advantages is that an infinite range can have random 
access (meets RA requirements), even though it has no length 
member (normally, any RA range must have length).

Having "isInfinite" can also have the advantage of protecting 
users from stupid calls. For example, calling "count" on an 
infinite range is forbidden => shifting problems from runtime to 
compile time is a HUGE gain.

One of downsides to having infinite ranges is that their 
existence tends to make dealing with generic RA ranges a bit more 
difficult. A lot of our algorithms have changed requirements 
conditions from:
"if (isRandomAccessRange!R)"
to
"if (isRandomAccessRange!R && hasLength!R)"
or
"if (isRandomAccessRange!R && !isInfinite!R)"
//NOTE: Both are strictly equivalent: An RA range is either 
infinite, or has length, but not neither nor both.

Up until not so long ago, it was not possible to slice infinite 
ranges. It is now possible. Unfortunatly, because RA ranges with 
slicing don't guarantee that r[0 .. $] is legal, things are still 
complicated in template code.

The last point (IMO minor) that is raised in the thread is 
"runtime" infiniteness. EG: a range that may or may not be 
infinite at compile time, but which will be known at runtime. 
IMO, these a rare enough (arguably, inexistent) to not really 
matter. The workarounds are easy:
1) Make the range always infinite, but with a requirement that 
user must intialize it or whatnot.
2) Make a runtime fork that will call code that operates on a 
compile-time known infinite adaptor/subtype.
March 12, 2013
Re: isInfinite isInadequate
12-Mar-2013 14:49, monarch_dodra пишет:

> Up until not so long ago, it was not possible to slice infinite ranges.
> It is now possible. Unfortunatly, because RA ranges with slicing don't
> guarantee that r[0 .. $] is legal, things are still complicated in
> template code.

I thought it goes in opposite direction - slicing of Infinite range 
works only for ..$ slice. The chief new requirement of slicing is 
self-assign ability.
>
> The last point (IMO minor) that is raised in the thread is "runtime"
> infiniteness. EG: a range that may or may not be infinite at compile
> time, but which will be known at runtime. IMO, these a rare enough
> (arguably, inexistent) to not really matter. The workarounds are easy:
> 1) Make the range always infinite, but with a requirement that user must
> intialize it or whatnot.
> 2) Make a runtime fork that will call code that operates on a
> compile-time known infinite adaptor/subtype.


-- 
Dmitry Olshansky
March 12, 2013
Re: isInfinite isInadequate
On Tuesday, 12 March 2013 at 11:24:00 UTC, Dmitry Olshansky wrote:
> 12-Mar-2013 14:49, monarch_dodra пишет:
>
>> Up until not so long ago, it was not possible to slice 
>> infinite ranges.
>> It is now possible. Unfortunatly, because RA ranges with 
>> slicing don't
>> guarantee that r[0 .. $] is legal, things are still 
>> complicated in
>> template code.
>
> I thought it goes in opposite direction - slicing of Infinite 
> range works only for ..$ slice. The chief new requirement of 
> slicing is self-assign ability.

I believe the official stance on this is that self-assign is only 
required for non-infinite ranges.
March 12, 2013
Re: isInfinite isInadequate
On Tuesday, 12 March 2013 at 11:24:00 UTC, Dmitry Olshansky wrote:
> 12-Mar-2013 14:49, monarch_dodra пишет:
>
>> Up until not so long ago, it was not possible to slice 
>> infinite ranges.
>> It is now possible. Unfortunatly, because RA ranges with 
>> slicing don't
>> guarantee that r[0 .. $] is legal, things are still 
>> complicated in
>> template code.
>
> I thought it goes in opposite direction - slicing of Infinite 
> range works only for ..$ slice. The chief new requirement of 
> slicing is self-assign ability.

Its... complicated.

To be exact: hasSlicing only requires that:
//--------
        static if(isInfinite!R)
            typeof(take(r, 1)) s = r[1 .. 2];
        else
        {
            static assert(is(typeof(r[1 .. 2]) == R));
            R s = r[1 .. 2];
        }
        //minor tests here
//--------

Which means that if you are going to slice an RA, make sure it is 
finite before back-assigning.

From there, *if* r[0 .. $] is legal, *then* extra checks are made:
//--------
        static if(is(typeof(r[0 .. $])))
        {
            static assert(is(typeof(r[0 .. $]) == R));
            //minor tests here
        }
//--------

*Ideally*, for finite RA ranges, we would want to enforce that [0 
.. $] MUST be legal. This would be breaking change however. We'd 
want the compiler to auto generate opDollar, which would make 
things simpler for everyone:
http://d.puremagic.com/issues/show_bug.cgi?id=7177
The only reason this isn't done yet (AFAIK) is because:
* Support for opDollar is still relativelly new.
* exact details are not fully thought out yet.

As for infinite ranges, ditto. Basically, once you've implemented 
"slice to end", normal slicing is also trivial.

However, today, this is not the case, since it's breaking change.

If you want to call "r[0 .. $]", you have to jump through hoops 
to know if it is legal code.

...

Come to think about it, with today's "deprecated features are on 
by default", I think it would be possible to activate this new 
requirement without breaking any code. Those that activate -w 
would then notice their range needs change to meet the new 
hasSlicing requirements. traits + deprecation is funny business.

@jmdavis: What do you think?
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home