• dsimcha (21/21) Nov 20 2009 I'm thinking about what the best way might be to model ranges in an
• Andrei Alexandrescu (42/64) Nov 20 2009 I'm very glad you opened discussion on this matter!
• Lutger (5/16) Nov 21 2009 [OT] fwiw this is used in .NET a lot to prevent factoring into loads of
• BCS (10/19) Nov 23 2009 make hasLength a static const variable and it can be used for reflection...
• dsimcha (6/25) Nov 23 2009 Point of clarification, since I realized I omitted an important detail: ...

dsimcha <dsimcha yahoo.com> writes:

I'm thinking about what the best way might be to model ranges in an
OO/inheritance style for collections/containers, and needless to say it's
pretty complicated and virtually impossible to model well.  (As an aside, this
is why I like duck typing, be it compile time or traditional, so much.)

At the top of the hierarchy is forward ranges, or maybe input ranges.
Bidirectional ranges are obviously a subclass of input ranges.  Then things
get ugly.

1.  Random access ranges must also be bidirectional and define back() and
popBack() iff the range is finite.  Does iRandomAccessRange(T) inherit from
iForwardRange(T), iBidirectionalRange(T), or neither?

2.  How about length and assignable elements?  How do we fit these into the
hierarchy?  We get combinatorial explosion.  We can't have an
iRandomAccessRangeWithLengthAndAssignableElements(T), an
iRandomAccessRange(T), an iRandomAccessRangeWithAssignableElements(T), ad
nauseum.

3.  Can we simplify this by using runtime exceptions instead of compile time
errors for some of this stuff?  For example, every range would have a
hasLength() method and a length() method.  If hasLength() is false, length()
would throw.  Though this sacrifices compile time error checking, it might be
better in some ways.  For example, if a given compile time type may or may not
have length depending on its runtime type, you could check at runtime whether
it has a length and adapt your handling of it accordingly.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

dsimcha wrote:
 I'm thinking about what the best way might be to model ranges in an
 OO/inheritance style for collections/containers, and needless to say it's
 pretty complicated and virtually impossible to model well.  (As an aside, this
 is why I like duck typing, be it compile time or traditional, so much.)
 
 At the top of the hierarchy is forward ranges, or maybe input ranges.
 Bidirectional ranges are obviously a subclass of input ranges.  Then things
 get ugly.

I'm very glad you opened discussion on this matter!

A possible starting point is 
http://erdani.com/publications/on-iteration.html. If we take that route, 
then instead of input ranges we have one-pass ranges which may be used 
for input, output, or both. Another thing is that ranges must be 
parameterized on the iterated type and also on the reference type. 
Here's how I think we can do it:

interface OnePassRange(T, alias Ref) {
      property bool empty();
      property Ref!T front();
     void popFront();
}

So now we can read and write stuff. For forward ranges there's the 
save() extra operation:

interface ForwardRange(T, alias Ref) : OnePassRange!(T, Ref) {
     ForwardRange!(T, Ref) save();
}

Double-ended range adds back and popBack:

interface DoubleEndedRange(T, alias Ref) : ForwardRange!(T, Ref) {
      property Ref!T back();
     void popBack();
}

Finally we have two kinds of random access ranges:

interface InfiniteRandomAccessRange(T, alias Ref)
         : ForwardRange!(T, Ref) {
     Ref!T opIndex(size_t);
}

interface RandomAccessRange(T, alias Ref)
         : DoubleEndedRange!(T, Ref) {
     Ref!T opIndex(size_t);
     RandomAccessRange!(T, alias Ref) opSlice(size_t, size_t);
}

Things get a bit more difficult when opDollar enters the stage. I 
haven't thought that through completely yet.

 1.  Random access ranges must also be bidirectional and define back() and
 popBack() iff the range is finite.  Does iRandomAccessRange(T) inherit from
 iForwardRange(T), iBidirectionalRange(T), or neither?

I think the notions of infinite random-access range is distinct from 
that of finite random-access range.

 2.  How about length and assignable elements?  How do we fit these into the
 hierarchy?  We get combinatorial explosion.  We can't have an
 iRandomAccessRangeWithLengthAndAssignableElements(T), an
 iRandomAccessRange(T), an iRandomAccessRangeWithAssignableElements(T), ad
nauseum.

Length is a separate interface I think. Whether elements are assigned or 
not is decided by Ref. If we still have combinatorial issues, encoding 
capabilities as policies should help.

 3.  Can we simplify this by using runtime exceptions instead of compile time
 errors for some of this stuff?  For example, every range would have a
 hasLength() method and a length() method.  If hasLength() is false, length()
 would throw.  Though this sacrifices compile time error checking, it might be
 better in some ways.  For example, if a given compile time type may or may not
 have length depending on its runtime type, you could check at runtime whether
 it has a length and adapt your handling of it accordingly.

Would be great to avoid that.


Andrei

Lutger <lutger.blijdestijn gmail.com> writes:

dsimcha wrote:
...
 
 3.  Can we simplify this by using runtime exceptions instead of compile
 time
 errors for some of this stuff?  For example, every range would have a
 hasLength() method and a length() method.  If hasLength() is false,
 length()
 would throw.  Though this sacrifices compile time error checking, it might
 be
 better in some ways.  For example, if a given compile time type may or may
 not have length depending on its runtime type, you could check at runtime
 whether it has a length and adapt your handling of it accordingly.

[OT] fwiw this is used in .NET a lot to prevent factoring into loads of 
interfaces. They call it Optional Feature pattern (giving further credit to 
the idea that patterns are workarounds for weak spots in a language...)

BCS <none anon.com> writes:

Hello dsimcha,


 3.  Can we simplify this by using runtime exceptions instead of
 compile time errors for some of this stuff?  For example, every range
 would have a hasLength() method and a length() method.  If hasLength()
 is false, length() would throw.  Though this sacrifices compile time
 error checking, it might be better in some ways.  For example, if a
 given compile time type may or may not have length depending on its
 runtime type, you could check at runtime whether it has a length and
 adapt your handling of it accordingly.
 

make hasLength a static const variable and it can be used for reflection 
if you need polymorphism add a function that returns this.hasLength. Following 
that pattern, you could make much of the boiler plate into a mixin:

template Range()
{
    bool p_hasLength() { return this.hasLength; }
    int length() { static if(this.hasLength) return iLength() else thrown 
... ; }
}

dsimcha <dsimcha yahoo.com> writes:

== Quote from BCS (none anon.com)'s article
 Hello dsimcha,
 3.  Can we simplify this by using runtime exceptions instead of
 compile time errors for some of this stuff?  For example, every range
 would have a hasLength() method and a length() method.  If hasLength()
 is false, length() would throw.  Though this sacrifices compile time
 error checking, it might be better in some ways.  For example, if a
 given compile time type may or may not have length depending on its
 runtime type, you could check at runtime whether it has a length and
 adapt your handling of it accordingly.

 make hasLength a static const variable and it can be used for reflection
 if you need polymorphism add a function that returns this.hasLength. Following
 that pattern, you could make much of the boiler plate into a mixin:
 template Range()
 {
     bool p_hasLength() { return this.hasLength; }
     int length() { static if(this.hasLength) return iLength() else thrown
 ... ; }
 }

Point of clarification, since I realized I omitted an important detail:  When I
said "every range has a hasLength() method", I meant every range that inherits
from the Range interface and is part of the class hierarchy.  This does **not**
apply to struct based ranges that only use compile time duck typing and are not
part of any class hierarchy.  These would be completely unaffected.