View mode: basic / threaded / horizontal-split · Log in · Help
November 21, 2009
Class/Interface Modeling of Ranges
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.
November 21, 2009
Re: Class/Interface Modeling of Ranges
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
November 21, 2009
Re: Class/Interface Modeling of Ranges
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...)
November 23, 2009
Re: Class/Interface Modeling of Ranges
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 
... ; }
}
November 23, 2009
Re: Class/Interface Modeling of Ranges
== 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.
Top | Discussion index | About this forum | D home