www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: "the last change" for ranges

reply MLT <none anone.com> writes:
Andrei Alexandrescu Wrote:


 In wake of a few discussion I've witnessed, I'm thinking of a last 
 change for ranges. (In fact there's one more, but that's minor.)
 
 The problem is that input ranges and forward ranges have the same 
 syntactic interface, but different semantic interfaces. Consider the 
 problem of finding the first two identical adjacent items in a range:
 
 R adjacentFind(R)(R r)
 {
      if (r.empty) return r;
      R last = r;
      r.popFront;
      for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
      {
      }
      return r;
 }
 
 This will work properly on lists and vectors, but horrendously on files 
 and sockets. This is because input ranges can't be saved for later use: 
 incrementing r also increments popFront and essentially forces both to 
 look at the same current value.
 



I think that if

      R last = r;




      r.popFront;




If I understood the logic of ranges, popFront() just changes the range, and not
the elements it points to.
May 20 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
MLT wrote:

 I think that if

 R last = r;




 r.popFront;



 type of range you are dealing with. (That means that input operations
 would be buffered to the leftmost range that still extsts.)
 
 If I understood the logic of ranges, popFront() just changes the
 range, and not the elements it points to.



That's the case for all ranges except input ranges. Consider:

FileByCharacter
{
     private FILE* _f;
     private dchar _last;
     bool empty() { return _last == 0xffff; }
     void popFront() { _last = fgetc(_f); }
     dchar front() { return _last; }
}

Consider what happens when you copy this range around.


Andrei
May 20 2009
next sibling parent Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:


 MLT wrote:

 I think that if

 R last = r;




 r.popFront;



 type of range you are dealing with. (That means that input operations
 would be buffered to the leftmost range that still extsts.)
 
 If I understood the logic of ranges, popFront() just changes the
 range, and not the elements it points to.



 That's the case for all ranges except input ranges. Consider:
 
 FileByCharacter
 {
      private FILE* _f;
      private dchar _last;
      bool empty() { return _last == 0xffff; }
      void popFront() { _last = fgetc(_f); }
      dchar front() { return _last; }
 }
 
 Consider what happens when you copy this range around.
 
 
 Andrei



You didn't declare FileByCharacter as either a struct or a class? Did I plant a
seed? :)
May 20 2009
prev sibling parent reply MLT <none anon.com> writes:
Andrei Alexandrescu Wrote:


 MLT wrote:

 I think that if

 R last = r;




 r.popFront;



 type of range you are dealing with. (That means that input operations
 would be buffered to the leftmost range that still extsts.)
 
 If I understood the logic of ranges, popFront() just changes the
 range, and not the elements it points to.



 That's the case for all ranges except input ranges. Consider:
 
 FileByCharacter
 {
      private FILE* _f;
      private dchar _last;
      bool empty() { return _last == 0xffff; }
      void popFront() { _last = fgetc(_f); }
      dchar front() { return _last; }
 }
 
 Consider what happens when you copy this range around.
 
 
 Andrei




I thought more of something like:

FileByCharacter
 {
      private FILE* _f;
      private dchar[] _buf;
      bool empty() { return _buf[0] == 0xffff; } 
      void popFront() { 
        _buf = _buf[1..$] ; 
        if( _buf.length < 1 ) _buf ~= fgetc(_f); 
      }
      dchar front() { return _buf[0]; }
 }

The idea is that you continue to expand an array. Another copy of the range
will continue to step over the same array. This doesn't really work, because
the second copy doesn't really know how much the first copy already read. But
that should be fixable....
the problem is in the line
        if( _buf.length < 1 ) _buf ~= fgetc(_f); 
which should only trigger if _buf reached the end of the read part, not the end
of the current copy of _buf.

I'm also not sure if D's GC will handle dropping the part of the array that no
one looks at.

One needs something like a lazy semi-infinite range, that only calls a certain
function when it reaches an unexplored part.
May 20 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
MLT wrote:

 One needs something like a lazy semi-infinite range, that only calls
 a certain function when it reaches an unexplored part.



That's a great abstraction, but we can't afford to impose that to 
everybody. There must be an abstraction for a one-pass go through an 
arbitrarily long stream.

Anyhow, I decided to change ranges as follows:

a) Input:

bool empty();
ref T popNext();

b) Output:

void putNext(T);

c) Forward:

bool empty();
ref T front();
void popFront();

The function ref T popNext() is a nonmember that accepts any forward 
range and uses front() and popFront(). Of course, a forward range is 
welcome to implement popFront as a member if it so wishes. The function 
putNext() overwrites front() and then calls popFront.

d) Bidirectional:

bool empty();
ref T front();
void popFront();
ref T back();
void popBack();

popNext, putNext apply as for forward ranges.

e) Random

bool empty();
ref T front();
void popFront();
ref T back();
void popBack();
ref T opIndex(uint n);
void opIndexAssign(T, uint n);

popNext, putNext apply as for forward ranges. We need to fix the 
opIndexAssign mess.


Andrei
May 20 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 MLT wrote:

 One needs something like a lazy semi-infinite range, that only calls
 a certain function when it reaches an unexplored part.



 everybody. There must be an abstraction for a one-pass go through an
 arbitrarily long stream.
 Anyhow, I decided to change ranges as follows:
 a) Input:
 bool empty();
 ref T popNext();
 b) Output:
 void putNext(T);
 c) Forward:
 bool empty();
 ref T front();
 void popFront();
 The function ref T popNext() is a nonmember that accepts any forward
 range and uses front() and popFront(). Of course, a forward range is
 welcome to implement popFront as a member if it so wishes. The function
 putNext() overwrites front() and then calls popFront.
 d) Bidirectional:
 bool empty();
 ref T front();
 void popFront();
 ref T back();
 void popBack();
 popNext, putNext apply as for forward ranges.
 e) Random
 bool empty();
 ref T front();
 void popFront();
 ref T back();
 void popBack();
 ref T opIndex(uint n);
 void opIndexAssign(T, uint n);
 popNext, putNext apply as for forward ranges. We need to fix the
 opIndexAssign mess.
 Andrei



Please, please, please PLEASE, PRETTY PLEASE FOR THE LOVE OF GOD ALMIGHTY tell
me
you're not serious!!!  Isn't changing the interface such that forward ranges are
no longer effectively a subtype of input ranges a bit drastic?  Or do you have
some magic up your sleeve that, given any forward range, will automatically call
popFront, and then front, when popNext is called, using extension function hacks
or something?

The whole beauty of ranges is that they provide one standard interface to
program
to if all you need is a lowest common denominator level of functionality.
Frankly, if you destroy this, I think that just enforcing forward vs. input
ranges
purely by convention would be the lesser of two evils.
May 20 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 Please, please, please PLEASE, PRETTY PLEASE FOR THE LOVE OF GOD ALMIGHTY tell
me
 you're not serious!!!  Isn't changing the interface such that forward ranges
are
 no longer effectively a subtype of input ranges a bit drastic?  Or do you have
 some magic up your sleeve that, given any forward range, will automatically
call
 popFront, and then front, when popNext is called, using extension function
hacks
 or something?



Consider:

struct R
{
     bool empty();
     ref int front();
     void popFront();
}

ref int popNext(ref R fwdRange)
{
     auto result = & fwdRange.front();
     fwdRange.popFront;
     return *result;
}

void main()
{
     R r;
     int x = r.popNext;
}

This should work, I just noticed with surprise it doesn't. It's a bug, 
specifically bug 3015:

http://d.puremagic.com/issues/show_bug.cgi?id=3015


 The whole beauty of ranges is that they provide one standard interface to
program
 to if all you need is a lowest common denominator level of functionality.
 Frankly, if you destroy this, I think that just enforcing forward vs. input
ranges
 purely by convention would be the lesser of two evils.



You and I see eye to eye.


Andrei
May 20 2009
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:gv2hj8$k1n$1 digitalmars.com...

 dsimcha wrote:

 Consider:

 struct R
 {
     bool empty();
     ref int front();
     void popFront();
 }

 ref int popNext(ref R fwdRange)
 {
     auto result = & fwdRange.front();
     fwdRange.popFront;
     return *result;
 }

 void main()
 {
     R r;
     int x = r.popNext;
 }

 This should work, I just noticed with surprise it doesn't. It's a bug, 
 specifically bug 3015:

 http://d.puremagic.com/issues/show_bug.cgi?id=3015



I thought that was only supposed to work for arrays. Has that changed? If 
so, what's the new rule?
May 20 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Nick Sabalausky wrote:

 "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
 news:gv2hj8$k1n$1 digitalmars.com...

 dsimcha wrote:

 Consider:

 struct R
 {
     bool empty();
     ref int front();
     void popFront();
 }

 ref int popNext(ref R fwdRange)
 {
     auto result = & fwdRange.front();
     fwdRange.popFront;
     return *result;
 }

 void main()
 {
     R r;
     int x = r.popNext;
 }

 This should work, I just noticed with surprise it doesn't. It's a bug, 
 specifically bug 3015:

 http://d.puremagic.com/issues/show_bug.cgi?id=3015



 I thought that was only supposed to work for arrays. Has that changed? If 
 so, what's the new rule?



If a.fun(args) doesn't find fun, rewrite to fun(a, args).

Andrei
May 20 2009
prev sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
Andrei Alexandrescu wrote:

 struct R
 {
     bool empty();
     ref int front();
     void popFront();
 }
 
 ref int popNext(ref R fwdRange)
 {
     auto result = & fwdRange.front();
     fwdRange.popFront;
     return *result;
 }
 
 void main()
 {
     R r;
     int x = r.popNext;
 }
 
 This should work, I just noticed with surprise it doesn't. It's a bug, 
 specifically bug 3015:
 
 http://d.puremagic.com/issues/show_bug.cgi?id=3015



Yes. Oh yes. YES!!!
May 20 2009
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 MLT wrote:

 One needs something like a lazy semi-infinite range, that only calls
 a certain function when it reaches an unexplored part.



 everybody. There must be an abstraction for a one-pass go through an
 arbitrarily long stream.
 Anyhow, I decided to change ranges as follows:
 a) Input:
 bool empty();
 ref T popNext();
 b) Output:
 void putNext(T);
 c) Forward:
 bool empty();
 ref T front();
 void popFront();
 The function ref T popNext() is a nonmember that accepts any forward
 range and uses front() and popFront(). Of course, a forward range is
 welcome to implement popFront as a member if it so wishes. The function
 putNext() overwrites front() and then calls popFront.
 d) Bidirectional:
 bool empty();
 ref T front();
 void popFront();
 ref T back();
 void popBack();
 popNext, putNext apply as for forward ranges.
 e) Random
 bool empty();
 ref T front();
 void popFront();
 ref T back();
 void popBack();
 ref T opIndex(uint n);
 void opIndexAssign(T, uint n);
 popNext, putNext apply as for forward ranges. We need to fix the
 opIndexAssign mess.
 Andrei



(Bangs head against desk.)  Sorry.  Didn't see the part about the non-member
popNext(), though this would require Walter to make extension methods work for
structs, which should probably happen anyway.
May 20 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 MLT wrote:

 One needs something like a lazy semi-infinite range, that only calls
 a certain function when it reaches an unexplored part.



 everybody. There must be an abstraction for a one-pass go through an
 arbitrarily long stream.
 Anyhow, I decided to change ranges as follows:
 a) Input:
 bool empty();
 ref T popNext();
 b) Output:
 void putNext(T);
 c) Forward:
 bool empty();
 ref T front();
 void popFront();
 The function ref T popNext() is a nonmember that accepts any forward
 range and uses front() and popFront(). Of course, a forward range is
 welcome to implement popFront as a member if it so wishes. The function
 putNext() overwrites front() and then calls popFront.
 d) Bidirectional:
 bool empty();
 ref T front();
 void popFront();
 ref T back();
 void popBack();
 popNext, putNext apply as for forward ranges.
 e) Random
 bool empty();
 ref T front();
 void popFront();
 ref T back();
 void popBack();
 ref T opIndex(uint n);
 void opIndexAssign(T, uint n);
 popNext, putNext apply as for forward ranges. We need to fix the
 opIndexAssign mess.
 Andrei



 (Bangs head against desk.)  Sorry.  Didn't see the part about the non-member
 popNext(), though this would require Walter to make extension methods work for
 structs, which should probably happen anyway.



I should learn to never post before reading all messages...

Andrei
May 20 2009
prev sibling parent Brad Roberts <braddr puremagic.com> writes:
Andrei Alexandrescu wrote:

 dsimcha wrote:

 Please, please, please PLEASE, PRETTY PLEASE FOR THE LOVE OF GOD
 ALMIGHTY tell me
 you're not serious!!!  Isn't changing the interface such that forward
 ranges are
 no longer effectively a subtype of input ranges a bit drastic?  Or do
 you have
 some magic up your sleeve that, given any forward range, will
 automatically call
 popFront, and then front, when popNext is called, using extension
 function hacks
 or something?



 Consider:
 
 struct R
 {
     bool empty();
     ref int front();
     void popFront();
 }
 
 ref int popNext(ref R fwdRange)
 {
     auto result = & fwdRange.front();
     fwdRange.popFront;
     return *result;
 }
 
 void main()
 {
     R r;
     int x = r.popNext;
 }
 
 This should work, I just noticed with surprise it doesn't. It's a bug,
 specifically bug 3015:
 
 http://d.puremagic.com/issues/show_bug.cgi?id=3015
 
 Andrei



It was in the talk at the first conference as a 'todo for v2', but it's still on
the todo list. :)

Later,
Brad
May 20 2009