www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Class/Interface Modeling of Ranges

reply 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.
Nov 20 2009
next sibling parent 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
Nov 20 2009
prev sibling next sibling parent 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...)
Nov 21 2009
prev sibling parent reply 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 ... ; } }
Nov 23 2009
parent 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.

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.
Nov 23 2009