www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - isInfinite isInadequate

reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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?
Oct 17 2012
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Oct 17 2012
next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
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.
Oct 17 2012
parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Oct 17 2012
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
I want to resurrect that thread. Can someone explains the 
benefices of isInfinite ? I fail to see how it really benefit the 
code.
Mar 12 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Mar 12 2013
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Mar 12 2013
next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
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.
Mar 12 2013
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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?
Mar 12 2013
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 12 Mar 2013 06:49:56 -0400, monarch_dodra <monarchdodra gmail.com>  
wrote:


 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.


Wouldn't it automatically be optimized out?  I mean if r.empty is an enum,  
it's like saying if(false)  I would think even with optimizations off,  
this might be done.

Not that I'm questioning the value of isInfinite (I'm neutral on it), but  
this is not a benefit.

-Steve
Mar 12 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 12 March 2013 at 14:30:00 UTC, Steven Schveighoffer 
wrote:

 On Tue, 12 Mar 2013 06:49:56 -0400, monarch_dodra 
 <monarchdodra gmail.com> wrote:


 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.


 Wouldn't it automatically be optimized out?  I mean if r.empty 
 is an enum, it's like saying if(false)  I would think even with 
 optimizations off, this might be done.

 Not that I'm questioning the value of isInfinite (I'm neutral 
 on it), but this is not a benefit.

 -Steve


Right, that's what I said. This first paragraph was just about 
enum empty = false.

The actual "isInfinite" discussion comes later.

Another point: isInfinite is useful, if only to propagate 
infiniteness. For example: "1.repeat().map"a * 2"()". If "map" 
didn't know that repeat is infinite, it would simply provide the 
"dumb" empty implementation, and the final range will have lost 
it's infinite trait.
Mar 12 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 12 Mar 2013 11:02:43 -0400, monarch_dodra <monarchdodra gmail.com>  
wrote:


 On Tuesday, 12 March 2013 at 14:30:00 UTC, Steven Schveighoffer wrote:

 On Tue, 12 Mar 2013 06:49:56 -0400, monarch_dodra  
 <monarchdodra gmail.com> wrote:


 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.


 Wouldn't it automatically be optimized out?  I mean if r.empty is an  
 enum, it's like saying if(false)  I would think even with optimizations  
 off, this might be done.

 Not that I'm questioning the value of isInfinite (I'm neutral on it),  
 but this is not a benefit.

 -Steve


 Right, that's what I said. This first paragraph was just about enum  
 empty = false.


Oh, ok.  When you said "optmizing out" I thought you meant using  
isInfinite to optionally remove calls to empty by hand.


 Another point: isInfinite is useful, if only to propagate infiniteness.  
 For example: "1.repeat().map"a * 2"()". If "map" didn't know that repeat  
 is infinite, it would simply provide the "dumb" empty implementation,  
 and the final range will have lost it's infinite trait.


With inlining, this should propagate properly:

struct WrapperRange(R)
{
    R src;
     property auto front() { return src.front;}
     property bool empty() { return src.empty;} // should be optimized to  
'false' with inlining
    void popFront() { src.popFront();}
}

If R's empty is an enum, then WrapperRange's empty should inline to the  
enum also.

-Steve
Mar 12 2013
prev sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 12 March 2013 at 15:02:44 UTC, monarch_dodra wrote:

 Right, that's what I said. This first paragraph was just about 
 enum empty = false.

 The actual "isInfinite" discussion comes later.

 Another point: isInfinite is useful, if only to propagate 
 infiniteness. For example: "1.repeat().map"a * 2"()". If "map" 
 didn't know that repeat is infinite, it would simply provide 
 the "dumb" empty implementation, and the final range will have 
 lost it's infinite trait.


That will always be optimized away without trouble by existing 
compilers. You'd loose the character of infinitness, but it seems 
to me like a lot of trouble as it add a whole class of things to 
consider when implementing wrapper ranges, for benefice that you 
can already get most of the time.

Note that something like computeIfCTFEable!(r.empty, true) would 
be much more beneficial than the actual implementation.
Mar 12 2013
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:

 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.


I think the point is moot for the same reason it is for 
SentinelRange. A function that return false will be inlined and 
the whole if optimized away anyway. Same goes for a constant.

I'm not talking about a supposed sufficiently smart compiler, but 
actual compiler that exist right now.


 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.


Clearly this is a good point. I however think that a static 
assert within count is much better because it allow to give nicer 
feedback. The problem with InfiniteRange is that it does gives 
you cryptic error message like the count function do not exists.


 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.


I conclude that the fix introduced complexity without solving the 
problem, just pushing the limit. I think we should avoid this 
kind of stuff.


 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.


A common case is unknown "infinitivenes".
Mar 12 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix gmail.com> wrote:


 On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:



 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.


 Clearly this is a good point. I however think that a static assert  
 within count is much better because it allow to give nicer feedback. The  
 problem with InfiniteRange is that it does gives you cryptic error  
 message like the count function do not exists.


Hm... is there a way to test for inifinitness without requiring to be an  
enum?

Wouldn't this also be valid?

if(!R.init.empty)

Essentially, you can evaluate R.init.empty at compile time AND it's false  
on an uninitialized range.  How can a correctly written non-infinite range  
pass that?

That would make forwarding much easier, as the 'dumb' implementation still  
would result in an infinite range.

-Steve
Mar 12 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/12/13 11:47 AM, Steven Schveighoffer wrote:

 On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix gmail.com> wrote:


 On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:



 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.


 Clearly this is a good point. I however think that a static assert
 within count is much better because it allow to give nicer feedback.
 The problem with InfiniteRange is that it does gives you cryptic error
 message like the count function do not exists.


 Hm... is there a way to test for inifinitness without requiring to be an
 enum?

 Wouldn't this also be valid?

 if(!R.init.empty)

 Essentially, you can evaluate R.init.empty at compile time AND it's
 false on an uninitialized range. How can a correctly written
 non-infinite range pass that?

 That would make forwarding much easier, as the 'dumb' implementation
 still would result in an infinite range.


Crossed my mind a few times that fresh non-infinite ranges should be 
empty. But there's no explicit requirement stating that, and I think 
e.g. one may define a k-elements buffer backed by in-situ storage.

Andrei
Mar 12 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 12 Mar 2013 12:16:10 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 3/12/13 11:47 AM, Steven Schveighoffer wrote:

 On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix gmail.com>  
 wrote:


 On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:



 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.


 Clearly this is a good point. I however think that a static assert
 within count is much better because it allow to give nicer feedback.
 The problem with InfiniteRange is that it does gives you cryptic error
 message like the count function do not exists.


 Hm... is there a way to test for inifinitness without requiring to be an
 enum?

 Wouldn't this also be valid?

 if(!R.init.empty)

 Essentially, you can evaluate R.init.empty at compile time AND it's
 false on an uninitialized range. How can a correctly written
 non-infinite range pass that?

 That would make forwarding much easier, as the 'dumb' implementation
 still would result in an infinite range.


 Crossed my mind a few times that fresh non-infinite ranges should be  
 empty. But there's no explicit requirement stating that, and I think  
 e.g. one may define a k-elements buffer backed by in-situ storage.


So something like this:

struct R
{
   int[4] elems;
   int idx;
   int front() { return elems[idx];}
   void popFront() {++idx;}
   bool empty() {idx < elems.length;}
}

which would make this an infinite range by my measurement.  Crap.

How can we make wrapping ranges easier?  I get the point that it's a pain  
in the ass in order to implement a wrapper for another range for things  
like isInfinite, and save.  We need something in std.range that allows you  
to wrap such functions, like a nice mixin.

-Steve
Mar 12 2013
prev sibling next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 12 March 2013 at 16:16:07 UTC, Andrei Alexandrescu 
wrote:

 On 3/12/13 11:47 AM, Steven Schveighoffer wrote:

 On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix 
 <deadalnix gmail.com> wrote:


 On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra 
 wrote:



 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.


 Clearly this is a good point. I however think that a static 
 assert
 within count is much better because it allow to give nicer 
 feedback.
 The problem with InfiniteRange is that it does gives you 
 cryptic error
 message like the count function do not exists.


 Hm... is there a way to test for inifinitness without 
 requiring to be an
 enum?

 Wouldn't this also be valid?

 if(!R.init.empty)

 Essentially, you can evaluate R.init.empty at compile time AND 
 it's
 false on an uninitialized range. How can a correctly written
 non-infinite range pass that?

 That would make forwarding much easier, as the 'dumb' 
 implementation
 still would result in an infinite range.


 Crossed my mind a few times that fresh non-infinite ranges 
 should be empty.


s/should/could/

In any case, that's a very dangerous logic to follow. 
Not-initialized means not initialized. At that point, the concept 
of empty or not empty is irrelevant, it's a wrong call.

By the same token, I don't think anybody would expect a call to 
empty on a null class reference to actually succeed.


 But there's no explicit requirement stating that, and I think 
 e.g. one may define a k-elements buffer backed by in-situ 
 storage.

 Andrei


Not sure what you mean?
Mar 12 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 12 Mar 2013 12:32:22 -0400, monarch_dodra <monarchdodra gmail.com>  
wrote:


 On Tuesday, 12 March 2013 at 16:16:07 UTC, Andrei Alexandrescu wrote:

 On 3/12/13 11:47 AM, Steven Schveighoffer wrote:

 On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix gmail.com>  
 wrote:


 On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:



 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.


 Clearly this is a good point. I however think that a static assert
 within count is much better because it allow to give nicer feedback.
 The problem with InfiniteRange is that it does gives you cryptic error
 message like the count function do not exists.


 Hm... is there a way to test for inifinitness without requiring to be  
 an
 enum?

 Wouldn't this also be valid?

 if(!R.init.empty)

 Essentially, you can evaluate R.init.empty at compile time AND it's
 false on an uninitialized range. How can a correctly written
 non-infinite range pass that?

 That would make forwarding much easier, as the 'dumb' implementation
 still would result in an infinite range.


 Crossed my mind a few times that fresh non-infinite ranges should be  
 empty.


 s/should/could/

 In any case, that's a very dangerous logic to follow. Not-initialized  
 means not initialized. At that point, the concept of empty or not empty  
 is irrelevant, it's a wrong call.


No, ranges can be initialized without a constructor.  Structs are.   
Classes aren't.  But a class with empty as an enum would work.

The idea is that the ultimate underlying source of empty is an enum.   
Since it's an enum, it should be calculable at compile-time, and it should  
always be false, regardless of the state of the range (invalid or valid).

The problem is whether NON-infinite ranges are empty or not.  Looks like  
there are cases where they could be non-empty.


 By the same token, I don't think anybody would expect a call to empty on  
 a null class reference to actually succeed.


If it's an enum, I would.  If it doesn't work, the constraint is false,  
which is what we want.

-Steve
Mar 12 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 12 March 2013 at 16:41:32 UTC, Steven Schveighoffer 
wrote:

 On Tue, 12 Mar 2013 12:32:22 -0400, monarch_dodra 
 <monarchdodra gmail.com> wrote:

 On Tuesday, 12 March 2013 at 16:16:07 UTC, Andrei Alexandrescu

 Crossed my mind a few times that fresh non-infinite ranges 
 should be empty.


 s/should/could/

 In any case, that's a very dangerous logic to follow. 
 Not-initialized means not initialized. At that point, the 
 concept of empty or not empty is irrelevant, it's a wrong call.


 No, ranges can be initialized without a constructor.  Structs 
 are.  Classes aren't.  But a class with empty as an enum would 
 work.


Depends on your definition of "initialized" I guess. Sure, you 
can create a struct instance without a constructor. Try using a 
RefCounted!(AutoInit.No) and see what happens.


 The idea is that the ultimate underlying source of empty is an 
 enum.  Since it's an enum, it should be calculable at 
 compile-time, and it should always be false, regardless of the 
 state of the range (invalid or valid).


Yes. *empty* will always answer false. My point though is that 
it's not just because range.empty says false that the range is 
ready for use.


 The problem is whether NON-infinite ranges are empty or not.  
 Looks like there are cases where they could be non-empty.

 -Steve


I think that each range should be responsible for its own 
initialization semantics.
Mar 12 2013
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/12/2013 05:16 PM, Andrei Alexandrescu wrote:

 On 3/12/13 11:47 AM, Steven Schveighoffer wrote:

 ...
 Wouldn't this also be valid?

 if(!R.init.empty)

 Essentially, you can evaluate R.init.empty at compile time AND it's
 false on an uninitialized range. How can a correctly written
 non-infinite range pass that?

 That would make forwarding much easier, as the 'dumb' implementation
 still would result in an infinite range.


 Crossed my mind a few times that fresh non-infinite ranges should be
 empty. But there's no explicit requirement stating that, and I think
 e.g. one may define a k-elements buffer backed by in-situ storage.

 Andrei


std.algorithm.joiner assumes that default-initialized separator ranges 
are empty.

import std.algorithm, std.array, std.range;

struct NonEmptyRange{
	int[] a = [0,8];
	 property int front(){ return a.front; }
	 property bool empty(){ return a.empty; }
	void popFront(){ a.popFront(); }
	 property NonEmptyRange save(){ return NonEmptyRange(a.save); }
}

void main(){
 
assert(equal([[1,2,3],[1,2,3]].joiner(NonEmptyRange()),[1,2,3,0,8,1,2,3])); 
// fail
}

I'd report it, but the bug tracker is down.
Mar 13 2013
prev sibling parent reply Brad Roberts <braddr slice-2.puremagic.com> writes:
On Tue, 12 Mar 2013, monarch_dodra wrote:


 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).


Where did this assertion come from?  There's nothing about infinite that 
implies random access in the general case.  Consider a circular linked 
list.  It's infinite but not random access.

There's a class of infinite functions which are random access, but 
definitely not all.
Mar 12 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 12 March 2013 at 18:08:25 UTC, Brad Roberts wrote:

 On Tue, 12 Mar 2013, monarch_dodra wrote:


 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).


 Where did this assertion come from?  There's nothing about 
 infinite that
 implies random access in the general case.  Consider a circular 
 linked
 list.  It's infinite but not random access.

 There's a class of infinite functions which are random access, 
 but
 definitely not all.


Yeah... ergo "can".
Mar 12 2013
parent Brad Roberts <braddr slice-2.puremagic.com> writes:
On Tue, 12 Mar 2013, monarch_dodra wrote:


 On Tuesday, 12 March 2013 at 18:08:25 UTC, Brad Roberts wrote:

 On Tue, 12 Mar 2013, monarch_dodra wrote:
 

 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).


 
 Where did this assertion come from?  There's nothing about infinite that
 implies random access in the general case.  Consider a circular linked
 list.  It's infinite but not random access.
 
 There's a class of infinite functions which are random access, but
 definitely not all.


 
 Yeah... ergo "can".


Ok.  The use of 'can' there is generally a much stronger implication than 
that read of it.  I read it as an implies rather than allows for the 
possibility, and I'll bet I'm not alone.
Mar 12 2013
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 17 2012
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Mar 12 2013