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

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
> 

"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.

Thanks for the explanation. I'll have to do some thinking about it.

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.

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.

>>>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

>>>>> 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

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.

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.