View mode: basic / threaded / horizontal-split · Log in · Help
May 31, 2005
Re: Interfaces Suck [Plz read, Walter]
On Mon, 2005-05-30 at 21:12 -0700, Walter wrote:
> "John Demme" <me@teqdruid.com> wrote in message
> news:1117478447.19815.73.camel@localhost.localdomain...
> > -Covariance.  I've been told that this simply cannot work with the
> > current D compiler implementation, and given a technical reason that I
> > don't really understand, but I don't buy it.  We've got some pretty
> > smart guys here, and I'm pretty confident that it could work.  (in other
> > news, if anyone could point me at some resources to help me understand
> > the mechanisms involved in "preventing" this from working, I'd
> > appreciate it.  I don't really have any footing to stand on if I don't
> > understand the issue.)  This one is a really big issue.  Try designing a
> > good containers library with interfaces without support for this.  Not
> > possible.
> 
> Covariance can mean different things. Exactly what meaning are you using -
> please provide an example.
Sorry.  I was referring specifically to return type covariance.
Example:
> interface I {
>         I myMeth();
> }
> class A : I {
>         A myMeth(); //Obviously, this won't link
> }
Since A implements I, logically, this should work.  DMD won't compile it
because it doesn't support interface-class return type covariance.  (I
think that's the right verbiage)

The big problem here surfaces in Containers APIs.  See example below:
> interface List {
>         List opSlice(int a, int b);
> }
> 
> class MySpecialList : List {
>         MySpecialList opSlice(int a, int b); //These won't link.
>         MySpecialList specialSort();
> }
> 
> MySpecialList someFunc(MySpecialList msl) {
>         return msl[0..3].specialSort();
> }
Again, logically this should work.  DMD doesn't support it.  Do you
understand why one would want this supported, and how severely it
cripples D's interface support?



> 
> > -Interface arrays.  Casting from Interface arrays to Object arrays
> > doesn't work.  This issue I understand, and wouldn't consider it to be a
> > bug.  That being said, it IS an issue that there is no easy way to do an
> > operation like this, short of iterating through the entire array, and
> > running the cast on each object before inserting it into a new array.
> > This has bit me a few times
> >
> > -Interfaces as AA keys.  This doesn't seem to work at all.  I dunno why.
> 
> To work in an AA, it needs to be sortable and hashable. How would interfaces
> be sorted?

The Object class has .toHash() and .opCmp() methods.  Since all
interface instances are children of Object, they've got the methods.  I
might also add that the interface I've been trying to use as a key has
both the .toHash() and .opCmp() methods in it, to force implementors to
re-implement them from Object.

> 
> > -Interfaces are not implicitly castable to objects.  All interfaces
> > instances are Objects, so this should work!
> 
> Implicit casting is a powerful tool, but if the language allows too many
> implicit casts, then things just start becoming unglued. Where the line is,
> I don't know. But to add this implicit cast to interfaces, I need a strong
> argument.

If implicitly casting from interfaces to Objects were possible, the
above AA key problem of what hash and compare methods to use would go
away... at least on the logical side.  I've no idea how this would
affect the innards.

Also, all classes are implicitly castable to their parents (including
Object) and, logically, all interface instances are children of Object
because they are classes.  Therefore, since all class instances are
implicitly castable to Object, all interfaces should be implicitly
castable to Object.  Am I explaining my reasoning well?

-John Demme
May 31, 2005
Re: Interfaces Suck [Plz read, Walter]
Sorry to reply to myself, but I was just playing around and realized
that interface-interface return type covariance isn't even supported.
So the following (although it should be perfectly legit) won't compile:
> interface Container {
>         Container dup();
> }
> interface List: Container {
> }
> class LinkedList: List {
>         List dup();
> }
I guess this is actually the same problem, but it didn't even occur to
me that this wouldn't work.  This problem is much, much worse than I
thought!

-John Demme

On Tue, 2005-05-31 at 16:56 -0400, John Demme wrote:
> On Mon, 2005-05-30 at 21:12 -0700, Walter wrote:
> > "John Demme" <me@teqdruid.com> wrote in message
> > news:1117478447.19815.73.camel@localhost.localdomain...
> > > -Covariance.  I've been told that this simply cannot work with the
> > > current D compiler implementation, and given a technical reason that I
> > > don't really understand, but I don't buy it.  We've got some pretty
> > > smart guys here, and I'm pretty confident that it could work.  (in other
> > > news, if anyone could point me at some resources to help me understand
> > > the mechanisms involved in "preventing" this from working, I'd
> > > appreciate it.  I don't really have any footing to stand on if I don't
> > > understand the issue.)  This one is a really big issue.  Try designing a
> > > good containers library with interfaces without support for this.  Not
> > > possible.
> > 
> > Covariance can mean different things. Exactly what meaning are you using -
> > please provide an example.
> Sorry.  I was referring specifically to return type covariance.
> Example:
> > interface I {
> >         I myMeth();
> > }
> > class A : I {
> >         A myMeth(); //Obviously, this won't link
> > }
> Since A implements I, logically, this should work.  DMD won't compile it
> because it doesn't support interface-class return type covariance.  (I
> think that's the right verbiage)
> 
> The big problem here surfaces in Containers APIs.  See example below:
> > interface List {
> >         List opSlice(int a, int b);
> > }
> > 
> > class MySpecialList : List {
> >         MySpecialList opSlice(int a, int b); //These won't link.
> >         MySpecialList specialSort();
> > }
> > 
> > MySpecialList someFunc(MySpecialList msl) {
> >         return msl[0..3].specialSort();
> > }
> Again, logically this should work.  DMD doesn't support it.  Do you
> understand why one would want this supported, and how severely it
> cripples D's interface support?
> 
> 
> 
> > 
> > > -Interface arrays.  Casting from Interface arrays to Object arrays
> > > doesn't work.  This issue I understand, and wouldn't consider it to be a
> > > bug.  That being said, it IS an issue that there is no easy way to do an
> > > operation like this, short of iterating through the entire array, and
> > > running the cast on each object before inserting it into a new array.
> > > This has bit me a few times
> > >
> > > -Interfaces as AA keys.  This doesn't seem to work at all.  I dunno why.
> > 
> > To work in an AA, it needs to be sortable and hashable. How would interfaces
> > be sorted?
> 
> The Object class has .toHash() and .opCmp() methods.  Since all
> interface instances are children of Object, they've got the methods.  I
> might also add that the interface I've been trying to use as a key has
> both the .toHash() and .opCmp() methods in it, to force implementors to
> re-implement them from Object.
> 
> > 
> > > -Interfaces are not implicitly castable to objects.  All interfaces
> > > instances are Objects, so this should work!
> > 
> > Implicit casting is a powerful tool, but if the language allows too many
> > implicit casts, then things just start becoming unglued. Where the line is,
> > I don't know. But to add this implicit cast to interfaces, I need a strong
> > argument.
> 
> If implicitly casting from interfaces to Objects were possible, the
> above AA key problem of what hash and compare methods to use would go
> away... at least on the logical side.  I've no idea how this would
> affect the innards.
> 
> Also, all classes are implicitly castable to their parents (including
> Object) and, logically, all interface instances are children of Object
> because they are classes.  Therefore, since all class instances are
> implicitly castable to Object, all interfaces should be implicitly
> castable to Object.  Am I explaining my reasoning well?
> 
> -John Demme
>
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
"zwang" <nehzgnaw@gmail.com> wrote in message
news:d7gp4d$ml7$1@digitaldaemon.com...
> Walter wrote:
> > To work in an AA, it needs to be sortable and hashable. How would
interfaces
> > be sorted?
>
> Why is sortability required for a hashed AA?

To deal with the inevitable hash collisions.
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
Thanks for the explanation. I'll have to do some thinking about it.
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
Walter wrote:
> "zwang" <nehzgnaw@gmail.com> wrote in message 
> news:d7gp4d$ml7$1@digitaldaemon.com...
> 
>> Walter wrote:
>> 
>>> To work in an AA, it needs to be sortable and hashable. How would 
>>> interfaces be sorted?
>> 
>> Why is sortability required for a hashed AA?
> 
> To deal with the inevitable hash collisions.

Doesn't follow:

(a) Last time I checked the AA implementation worked perfectly well on 
classes (but not structs) where unequal objects can rank equally in order.

(b) Java's HashMap manages perfectly well without this "required" "feature".

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
Stewart Gordon wrote:
> Walter wrote:
> 
>> "zwang" <nehzgnaw@gmail.com> wrote in message 
>> news:d7gp4d$ml7$1@digitaldaemon.com...
>>
>>> Walter wrote:
>>>
>>>> To work in an AA, it needs to be sortable and hashable. How would 
>>>> interfaces be sorted?
>>>
>>>
>>> Why is sortability required for a hashed AA?
>>
>>
>> To deal with the inevitable hash collisions.
> 
> 
> Doesn't follow:
> 
> (a) Last time I checked the AA implementation worked perfectly well on 
> classes (but not structs) where unequal objects can rank equally in order.
> 
> (b) Java's HashMap manages perfectly well without this "required" 
> "feature".
> 
> Stewart.
> 

It seems to me that Walter is using a binary tree for each bucket of
a hashed AA, while Java's HashMap probably using a list structure.
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
>>>Covariance can mean different things. Exactly what meaning are you using -
>>>please provide an example.
>> 
>> Can it? I thought it would be just the opposit of contravariance.
>
>But how many meanings does contravariance have?

Right, co- and contravarince are a bit complicated sometimes. E.g. there are
languages, where you can do this:

class Foo [+T] {
..
}

where the plus in front of the T means that T is a covariant type. It can only
be used in covariant positions (as return type and some other positions that
doesn't exist in D, so I won't explain them here).

So if some type D is derived from some type B than Foo[D] is derived from
Foo[B].


><snip>
>> class Derived2 : Base2 {
>> void foo (Base base) {...}  // contravariant argument type (currently not
>> supported)
>> }
><snip>
>
>So that's what this is called!  Do you know of a language that supports 
>this?

AFAIK Sather supports this.

-- Matthias Becker
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
>>>>> To work in an AA, it needs to be sortable and hashable. How would 
>>>>> interfaces be sorted?
>>>>
>>>>
>>>> Why is sortability required for a hashed AA?
>>>
>>>
>>> To deal with the inevitable hash collisions.
>> 
>> 
>> Doesn't follow:
>> 
>> (a) Last time I checked the AA implementation worked perfectly well on 
>> classes (but not structs) where unequal objects can rank equally in order.
>> 
>> (b) Java's HashMap manages perfectly well without this "required" 
>> "feature".
>> 
>> Stewart.
>> 
>
>It seems to me that Walter is using a binary tree for each bucket of
>a hashed AA, while Java's HashMap probably using a list structure.

So D's AAs are faster than Java's HashMaps, but therefor you can only store
objects that can be ordered.

Wouldn't it be better if by default a list is used and only if you explicitly
support ordering a tree is used?

-- Matthias Becker
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
Matthias Becker wrote:
<snip>
>>It seems to me that Walter is using a binary tree for each bucket of
>>a hashed AA, while Java's HashMap probably using a list structure.
> 
> So D's AAs are faster than Java's HashMaps, but therefor you can only store
> objects that can be ordered.

Try it yourself.  Define a class having appropriate opEquals and toHash 
functions, but always returning zero for opCmp.  Now try using it in an AA.

Here's a working example:

----------
import std.stream;
import std.stdio;
import std.conv;

alias std.stream.stdin stdin;

class UintBox {
    uint value;

    this(uint v) { value = v; }
    uint toHash() { return value; }
    int opEquals(Object o) { return value == (cast(UintBox) o).value; }
    int opCmp(Object o) { return 0; }
}

void main() {
    int[UintBox] aa;

    for (int i = 0; i < 10; i++) {
        UintBox key = new UintBox(toUint(stdin.readLine));
        int value = toInt(stdin.readLine);

        aa[key] = value;
    }

    writefln("Now query");

    while (true) {
        UintBox key = new UintBox(toUint(stdin.readLine));

        writefln(aa[key]);
    }
}
----------

> Wouldn't it be better if by default a list is used and only if you explicitly
> support ordering a tree is used?

Indeed.  It's one of the main arguments for getting rid of Object.opCmp.

http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/10558

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
Stewart Gordon wrote:
> Matthias Becker wrote:
> <snip>
> 
>>> It seems to me that Walter is using a binary tree for each bucket of
>>> a hashed AA, while Java's HashMap probably using a list structure.
>>
>>
>> So D's AAs are faster than Java's HashMaps, but therefor you can only 
>> store
>> objects that can be ordered.
> 
> 
> Try it yourself.  Define a class having appropriate opEquals and toHash 
> functions, but always returning zero for opCmp.  Now try using it in an AA.
> 
> Here's a working example:
> 
> ----------
> import std.stream;
> import std.stdio;
> import std.conv;
> 
> alias std.stream.stdin stdin;
> 
> class UintBox {
>     uint value;
> 
>     this(uint v) { value = v; }
>     uint toHash() { return value; }
>     int opEquals(Object o) { return value == (cast(UintBox) o).value; }
>     int opCmp(Object o) { return 0; }
> }
> 
> void main() {
>     int[UintBox] aa;
> 
>     for (int i = 0; i < 10; i++) {
>         UintBox key = new UintBox(toUint(stdin.readLine));
>         int value = toInt(stdin.readLine);
> 
>         aa[key] = value;
>     }
> 
>     writefln("Now query");
> 
>     while (true) {
>         UintBox key = new UintBox(toUint(stdin.readLine));
> 
>         writefln(aa[key]);
>     }
> }
> ----------
> 
>> Wouldn't it be better if by default a list is used and only if you 
>> explicitly
>> support ordering a tree is used?
> 
> 
> Indeed.  It's one of the main arguments for getting rid of Object.opCmp.
> 
> http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/10558
> 
> Stewart.
> 


What do you want to prove by this example?
The compiler does not care how you implement the opCmp operator at all.
1 2 3
Top | Discussion index | About this forum | D home