www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Get rid of isInfinite()?

reply "Mehrdad" <wfunction hotmail.com> writes:
I feel like isInfinite is useless for typical cases... the only 
"infinite" (perhaps I should call it "unbounded" instead?) range 
I've ever realistically come across is a stream, like console 
input or a network stream.

Of course, isInfinite doesn't make any sense for any type of 
wrapper around console input -- is it true or false?
You can't tell, because it depends on whether the input is 
redirected.
If the console input was redirected, then it would be finite, 
with a certain length (the length of the file).
If not, then it would be infinite (er, unbounded).

So IMHO, we should deprecate isInfinite entirely, and instead 
rely on length being size_t.max.

Not only would it make more sense, but it would make it possible 
to create a random-access wrapper around an input range (like 
console input), which lazily fetches its data.
Then you can work with console input like a regular string!
Jun 25 2012
next sibling parent reply "Mehrdad" <wfunction hotmail.com> writes:
On Monday, 25 June 2012 at 17:26:23 UTC, Mehrdad wrote:

 I feel like isInfinite is useless for typical cases... the only 
 "infinite" (perhaps I should call it "unbounded" instead?) 
 range I've ever realistically come across is a stream, like 
 console input or a network stream.

 Of course, isInfinite doesn't make any sense for any type of 
 wrapper around console input -- is it true or false?
 You can't tell, because it depends on whether the input is 
 redirected.
 If the console input was redirected, then it would be finite, 
 with a certain length (the length of the file).
 If not, then it would be infinite (er, unbounded).

 So IMHO, we should deprecate isInfinite entirely, and instead 
 rely on length being size_t.max.

 Not only would it make more sense, but it would make it 
 possible to create a random-access wrapper around an input 
 range (like console input), which lazily fetches its data.
 Then you can work with console input like a regular string!


This also prompts another issue:
The length of a range should be a long, not size_t.

Otherwise there's no way we could possibly replace streams with 
ranges. 32-bit systems have LOTS of common streams that are over 
2^32 bytes (e.g. DVD images, partition images, large movies, 
etc.).
Jun 25 2012
parent "Mehrdad" <wfunction hotmail.com> writes:
On Monday, 25 June 2012 at 17:28:27 UTC, Mehrdad wrote:

 On Monday, 25 June 2012 at 17:26:23 UTC, Mehrdad wrote:

 I feel like isInfinite is useless for typical cases... the 
 only "infinite" (perhaps I should call it "unbounded" 
 instead?) range I've ever realistically come across is a 
 stream, like console input or a network stream.

 Of course, isInfinite doesn't make any sense for any type of 
 wrapper around console input -- is it true or false?
 You can't tell, because it depends on whether the input is 
 redirected.
 If the console input was redirected, then it would be finite, 
 with a certain length (the length of the file).
 If not, then it would be infinite (er, unbounded).

 So IMHO, we should deprecate isInfinite entirely, and instead 
 rely on length being size_t.max.

 Not only would it make more sense, but it would make it 
 possible to create a random-access wrapper around an input 
 range (like console input), which lazily fetches its data.
 Then you can work with console input like a regular string!


 This also prompts another issue:
 The length of a range should be a long, not size_t.

 Otherwise there's no way we could possibly replace streams with 
 ranges. 32-bit systems have LOTS of common streams that are 
 over 2^32 bytes (e.g. DVD images, partition images, large 
 movies, etc.).


Moved the other part to a separate thread:
http://forum.dlang.org/thread/wgulnffhhkorfvtzbnqb forum.dlang.org#post-wgulnffhhkorfvtzbnqb:40forum.dlang.org
Jun 25 2012
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 25 Jun 2012 13:26:22 -0400, Mehrdad <wfunction hotmail.com> wrote:


 I feel like isInfinite is useless for typical cases... the only  
 "infinite" (perhaps I should call it "unbounded" instead?) range I've  
 ever realistically come across is a stream, like console input or a  
 network stream.

 Of course, isInfinite doesn't make any sense for any type of wrapper  
 around console input -- is it true or false?
 You can't tell, because it depends on whether the input is redirected.
 If the console input was redirected, then it would be finite, with a  
 certain length (the length of the file).
 If not, then it would be infinite (er, unbounded).

 So IMHO, we should deprecate isInfinite entirely, and instead rely on  
 length being size_t.max.

 Not only would it make more sense, but it would make it possible to  
 create a random-access wrapper around an input range (like console  
 input), which lazily fetches its data.
 Then you can work with console input like a regular string!


I think you misunderstand an infinite range.  There are plenty of truly  
infinite ranges available.

An example infinite range:

struct Infinite
{
    int x;
     property int front() { return x;}
    void popFront() {}
    enum empty = false;
}

length has nothing to do with infinite ranges.  In fact, infinite ranges  
should have no length member.

-Steve
Jun 25 2012
parent reply "Mehrdad" <wfunction hotmail.com> writes:
On Monday, 25 June 2012 at 17:38:55 UTC, Steven Schveighoffer 
wrote:

 I think you misunderstand an infinite range.  There are plenty 
 of truly infinite ranges available.

 An example infinite range:

 struct Infinite
 {
    int x;
     property int front() { return x;}
    void popFront() {}
    enum empty = false;
 }

 length has nothing to do with infinite ranges.  In fact, 
 infinite ranges should have no length member.

 -Steve


Oh, I see. So they're truly infinite, not just unbounded.

In that case, how do you make a random-access wrapper around an 
input range?
(i.e. What do you use for 'length'?)
Jun 25 2012
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, June 25, 2012 19:43:00 Mehrdad wrote:

 On Monday, 25 June 2012 at 17:38:55 UTC, Steven Schveighoffer
 
 wrote:

 I think you misunderstand an infinite range. There are plenty
 of truly infinite ranges available.
 
 An example infinite range:
 
 struct Infinite
 {
 
 int x;
  property int front() { return x;}
 void popFront() {}
 enum empty = false;
 
 }
 
 length has nothing to do with infinite ranges. In fact,
 infinite ranges should have no length member.
 
 -Steve


 
 Oh, I see. So they're truly infinite, not just unbounded.
 
 In that case, how do you make a random-access wrapper around an
 input range?
 (i.e. What do you use for 'length'?)


Input ranges cannot be random access. Iterating over them consumes them, and 
you have no way of knowing their length other then iterating over them and 
counting (which would consume them), so they have no length property. If you 
want an input range to be treated as a forward range or random access range, 
you're going to need to copy it into something first.

- Jonathan M Davis
Jun 25 2012
prev sibling parent reply "Bernard Helyer" <b.helyer gmail.com> writes:
On Monday, 25 June 2012 at 17:43:01 UTC, Mehrdad wrote:

 In that case, how do you make a random-access wrapper around an 
 input range?


You don't. If you could, they wouldn't be an input range.
Jun 25 2012
parent reply "Mehrdad" <wfunction hotmail.com> writes:
On Monday, 25 June 2012 at 18:29:45 UTC, Bernard Helyer wrote:

 On Monday, 25 June 2012 at 17:43:01 UTC, Mehrdad wrote:

 In that case, how do you make a random-access wrapper around 
 an input range?


 You don't. If you could, they wouldn't be an input range.



Wait, what?

I don't see why you _shouldn't_ be able to create a random-access 
wrapper that lazily reads as much data as it needs to, in order 
to satisfy a random read.

i.e. I see no obstacle, at least conceptually, other than the 
fact you're saying you can't do it.
Jun 25 2012
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, June 26, 2012 00:46:40 Mehrdad wrote:

 On Monday, 25 June 2012 at 18:29:45 UTC, Bernard Helyer wrote:

 On Monday, 25 June 2012 at 17:43:01 UTC, Mehrdad wrote:

 In that case, how do you make a random-access wrapper around
 an input range?


 
 You don't. If you could, they wouldn't be an input range.


 
 Wait, what?
 
 I don't see why you _shouldn't_ be able to create a random-access
 wrapper that lazily reads as much data as it needs to, in order
 to satisfy a random read.
 
 i.e. I see no obstacle, at least conceptually, other than the
 fact you're saying you can't do it.


You can't do it as a proper random-access range. To do that, it would have to 
be a forward range, and if it's not a forward range already, then presumably, 
there's a reason why it can't be. You could easily tell it to give you the nth 
element, but that would require consuming all of the preceding elements to get 
to it. You could store those elements internally as you iterate over them, but 
normally, they'd be gone, meaning that skipping to the nth element would mean 
losing all of the preceding elements.

Regardless, unless you can find a way to define a save function which will 
return a copy of the range and be able to iterate over both of them separately 
and get exactly the same elements, then you can't have anything more than an 
input range as far as how the various ranges are defined goes. If you can 
somehow figure out how to do that via buffering, then you could make it a 
forward range as well as whatever other range types you could define the 
functions for, but you'd have to figure out a way to define save.

- Jonathan M Davis
Jun 25 2012
parent reply "Mehrdad" <wfunction hotmail.com> writes:
On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:

 You could store those elements internally as you iterate over 
 them




That's *precisely* the point of my wrapper... sorry if that 
wasn't clear.

Why shouldn't that be sufficient for making it random-access?







 If you can somehow figure out how to do that via buffering, 
 then you could make it a forward range as well as whatever 
 other range types you could define the functions for, but you'd 
 have to figure out a way to define save.




OK, now we're at the same place. :P

What I'm saying is, I __CAN__ get the buffering to work.

What I __cannot__ figure out what to do with is 'length'... I 
can't think of anything reasonable to return, since it's not 
infinite (which I might represent as ulong.max, if anything) but 
it's unbounded.


So the _ONLY_ problem I'm running into right now is length() -- 
any ideas how I could fix that?
Jun 25 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, June 26, 2012 05:40:10 Mehrdad wrote:

 On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:

 You could store those elements internally as you iterate over
 them


 
 That's *precisely* the point of my wrapper... sorry if that
 wasn't clear.
 
 Why shouldn't that be sufficient for making it random-access?
 

 If you can somehow figure out how to do that via buffering,
 then you could make it a forward range as well as whatever
 other range types you could define the functions for, but you'd
 have to figure out a way to define save.


 
 OK, now we're at the same place. :P
 
 What I'm saying is, I __CAN__ get the buffering to work.
 
 What I __cannot__ figure out what to do with is 'length'... I
 can't think of anything reasonable to return, since it's not
 infinite (which I might represent as ulong.max, if anything) but
 it's unbounded.
 
 
 So the _ONLY_ problem I'm running into right now is length() --
 any ideas how I could fix that?


If you can't calculate the length in O(1), then you're stuck using walkLength, 
which means iterating over the entire range to get its length. And if that's 
the case, then you can't make it a random access range, because for it to be a 
random access range, it either needs to have a length property (which must be 
O(1)) or be infinite. And I would fully expect for your code to run into a 
variety of bugs if you tried to claim that it was a length that it wasn't 
(e.g. ulong.max), since a number of functions will expect that that's its 
actual length and won't work properly if it's not.

For a range to be random access, it must fulfill these requirements:

template isRandomAccessRange(R)
{
    enum bool isRandomAccessRange = is(typeof(
    (inout int _dummy=0)
    {
        static assert(isBidirectionalRange!R ||
                      isForwardRange!R && isInfinite!R);
        R r = void;
        auto e = r[1];
        static assert(!isNarrowString!R);
        static assert(hasLength!R || isInfinite!R);
    }));
}

and I'm not sure that you can squeeze your range into that. You could do it if 
you just read in the entire range and created another range from it (be it an 
array or whatever), but you appear to be attempting something which probably 
won't quite work with the current range design. I suspect that you'd do better 
trying to claim that it wasn infinite rather than had a length, but then you'd 
have to be able to deal with the fact that empty is always false.

- Jonathan M Davis
Jun 25 2012
parent "Mehrdad" <wfunction hotmail.com> writes:
On Tuesday, 26 June 2012 at 06:05:49 UTC, Jonathan M Davis wrote:

 If you can't calculate the length in O(1), then you're stuck 
 using walkLength,
 which means iterating over the entire range to get its length. 
 And if that's
 the case, then you can't make it a random access range, because 
 for it to be a
 random access range, it either needs to have a length property 
 (which must be
 O(1)) or be infinite. And I would fully expect for your code to 
 run into a
 variety of bugs if you tried to claim that it was a length that 
 it wasn't
 (e.g. ulong.max), since a number of functions will expect that 
 that's its
 actual length and won't work properly if it's not.

 For a range to be random access, it must fulfill these 
 requirements:

 template isRandomAccessRange(R)
 {
     enum bool isRandomAccessRange = is(typeof(
     (inout int _dummy=0)
     {
         static assert(isBidirectionalRange!R ||
                       isForwardRange!R && isInfinite!R);
         R r = void;
         auto e = r[1];
         static assert(!isNarrowString!R);
         static assert(hasLength!R || isInfinite!R);
     }));
 }

 and I'm not sure that you can squeeze your range into that. You 
 could do it if
 you just read in the entire range and created another range 
 from it (be it an
 array or whatever), but you appear to be attempting something 
 which probably
 won't quite work with the current range design. I suspect that 
 you'd do better
 trying to claim that it wasn infinite rather than had a length, 
 but then you'd
 have to be able to deal with the fact that empty is always 
 false.

 - Jonathan M Davis


I actually only needed length() because random access ranges 
required it (not because I did), but maybe I can avoid it some 
way without using random access ranges at all... I'll try to 
rework stuff. Thanks for the explanations.
Jun 25 2012
prev sibling next sibling parent "Roman D. Boiko" <rb d-coding.com> writes:
On Tuesday, 26 June 2012 at 03:40:11 UTC, Mehrdad wrote:

 On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:

 If you can somehow figure out how to do that via buffering, 
 then you could make it a forward range as well as whatever 
 other range types you could define the functions for, but 
 you'd have to figure out a way to define save.


 OK, now we're at the same place. :P

 What I'm saying is, I __CAN__ get the buffering to work.

 What I __cannot__ figure out what to do with is 'length'... I 
 can't think of anything reasonable to return, since it's not 
 infinite (which I might represent as ulong.max, if anything) 
 but it's unbounded.


 So the _ONLY_ problem I'm running into right now is length() -- 
 any ideas how I could fix that?


You should decide what is length **conceptually** in your 
abstraction. In a similar situation I might want to create a 
forward range, and add indexing or slicing if they are needed. Or 
create a forward range of arrays, each representing a buffer. Or 
specify that semantically length is allowed to increase if some 
condition / predicate is true (the user might pass this predicate 
if needed).

There are many options possible, important is what use cases you 
target and what intuitive associations to already existing 
concepts you would like your users to apply.
Jun 25 2012
prev sibling parent reply travert phare.normalesup.org (Christophe Travert) writes:
"Mehrdad" , dans le message (digitalmars.D:170697), a écrit :

 On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:

 You could store those elements internally as you iterate over 
 them


 
 That's *precisely* the point of my wrapper... sorry if that 
 wasn't clear.
 
 Why shouldn't that be sufficient for making it random-access?
 
 

 If you can somehow figure out how to do that via buffering, 
 then you could make it a forward range as well as whatever 
 other range types you could define the functions for, but you'd 
 have to figure out a way to define save.


 
 
 
 OK, now we're at the same place. :P
 
 What I'm saying is, I __CAN__ get the buffering to work.
 
 What I __cannot__ figure out what to do with is 'length'... I 
 can't think of anything reasonable to return, since it's not 
 infinite (which I might represent as ulong.max, if anything) but 
 it's unbounded.
 
 
 So the _ONLY_ problem I'm running into right now is length() -- 
 any ideas how I could fix that?


I you are planning to buffer all input as you read it to enable 
random-access, then you should better read the whole file in your buffer 
from the start and get done with it, since you will end up having read 
the whole file in the buffer at the end...

-- 
Christophe
Jun 26 2012
parent travert phare.normalesup.org (Christophe Travert) writes:
Christophe Travert, dans le message (digitalmars.D:170706), a écrit :

 "Mehrdad" , dans le message (digitalmars.D:170697), a écrit :

 On Monday, 25 June 2012 at 23:03:59 UTC, Jonathan M Davis wrote:

 You could store those elements internally as you iterate over 
 them


 
 That's *precisely* the point of my wrapper... sorry if that 
 wasn't clear.
 
 Why shouldn't that be sufficient for making it random-access?
 
 

 If you can somehow figure out how to do that via buffering, 
 then you could make it a forward range as well as whatever 
 other range types you could define the functions for, but you'd 
 have to figure out a way to define save.


 
 
 
 OK, now we're at the same place. :P
 
 What I'm saying is, I __CAN__ get the buffering to work.
 
 What I __cannot__ figure out what to do with is 'length'... I 
 can't think of anything reasonable to return, since it's not 
 infinite (which I might represent as ulong.max, if anything) but 
 it's unbounded.
 
 
 So the _ONLY_ problem I'm running into right now is length() -- 
 any ideas how I could fix that?


 
 I you are planning to buffer all input as you read it to enable 
 random-access, then you should better read the whole file in your buffer 
 from the start and get done with it, since you will end up having read 
 the whole file in the buffer at the end...
 


Hum, sorry, that is irrelevant if your input is not a file.
Jun 26 2012
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 06/25/2012 07:26 PM, Mehrdad wrote:

 I feel like isInfinite is useless for typical cases... the only
 "infinite" (perhaps I should call it "unbounded" instead?) range I've
 ever realistically come across  is a stream, like console input or a
 network stream.


Console input or network streams can be terminated.


 Of course, isInfinite doesn't make any sense for any type of wrapper
 around console input -- is it true or false?
 You can't tell, because it depends on whether the input is redirected.
 If the console input was redirected, then it would be finite, with a
 certain length (the length of the file).
 If not, then it would be infinite (er, unbounded).


Infinite lazy ranges are an useful abstraction. You could read up on
Haskell. Lists in Haskell programs are often infinite.



 So IMHO, we should deprecate isInfinite entirely, and instead rely on
 length being size_t.max.


Infinite ranges do not have a length.


 Not only would it make more sense, but it would make it possible to
 create a random-access wrapper around an input range (like console
 input), which lazily fetches its data.
 Then you can work with console input like a regular string!


An infinite range can be buffered lazily just fine.
Jun 25 2012