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 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
prev sibling next sibling 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
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 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 "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
prev sibling next sibling 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 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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 next 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 "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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 next 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 "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
prev sibling 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 "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent "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
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