www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - ProtoObject and comparison for equality and ordering

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.com> writes:
In designing ProtoObject and comparison for equality and ordering, we've 
assumed all class objects are supposed to be comparable (including 
ProtoObject themselves). That means code like this should always compile:

bool fun(C, D)(C x, D y) if (is(C == class) && is(D == class))
{
    return x < y && x == y;
}

That is, any two class objects should be comparable for equality (==, 
!=) and ordering (<. >, <=, >=). The decision whether comparison 
actually works for the types involved is deferred to runtime.


built-in means for comparison.

However the question Jonathan M Davis asked got me thinking - perhaps we 
should break with tradition and opt for a more statically-checked means 
of comparison. The drawback is that some objects would NOT be 
comparable, which may surprise some users.

As a consequence, for example, creating hash tables keyed on certain 
types will not work. This is not quite unheard of as a type could 
disable opEquals. Also, by default struct types cannot be compared for 
ordering - they must define opCmp.

Should we go with a more statically-checked/imposed approach with 
comparison, or stick with OOP tradition? Ideas welcome.
May 14 2019
next sibling parent 12345swordy <alexanderheistermann gmail.com> writes:
On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu 
wrote:

 In designing ProtoObject and comparison for equality and 
 ordering, we've assumed all class objects are supposed to be 
 comparable (including ProtoObject themselves). That means code 
 like this should always compile:

 bool fun(C, D)(C x, D y) if (is(C == class) && is(D == class))
 {
    return x < y && x == y;
 }

 That is, any two class objects should be comparable for 
 equality (==, !=) and ordering (<. >, <=, >=). The decision 
 whether comparison actually works for the types involved is 
 deferred to runtime.


 has built-in means for comparison.

 However the question Jonathan M Davis asked got me thinking - 
 perhaps we should break with tradition and opt for a more 
 statically-checked means of comparison. The drawback is that 
 some objects would NOT be comparable, which may surprise some 
 users.

 As a consequence, for example, creating hash tables keyed on 
 certain types will not work. This is not quite unheard of as a 
 type could disable opEquals. Also, by default struct types 
 cannot be compared for ordering - they must define opCmp.

 Should we go with a more statically-checked/imposed approach 
 with comparison, or stick with OOP tradition? Ideas welcome.


I say go for statically-checked/imposed approach means of 
comparison. As matter as fact do it for deconstructor as well as 
other features. Currently I can't create a deallocate function 
for class in a  nogc safe context without resorting to 
workarounds and hacks involving hidden symbols. This is a major 
pet peeve of mine that I have with D for years, which makes me 
consider it a hobby rather an serious language.
May 14 2019
prev sibling next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu 
wrote:

 In designing ProtoObject


I think ProtoObject should define *absolutely nothing*. If an 
object wants to be comparable, let it implement opEquals and 
opCmp itself (and this is D, we can use template mixins too).

We do generically have the `is` keyword for comparing any object 
for identity. Beyond that, non-identity equality might not even 
make sense for some objects... and comparison I don't think makes 
sense for *most* classes.

So no-brainer for me, go with the static approach.
May 14 2019
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.com> writes:
On 5/14/19 4:00 PM, Adam D. Ruppe wrote:

 On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu wrote:

 In designing ProtoObject


 
 I think ProtoObject should define *absolutely nothing*.


That is the case regardless. The question is whether the global __cmp 
accepts ProtoObjects.
May 14 2019
parent reply Eduard Staniloiu <edi33416 gmail.com> writes:
On Tuesday, 14 May 2019 at 20:07:08 UTC, Andrei Alexandrescu 
wrote:

 On 5/14/19 4:00 PM, Adam D. Ruppe wrote:

 On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu 
 wrote:

 In designing ProtoObject


 
 I think ProtoObject should define *absolutely nothing*.


 That is the case regardless. The question is whether the global 
 __cmp accepts ProtoObjects.


Adding some more context to this

The current design proposal states that we will have an empty 
ProtoObject as the root of all classes and interfaces that define 
what behaviours implementing types can achieve.

The proposed design for the Ordered interface is
```
interface Ordered
{
     const  nogc nothrow pure  safe scope
     int opCmp(scope const ProtoObject rhs);
}
```

Any class type that desires to be comparable should implement 
Ordered.
The reason why `Ordered`'s `opCmp` takes a `ProtoObject` is, as 
Andrei said, that there might
be some cases where we would have lost all compile time 
information and we are comparing two `ProtoObjects`. This 
interface solves this issue, but at the cost of imposing the 
function attributes on the user, instead of inferring them.

Jonathan's question got us to the point raised: maybe it doesn't 
make much sense to be able to compare two `ProtoObjects`, so 
maybe you shouldn't be able to. This would change the interface to
```
interface Ordered(T)
{
     int opCmp(scope const T rhs);
}
```

Now the attributes of `opCmp` will be inferred. The implication 
of this is that now, if we are in the worst case scenario 
(comparing two `ProtoObject`s) we can not establish any 
relationship between the two, the `__cmp` lowering won't be able 
to compare two.
This implies that the cast (runtime downcast or compile-time 
cast) will be moved at the call site, in the hands of the user; 
which might be the right thing to do.

Since we are here, I want to raise another question:
Should `opCmp` return a float?

The reason: when we attempt to compare two types that aren't 
comparable (an unordered relationship) we can return float.NaN. 
Thus we can differentiate between a valid -1, 0, 1 and an invalid 
float.NaN comparison.

Cheers,
Edi
May 14 2019
next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. 
 Thus we can differentiate between a valid -1, 0, 1 and an 
 invalid float.NaN comparison.


Seems like a job for an enum, not a float or an integer.

Mike
May 14 2019
next sibling parent reply Seb <seb wilzba.ch> writes:
On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return 
 float.NaN. Thus we can differentiate between a valid -1, 0, 1 
 and an invalid float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


+1 for enum. As far as I can see you only have four actual states:

lower, equal, higher, nonComparable
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 12:36 AM, Seb wrote:

 On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. Thus 
 we can differentiate between a valid -1, 0, 1 and an invalid 
 float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


 
 +1 for enum. As far as I can see you only have four actual states:
 
 lower, equal, higher, nonComparable


This won't work because the result of opCmp is compared against zero. 
Using a floating point number is likely to be more efficient.
May 14 2019
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:08 AM, Andrei Alexandrescu wrote:

 On 5/14/19 12:36 AM, Seb wrote:

 On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. Thus 
 we can differentiate between a valid -1, 0, 1 and an invalid 
 float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


 +1 for enum. As far as I can see you only have four actual states:

 lower, equal, higher, nonComparable


 
 This won't work because the result of opCmp is compared against zero. 
 Using a floating point number is likely to be more efficient.


s/likely/also likely/
May 14 2019
prev sibling next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Wednesday, 15 May 2019 at 00:08:10 UTC, Andrei Alexandrescu 
wrote:


 This won't work because the result of opCmp is compared against 
 zero. Using a floating point number is likely to be more 
 efficient.


Please consider the fact that some microcontrollers don't have an 
FPU.  Some may have a software floating point implementation but 
consider the cost in flash memory consumption and performance 
implementing such a thing in software.  It seems excessive.

Although it would be much more work, perhaps what is needed is a 
new type (e.g. `struct CmpResult`) with 4 immutable instances 
representing each result and an `opCmp` and `opEquals` 
implementation that does the right thing comparing against 0 or 
whatever else is needed.  Yes, it's more complicated, but I think 
it would scale better.

Mike
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:23 AM, Mike Franklin wrote:

 On Wednesday, 15 May 2019 at 00:08:10 UTC, Andrei Alexandrescu wrote:
 

 This won't work because the result of opCmp is compared against zero. 
 Using a floating point number is likely to be more efficient.


 
 Please consider the fact that some microcontrollers don't have an FPU.  
 Some may have a software floating point implementation but consider the 
 cost in flash memory consumption and performance implementing such a 
 thing in software.  It seems excessive.


Writing D code assuming float comparison is prohibitively expensive 
seems an .


 Although it would be much more work, perhaps what is needed is a new 
 type (e.g. `struct CmpResult`) with 4 immutable instances representing 
 each result and an `opCmp` and `opEquals` implementation that does the 
 right thing comparing against 0 or whatever else is needed.  Yes, it's 
 more complicated, but I think it would scale better.


Not sure there's much to gain there. a < b is lowered to a.opCmp(b) < 0. 
So then... you define opCmp to return an instance of this:

---
import std.stdio;

struct OverengineeredCmpResult {
     enum R { lt, eq, gt, ionno }
     private R payload;
     int opCmp(int alwaysZero) {
         writeln("b");
         return 0;
     }
}

struct A {
     OverengineeredCmpResult opCmp(A rhs) {
         writeln("a");
         return OverengineeredCmpResult(OverengineeredCmpResult.R.ionno);
     }
}

void main() {
     A a, b;
     if (a < b) {}
}
---

Much ado about nothing.
May 14 2019
next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Wednesday, 15 May 2019 at 00:32:32 UTC, Andrei Alexandrescu 
wrote:


 Please consider the fact that some microcontrollers don't have 
 an FPU.  Some may have a software floating point 
 implementation but consider the cost in flash memory 
 consumption and performance implementing such a thing in 
 software.  It seems excessive.


 Writing D code assuming float comparison is prohibitively 
 expensive seems an .


Not sure if that was an incomplete thought or not, but it doesn't 
seem like the right attitude for a systems programming language.
May 14 2019
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:37 AM, Mike Franklin wrote:

 On Wednesday, 15 May 2019 at 00:32:32 UTC, Andrei Alexandrescu wrote:
 

 Please consider the fact that some microcontrollers don't have an 
 FPU.  Some may have a software floating point implementation but 
 consider the cost in flash memory consumption and performance 
 implementing such a thing in software.  It seems excessive.


 Writing D code assuming float comparison is prohibitively expensive 
 seems an .


 
 Not sure if that was an incomplete thought or not, but it doesn't seem 
 like the right attitude for a systems programming language.


... anachronistic thing to do.
May 14 2019
prev sibling next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Wednesday, 15 May 2019 at 00:32:32 UTC, Andrei Alexandrescu 
wrote:


 Although it would be much more work, perhaps what is needed is 
 a new type (e.g. `struct CmpResult`) with 4 immutable 
 instances representing each result and an `opCmp` and 
 `opEquals` implementation that does the right thing comparing 
 against 0 or whatever else is needed.  Yes, it's more 
 complicated, but I think it would scale better.


 Not sure there's much to gain there. a < b is lowered to 
 a.opCmp(b) < 0. So then... you define opCmp to return an 
 instance of this:

 ---
 import std.stdio;

 struct OverengineeredCmpResult {
     enum R { lt, eq, gt, ionno }
     private R payload;
     int opCmp(int alwaysZero) {
         writeln("b");
         return 0;
     }
 }

 struct A {
     OverengineeredCmpResult opCmp(A rhs) {
         writeln("a");
         return 
 OverengineeredCmpResult(OverengineeredCmpResult.R.ionno);
     }
 }

 void main() {
     A a, b;
     if (a < b) {}
 }
 ---

 Much ado about nothing.


Cool! It actually looks much simpler than I imagined.

Mike
May 14 2019
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.com> writes:
On 5/14/19 10:35 PM, Mike Franklin wrote:

 On Wednesday, 15 May 2019 at 00:32:32 UTC, Andrei Alexandrescu wrote:
 

 Although it would be much more work, perhaps what is needed is a new 
 type (e.g. `struct CmpResult`) with 4 immutable instances 
 representing each result and an `opCmp` and `opEquals` implementation 
 that does the right thing comparing against 0 or whatever else is 
 needed.  Yes, it's more complicated, but I think it would scale better.


 Not sure there's much to gain there. a < b is lowered to a.opCmp(b) < 
 0. So then... you define opCmp to return an instance of this:

 ---
 import std.stdio;

 struct OverengineeredCmpResult {
     enum R { lt, eq, gt, ionno }
     private R payload;
     int opCmp(int alwaysZero) {
         writeln("b");
         return 0;
     }
 }

 struct A {
     OverengineeredCmpResult opCmp(A rhs) {
         writeln("a");
         return OverengineeredCmpResult(OverengineeredCmpResult.R.ionno);
     }
 }

 void main() {
     A a, b;
     if (a < b) {}
 }
 ---

 Much ado about nothing.


 
 Cool! It actually looks much simpler than I imagined.


I don't think I made my point clear. Ultimately you're still relying on 
int. The entire code does nothing relevant. It was a joke in code form.
May 15 2019
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 14, 2019 at 08:32:32PM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:
[...]

 ---
 import std.stdio;
 
 struct OverengineeredCmpResult {
     enum R { lt, eq, gt, ionno }
     private R payload;
     int opCmp(int alwaysZero) {
         writeln("b");
         return 0;
     }
 }
 
 struct A {
     OverengineeredCmpResult opCmp(A rhs) {
         writeln("a");
         return OverengineeredCmpResult(OverengineeredCmpResult.R.ionno);
     }
 }
 
 void main() {
     A a, b;
     if (a < b) {}
 }
 ---


[...]

FYI, even with the above amusingly elaborate hack, you still cannot
achieve proper 4-way comparison results.  Consider: what should
OverengineeredCmpResult.opCmp return for payload == ionno, such that <,
<=, >, >=, ==, != would all produce the correct result?

Answer: it's not possible unless you return float, because x < y
translates to x.opCmp(y) < 0, and x > y translates to x.opCmp(y) > 0, so
the only way to represent an incomparable state is for opCmp to return
some value z for which z < 0 and z > 0 are *both* false.  There is no
integer value that fits this description; the only candidate is
float.nan. Substituting the return value of opCmp with a custom struct
doesn't fix this problem; it only defers it to the custom struct's
opCmp, which suffers from the same problem.

tl;dr: it's currently *not possible* to represent an incomparable state
in opCmp with anything other than float.nan (or double.nan, etc.). No
amount of hackery with opCmp returning custom structs is going to fix
this without using float.nan at *some* point.


T

-- 
There's light at the end of the tunnel. It's the oncoming train.
May 15 2019
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/15/19 5:36 PM, H. S. Teoh wrote:

 FYI, even with the above amusingly elaborate hack, you still cannot
 achieve proper 4-way comparison results.


That was the joke.
May 15 2019
prev sibling parent Mike Franklin <slavo5150 yahoo.com> writes:
On Wednesday, 15 May 2019 at 16:36:27 UTC, H. S. Teoh wrote:


 FYI, even with the above amusingly elaborate hack, you still 
 cannot achieve proper 4-way comparison results.  Consider: what 
 should OverengineeredCmpResult.opCmp return for payload == 
 ionno, such that <, <=, >, >=, ==, != would all produce the 
 correct result?

 Answer: it's not possible unless you return float, because x < 
 y translates to x.opCmp(y) < 0, and x > y translates to 
 x.opCmp(y) > 0, so the only way to represent an incomparable 
 state is for opCmp to return some value z for which z < 0 and z

 0 are *both* false.  There is no integer value that fits this


 description; the only candidate is float.nan. Substituting the 
 return value of opCmp with a custom struct doesn't fix this 
 problem; it only defers it to the custom struct's opCmp, which 
 suffers from the same problem.


I see.  I'm a little embarrassed I didn't realize that but happy 
you took the time to explain it.  Thank you.

Mike
May 15 2019
prev sibling parent reply Noob <noob dlang.org> writes:
Any thoughts about the spaceship operator design as accepted for 
C++20?

Not invented here, but there seems to be room for improvement:

https://stackoverflow.com/q/47485803

On Wednesday, 15 May 2019 at 00:32:32 UTC, Andrei Alexandrescu 
wrote:

 ---
 import std.stdio;

 struct OverengineeredCmpResult {
     enum R { lt, eq, gt, ionno }
     private R payload;
     int opCmp(int alwaysZero) {
         writeln("b");
         return 0;
     }
 }

 struct A {
     OverengineeredCmpResult opCmp(A rhs) {
         writeln("a");
         return 
 OverengineeredCmpResult(OverengineeredCmpResult.R.ionno);
     }
 }

 void main() {
     A a, b;
     if (a < b) {}
 }
 ---
May 16 2019
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, May 16, 2019 at 05:31:19PM +0000, Noob via Digitalmars-d wrote:

 Any thoughts about the spaceship operator design as accepted for
 C++20?
 
 Not invented here, but there seems to be room for improvement:
 
 https://stackoverflow.com/q/47485803


[...]

Actually, D used to *have* the spaceship operator, and even several of
its friends like !<=, !>=, !<>=, and several others.

We deprecated them, and about a year or three ago finally got rid of
them.  Good riddance, I say.  Nobody uses them anyway, and nobody cares.
They are just a dead weight in the language, beautiful in theory but
never actually used in practice.

Don't bring those darned aliens back. ;-)


T

-- 
Trying to define yourself is like trying to bite your own teeth. -- Alan Watts
May 16 2019
prev sibling parent reply Seb <seb wilzba.ch> writes:
On Wednesday, 15 May 2019 at 00:08:10 UTC, Andrei Alexandrescu 
wrote:

 On 5/14/19 12:36 AM, Seb wrote:

 On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu 
 wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return 
 float.NaN. Thus we can differentiate between a valid -1, 0, 
 1 and an invalid float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


 
 +1 for enum. As far as I can see you only have four actual 
 states:
 
 lower, equal, higher, nonComparable


 This won't work because the result of opCmp is compared against 
 zero. Using a floating point number is likely to be more 
 efficient.


A DIP should cite real evidence/data though.

Also, note that all other cases except comparing against NaN 
require more instructions with a floating point number:

https://d.godbolt.org/z/lwzBVn
May 14 2019
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:24 AM, Seb wrote:

 On Wednesday, 15 May 2019 at 00:08:10 UTC, Andrei Alexandrescu wrote:

 On 5/14/19 12:36 AM, Seb wrote:

 On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. 
 Thus we can differentiate between a valid -1, 0, 1 and an invalid 
 float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


 +1 for enum. As far as I can see you only have four actual states:

 lower, equal, higher, nonComparable


 This won't work because the result of opCmp is compared against zero. 
 Using a floating point number is likely to be more efficient.


 
 A DIP should cite real evidence/data though.


I'm not sure I understand. I wouldn't know how to make an enum even 
work, let alone compare against that solution. I'd be in your debt if 
you showed how.


 Also, note that all other cases except comparing against NaN require 
 more instructions with a floating point number:
 
 https://d.godbolt.org/z/lwzBVn


Thanks. Looks like that's the price if we want to support unordered objects.
May 14 2019
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 15 May 2019 at 00:37:25 UTC, Andrei Alexandrescu 
wrote:

 Thanks. Looks like that's the price if we want to support 
 unordered objects.


But DO we want to support unordered objects?
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:52 AM, Adam D. Ruppe wrote:

 On Wednesday, 15 May 2019 at 00:37:25 UTC, Andrei Alexandrescu wrote:

 Thanks. Looks like that's the price if we want to support unordered 
 objects.


 
 But DO we want to support unordered objects?


In the rather general context of classes, it would be quite desirable.

The nice thing is if we opt for a statically-checked solution the user 
will be able to make a decision on the signature of opCmp in their base 
class, and then go with it. Different hierarchies may even support 
different flavors of comparisons.
May 14 2019
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 15 May 2019 at 00:54:20 UTC, Andrei Alexandrescu 
wrote:

 The nice thing is if we opt for a statically-checked solution 
 the user will be able to make a decision on the signature of 
 opCmp in their base class, and then go with it. Different 
 hierarchies may even support different flavors of comparisons.


Yes, I agree with this.

I think the opCmp discussion should be moot, as a ProtoObject 
should not be comparable anyway; it'd simply be a compile error 
to try. Just like with trying to call any other method on it, you 
need to explicitly cast it to some interface you've defined first.
May 14 2019
prev sibling parent reply Seb <seb wilzba.ch> writes:
On Wednesday, 15 May 2019 at 00:37:25 UTC, Andrei Alexandrescu 
wrote:

 On 5/14/19 1:24 AM, Seb wrote:

 On Wednesday, 15 May 2019 at 00:08:10 UTC, Andrei Alexandrescu 
 wrote:

 On 5/14/19 12:36 AM, Seb wrote:

 On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu 
 wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that 
 aren't comparable (an unordered relationship) we can 
 return float.NaN. Thus we can differentiate between a 
 valid -1, 0, 1 and an invalid float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


 +1 for enum. As far as I can see you only have four actual 
 states:

 lower, equal, higher, nonComparable


 This won't work because the result of opCmp is compared 
 against zero. Using a floating point number is likely to be 
 more efficient.


 
 A DIP should cite real evidence/data though.


 I'm not sure I understand. I wouldn't know how to make an enum 
 even work, let alone compare against that solution. I'd be in 
 your debt if you showed how.


Well, you already plan to change the compiler, so changing it to 
create a different opCmp lowering when it sees this special enum 
wouldn't be so hard, no?

i.e. if both opCmps return a special CompEnum, do sth. like this:

a < b => a.opCmp(b) == lowerCmp
...


There's no price to pay this way.
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:57 AM, Seb wrote:

 Well, you already plan to change the compiler, so changing it to create 
 a different opCmp lowering when it sees this special enum wouldn't be so 
 hard, no?


The DIP's charter does not include modifying opCmp.


 i.e. if both opCmps return a special CompEnum, do sth. like this:
 
 a < b => a.opCmp(b) == lowerCmp
 ...
 
 
 There's no price to pay this way.


Well there would be in some instances. People often implement 
comparisons as a - b currently, where a and b are int expressions. That 
would need to become...

return a < b ? lowerCmp : a > b ? upperCmp : equivCmp;

That's definitely liable to be worse for those cases.

Overall: I dream of a D landscape whereby this is enough of a problem to 
deserve discussion, a DIP, review, and implementation. As things are 
there are sufficient things to discuss and improve in D to make this 
exchange ironic.
May 14 2019
next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Wednesday, 15 May 2019 at 01:02:49 UTC, Andrei Alexandrescu 
wrote:


 Overall: I dream of a D landscape whereby this is enough of a 
 problem to deserve discussion, a DIP, review, and 
 implementation. As things are there are sufficient things to 
 discuss and improve in D to make this exchange ironic.


This is a fundamental feature of the new proposed object 
hierarchy on which so much D code will depend.  How is this not 
worthy of brainstorming, exploration, and consideration?  If it's 
not done well, and thoroughly, we'll be inventing yet another 
object hierarchy 5 years from now.  It also serves to educate 
those participating in and watching this discussion so they 
understand why things are the way they are.  Then can then spread 
that knowledge to the next generation of D programmers without 
having to query those that did that actual work and made the 
decision.

I'm seeing a lot of interesting ideas coming out of this 
discussion, and it's exciting and encouraging to know we have so 
many potential options to choose from and consider.  With a 
little patience, the dust will settle and something quite nice is 
likely to emerge.

Mike
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 2:38 AM, Mike Franklin wrote:

 On Wednesday, 15 May 2019 at 01:02:49 UTC, Andrei Alexandrescu wrote:
 

 Overall: I dream of a D landscape whereby this is enough of a problem 
 to deserve discussion, a DIP, review, and implementation. As things 
 are there are sufficient things to discuss and improve in D to make 
 this exchange ironic.


 
 This is a fundamental feature of the new proposed object hierarchy on 
 which so much D code will depend.  How is this not worthy of 
 brainstorming, exploration, and consideration?  If it's not done well, 
 and thoroughly, we'll be inventing yet another object hierarchy 5 years 
 from now.  It also serves to educate those participating in and watching 
 this discussion so they understand why things are the way they are.  
 Then can then spread that knowledge to the next generation of D 
 programmers without having to query those that did that actual work and 
 made the decision.


Of course. Changing how opCmp works does not qualify for all that.

It's all about change vs. addition. We in the D community are obsessed 
with change; if we only changed a little how that works, it would be so 
good. Yet changing how things that work work (repetition is intentional) 
is by definition low-yield; addition is fundamentally more generous and 
offers unbounded potential.

(Of course changing something that doesn't work is necessary. It's Right 
Work. Like fixing the shared qualifier.)

In this case, ProtoObject is a carefully considered addition that 
bypasses a malfunctioning artery - the Object class. But it doesn't 
change or remove it, because there's much live tissue connected to it. 
Changing how opCmp works - inserting a little botox during the surgery - 
is a damaging distraction.
May 14 2019
parent reply Jacob Carlborg <doob me.com> writes:
On 2019-05-15 04:09, Andrei Alexandrescu wrote:


 In this case, ProtoObject is a carefully considered addition that 
 bypasses a malfunctioning artery - the Object class. But it doesn't 
 change or remove it, because there's much live tissue connected to it. 
 Changing how opCmp works - inserting a little botox during the surgery - 
 is a damaging distraction.


It will cause issues with code that does `is(T : Object)` and expect 
that to be the root class. In other cases the same code has been used to 
identify D classes before `__traits(getLinkage)` was available for classes.

-- 
/Jacob Carlborg
May 15 2019
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, May 15, 2019 3:54:15 AM MDT Jacob Carlborg via Digitalmars-d 
wrote:

 On 2019-05-15 04:09, Andrei Alexandrescu wrote:

 In this case, ProtoObject is a carefully considered addition that
 bypasses a malfunctioning artery - the Object class. But it doesn't
 change or remove it, because there's much live tissue connected to it.
 Changing how opCmp works - inserting a little botox during the surgery -
 is a damaging distraction.


 It will cause issues with code that does `is(T : Object)` and expect
 that to be the root class. In other cases the same code has been used to
 identify D classes before `__traits(getLinkage)` was available for
 classes.


is(T == class) should work. And as it is, IIRC, using is(T : Object) is
already problematic due to extern(C++) classes not being derived from
Object. I think that there's also an issue with interfaces not necessarily
being classes due to how D handles COM, but fortunately, I haven't had to do
anything with COM recently, so I'm not very familiar with D's COM support.
There's also the problem that is(T : Object) can be true if alias this is
used. So, is(T : Object) probably shouldn't be used much even now, but I do
think that it's likely that adding classes below Object will break some
existing code. I'm not sure that there's much that we can do about that
though.

- Jonathan M Davis
May 15 2019
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 14, 2019 at 09:02:49PM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:
[...]

 Well there would be in some instances. People often implement
 comparisons as a - b currently, where a and b are int expressions.


[...]

FYI, the result of that is actually incorrect in some cases.  (Consider
what happens when there is overflow involved, such as int.max
- int.min, and remember the type of the result.) So, not exactly the
kind of code we should recommend, let alone bend over backwards to
support.

Int comparisons should be left as built-in operators <, =, >, etc.,
which then get translated to the correct hardware instructions that
don't suffer from the overflow bug.


T

-- 
This is not a sentence.
May 14 2019
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 15.05.19 07:30, H. S. Teoh wrote:

 On Tue, May 14, 2019 at 09:02:49PM -0400, Andrei Alexandrescu via
Digitalmars-d wrote:
 [...]

 Well there would be in some instances. People often implement
 comparisons as a - b currently, where a and b are int expressions.


 [...]
 
 FYI, the result of that is actually incorrect in some cases.  (Consider
 what happens when there is overflow involved, such as int.max
 - int.min, and remember the type of the result.) So, not exactly the
 kind of code we should recommend, let alone bend over backwards to
 support.
 
 Int comparisons should be left as built-in operators <, =, >, etc.,
 which then get translated to the correct hardware instructions that
 don't suffer from the overflow bug.
 
 
 T
 


That's not an option with opCmp, because the operators cannot be 
overloaded independently. Built-in types should just support overloaded 
operator syntax, so one can write a.opCmp(b) instead of trying to get 
overly clever with a manual implementation.
May 15 2019
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.com> writes:
On 5/15/19 1:30 AM, H. S. Teoh wrote:

 On Tue, May 14, 2019 at 09:02:49PM -0400, Andrei Alexandrescu via
Digitalmars-d wrote:
 [...]

 Well there would be in some instances. People often implement
 comparisons as a - b currently, where a and b are int expressions.


 [...]
 
 FYI, the result of that is actually incorrect in some cases.  (Consider
 what happens when there is overflow involved, such as int.max
 - int.min, and remember the type of the result.)


Thanks.


 So, not exactly the
 kind of code we should recommend, let alone bend over backwards to
 support.


All integral arithmetic is subject to overflow, at every step of the 
way. A D coder implementing opCmp would need to figure when the range of 
the operators does not put comparisons at risk, and where it does, use 
e.g. CheckedInt or a more elaborate approach.
May 15 2019
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, May 15, 2019 at 11:11:00AM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 5/15/19 1:30 AM, H. S. Teoh wrote:

 On Tue, May 14, 2019 at 09:02:49PM -0400, Andrei Alexandrescu via
Digitalmars-d wrote:
 [...]

 Well there would be in some instances. People often implement
 comparisons as a - b currently, where a and b are int expressions.


 [...]
 
 FYI, the result of that is actually incorrect in some cases.
 (Consider what happens when there is overflow involved, such as
 int.max - int.min, and remember the type of the result.)


 
 Thanks.
 

 So, not exactly the kind of code we should recommend, let alone bend
 over backwards to support.


 
 All integral arithmetic is subject to overflow, at every step of the
 way. A D coder implementing opCmp would need to figure when the range
 of the operators does not put comparisons at risk, and where it does,
 use e.g.  CheckedInt or a more elaborate approach.


In the case of integers, it's really just a matter of using the right
constructs that translate to the correct hardware instruction(s) that do
the right thing.


T

-- 
What do you call optometrist jokes? Vitreous humor.
May 15 2019
prev sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, May 14, 2019 6:24:58 PM MDT Seb via Digitalmars-d wrote:

 On Wednesday, 15 May 2019 at 00:08:10 UTC, Andrei Alexandrescu

 wrote:

 On 5/14/19 12:36 AM, Seb wrote:

 On Tuesday, 14 May 2019 at 21:06:05 UTC, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu

 wrote:

 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't
 comparable (an unordered relationship) we can return
 float.NaN. Thus we can differentiate between a valid -1, 0,
 1 and an invalid float.NaN comparison.


 Seems like a job for an enum, not a float or an integer.

 Mike


 +1 for enum. As far as I can see you only have four actual
 states:

 lower, equal, higher, nonComparable


 This won't work because the result of opCmp is compared against
 zero. Using a floating point number is likely to be more
 efficient.


 A DIP should cite real evidence/data though.

 Also, note that all other cases except comparing against NaN
 require more instructions with a floating point number:

 https://d.godbolt.org/z/lwzBVn


Except that this DIP doesn't need to define opCmp's signature - at least not
if it's not including interfaces in the design. The rules for opCmp's
signature on classes should be able to be the same as it is for structs.
Classes derived from a class that defines opCmp will be restricted by the
signature on the base class, but the base class should be able to define an
opCmp the same way that a struct would, meaning that any spec changes that
we might want to make about what opCmp returns or accepts should be able to
be completely separate from this DIP.

- Jonathan M Davis
May 15 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.com> writes:
On 5/15/19 4:09 AM, Jonathan M Davis wrote:

 Except that this DIP doesn't need to define opCmp's signature - at least not
 if it's not including interfaces in the design. The rules for opCmp's
 signature on classes should be able to be the same as it is for structs.
 Classes derived from a class that defines opCmp will be restricted by the
 signature on the base class, but the base class should be able to define an
 opCmp the same way that a struct would, meaning that any spec changes that
 we might want to make about what opCmp returns or accepts should be able to
 be completely separate from this DIP.


It seems that could work real neat.

One thing that bothers me is inheritance. It seems to me most of the 
time just inheriting opCmp and opEquals does not work - they'd need to 
be overridden to account for the added state. However, sometimes they 
_do_ just work. So I'm in two minds on whether inheriting but not 
overloading those two should be an error or not.
May 15 2019
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, May 15, 2019 at 11:14:17AM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 5/15/19 4:09 AM, Jonathan M Davis wrote:

 Except that this DIP doesn't need to define opCmp's signature - at
 least not if it's not including interfaces in the design. The rules
 for opCmp's signature on classes should be able to be the same as it
 is for structs.  Classes derived from a class that defines opCmp
 will be restricted by the signature on the base class, but the base
 class should be able to define an opCmp the same way that a struct
 would, meaning that any spec changes that we might want to make
 about what opCmp returns or accepts should be able to be completely
 separate from this DIP.


 
 It seems that could work real neat.


Yeah, I think that's the right way to go.  Don't impose any specific
signature on opCmp, and let the user derive a base class with whatever
desired signature he wants, be it int opCmp(), or float opCmp(), or
OverlyElaborateOpCmpResult opCmp().  As long as the compiler can
translate x < y to x.opCmp(y) < 0 and have it compile, that's Good
Enough.



 One thing that bothers me is inheritance. It seems to me most of the
 time just inheriting opCmp and opEquals does not work - they'd need to
 be overridden to account for the added state. However, sometimes they
 _do_ just work. So I'm in two minds on whether inheriting but not
 overloading those two should be an error or not.


How would you enforce it, though?  If we go the compile-time
introspection route, that means user base classes that define opCmp can
define whatever they want, including allowing derived classes to simply
inherit base class opCmp.  It wouldn't be ProtoObject's responsibility
to enforce any policies concerning opCmp -- it'd be up to the user to
get it right.


T

-- 
Freedom: (n.) Man's self-given right to be enslaved by his own depravity.
May 15 2019
prev sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, May 15, 2019 10:13:47 AM MDT H. S. Teoh via Digitalmars-d 
wrote:

 On Wed, May 15, 2019 at 11:14:17AM -0400, Andrei Alexandrescu via 


Digitalmars-d wrote:

 One thing that bothers me is inheritance. It seems to me most of the
 time just inheriting opCmp and opEquals does not work - they'd need to
 be overridden to account for the added state. However, sometimes they
 _do_ just work. So I'm in two minds on whether inheriting but not
 overloading those two should be an error or not.


 How would you enforce it, though?  If we go the compile-time
 introspection route, that means user base classes that define opCmp can
 define whatever they want, including allowing derived classes to simply
 inherit base class opCmp.  It wouldn't be ProtoObject's responsibility
 to enforce any policies concerning opCmp -- it'd be up to the user to
 get it right.


It wouldn't have anything to do wtih ProtoObject. Presumably, if a class
defined opCmp but not opEquals, it would be an error, and if a base class
defined opCmp, and the derived class defined either opEquals or opCmp, it
would be an error if it hadn't also defined the other.

We could also choose to do something similar to what we do when a derived
class overloads a base class function and involve alias. So, a derived class
could either override neither opEquals nor opCmp, override both, or override
one and provide an alias to the base class function for the other. I suppose
that it could also alias both, though that would be rather pointless.

As to whether we _should_ make it an error to override one but not the
other... I don't know. It seems highly unlikely that it would make sense to
override one and not the other if any behavioral changes are being made
(though you could certainly make one do something like log without caring
about the other), and the risk of bugs when you override one but not the
other would be high. So, requiring that either both or neither be overridden
would probably be worth it even if it were annoying in some cases -
especially if an alias were enough in those cases where you didn't really
want to override both.

Another consideration is that a base class could define opEquals without
defining opCpm while a derived class did define opCmp. And in that case, the
odds are much higher that overriding opEquals is unnecessary - though
requiring at least an alias could be worth it given the risk of bugs.
Certainly, it's something to think about.

toHash has similar issues if both it and opEquals are defined, though it
makes far more sense to override opEquals without overriding toHash than it
makes to override opEquals without overriding opCmp.

- Jonathan M Davis
May 15 2019
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 10:06 PM, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:
 

 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. Thus 
 we can differentiate between a valid -1, 0, 1 and an invalid float.NaN 
 comparison.


 
 Seems like a job for an enum, not a float or an integer.


I repeat myself: this won't work.

Recall that a < b is lowered into a.opCmp(b) < 0. So we have a 
comparison against the literal 0. For that float works nicely because 
nan etc etc.
May 14 2019
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 15 May 2019 at 00:19:05 UTC, Andrei Alexandrescu 
wrote:

 I repeat myself: this won't work.

 Recall that a < b is lowered into a.opCmp(b) < 0. So we have a 
 comparison against the literal 0.


We could just as well change the definition of the lowering to

a.opCmp(b) == ComparisonResult.lessThan


I understand the generated instructions would be slightly 
different and that might be relevant, but if we're talking about 
changing things, no need to arbitrarily draw the line like that.
May 14 2019
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 1:32 AM, Adam D. Ruppe wrote:

 On Wednesday, 15 May 2019 at 00:19:05 UTC, Andrei Alexandrescu wrote:

 I repeat myself: this won't work.

 Recall that a < b is lowered into a.opCmp(b) < 0. So we have a 
 comparison against the literal 0.


 
 We could just as well change the definition of the lowering to
 
 a.opCmp(b) == ComparisonResult.lessThan
 
 
 I understand the generated instructions would be slightly different and 
 that might be relevant, but if we're talking about changing things, no 
 need to arbitrarily draw the line like that.


The DIP does not set out to change the semantics of opCmp.

At a larger level I'm fascinated by our community's penchant to work on 
small problems. Comparisons in D work just fine, thank you very much, 
yet here we are calmly setting up the trench warfare. Must be an enum, 
must change opCmp, must do anything and everything as long as it's 
different from what we have. And we carefully pick up the least generous 
topics, too. In our search for water, we aren't happy until we find the 
driest patch of sand to drill into, while carefully avoiding the 
generous marshes.
May 14 2019
prev sibling parent Jonathan Marler <johnnymarler gmail.com> writes:
On Wednesday, 15 May 2019 at 00:19:05 UTC, Andrei Alexandrescu 
wrote:

 On 5/14/19 10:06 PM, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu 
 wrote:
 

 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return 
 float.NaN. Thus we can differentiate between a valid -1, 0, 1 
 and an invalid float.NaN comparison.


 
 Seems like a job for an enum, not a float or an integer.


 I repeat myself: this won't work.

 Recall that a < b is lowered into a.opCmp(b) < 0. So we have a 
 comparison against the literal 0. For that float works nicely 
 because nan etc etc.


Like you say, returning a float is the only way to allow a 
4-state result when comparing with 0.  However, since the Ordered 
interface is now a template, we can query the Type to see what 
they prefer:

//
// Allow the application to pick a result they want to use.
// Here's some example options that could be made available.
//
enum AlwaysComparableOpCmpResult : int
{
     lower = -1, equal = 0, higher = 1
}
enum SometimesNonComparableOpCmpResult : float
{
     lower = -1, equal = 0, higher = 1, nonComparable = float.nan
}
//
// A template that exposes the logic used to determine the opCmp 
return type
//
template OpCmpReturnType(T)
{
     static if (is(typeof(T.OpCmpResult))
         alias OpCmpReturnType= T;
     else
         alias OpCmpReturnType= AlwaysComparableOpCmpResult; // 
Default?

}
interface Ordered(T)
{
     OpCmpReturnType!T opCmp(scope const T rhs);
}


Policy-Based Programming anyone?

In the end, the only requirement of the return type of opCmp is 
that it being comparable to a literal "0".  So why not let the 
application decide?
May 15 2019
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2019 2:06 PM, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:
 

 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't comparable (an 
 unordered relationship) we can return float.NaN. Thus we can differentiate 
 between a valid -1, 0, 1 and an invalid float.NaN comparison.


 
 Seems like a job for an enum, not a float or an integer.


D used to support the 4 states with floating point comparisons. There was even
a 
set of operators for every case. Zero people used them. It was eventually 
deprecated, sat there for years, and finally removed. (It was proposed for C, 
and rejected, and C++ ignored it.)

     https://www.digitalmars.com/d/1.0/expression.html#floating_point_comparisons

Not a single user spoke up for it.

Here's how people write code for unordered cases:

     if (isNaN(f) || isNaN(g)) // deal with unordered cases
        ...
     else if (f < g) // only ordered cases considered here
        ...

I've seen no evidence that anyone would be interested in 4 state comparisons, 
and that's over two decades (yes, I implemented it in Digital Mars C++!).

I recommend we not waste time on this.
May 15 2019
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, May 15, 2019 at 10:37:10AM -0700, Walter Bright via Digitalmars-d wrote:
[...]

 I've seen no evidence that anyone would be interested in 4 state
 comparisons, and that's over two decades (yes, I implemented it in
 Digital Mars C++!).
 
 I recommend we not waste time on this.


In one of my projects, I wrote a simple integer set type, which
obviously included a test for the subset relation.  Originally I wanted
to use opCmp for this purpose, but couldn't, because I was unaware of
the possibility of opCmp returning a float, and therefore couldn't
represent the incomparable state.

Now that I know about this possibility, I still decided against using
opCmp for the subset relation, because opCmp draws a sharp distinction
between strictly-less vs. less-or-equal, i.e.:

	x.opCmp(y) <= 0

requires deciding whether x was a strict subset of y so that opCmp knew
whether to return -1 or 0, but in the end that extra work is thrown away
anyway because the difference is ignored by the <= 0.  Computing the
difference between -1 and 0 was useless work, even though the definition
of opCmp required it.

So either way, implementing a custom .isSubsetOf() member function was a
far better solution than trying to make any use of opCmp's support for
partial orders.  And that's not to mention people's expectation when
seeing an expression like x < y in code; I'd wager 99.999% of people
would immediately think "linear order" rather than "partial order".
Changing the meaning of < to a partial order sounds like borderline
operator overloading abuse IMO, much as I like the concept of not
arbitrarily limiting user options.


T

-- 
MAS = Mana Ada Sistem?
May 15 2019
prev sibling next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:


 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. 
 Thus we can differentiate between a valid -1, 0, 1 and an 
 invalid float.NaN comparison.


Thinking about this a little more, why would the compiler even 
allow comparing two types that aren't comparable?  Shouldn't that 
be a compiler error?

Mike
May 14 2019
next sibling parent SimonN <eiderdaus gmail.com> writes:
On Tuesday, 14 May 2019 at 21:21:56 UTC, Mike Franklin wrote:

 Thinking about this a little more, why would the compiler even 
 allow comparing two types that aren't comparable?  Shouldn't 
 that be a compiler error?


I agree that ==, <, > should not be allowed for a bare 
ProtoObject and that violation should be a compilation error, 
explaining what interface you have to implement to get comparison.

The point of ProtoObject is to fix the problems of Object. It's 
questionable that class Object allows comparison at compile time, 
but immediately throws at runtime:

     int opCmp(Object o)
     {
         throw new Exception("need opCmp for class " ~ 
typeid(this).name);
     }

This brought a latent bug in my code: I put a class that didn't 
override opCmp into an associative array. All goes well as long 
as the hashes were different. Then, months later, the code 
crashes when two hashes collide and opCmp is called.

Certainly that bug was my fault, but maybe we can prevent such 
bugs at compile time with ProtoObject?

-- Simon
May 14 2019
prev sibling next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, May 14, 2019 3:21:56 PM MDT Mike Franklin via Digitalmars-d 
wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:

 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't
 comparable (an unordered relationship) we can return float.NaN.
 Thus we can differentiate between a valid -1, 0, 1 and an
 invalid float.NaN comparison.


 Thinking about this a little more, why would the compiler even
 allow comparing two types that aren't comparable?  Shouldn't that
 be a compiler error?


The issue is being able to reproduce the behavior of comparing floating
point types when one of them is NaN. That design of floating point
comparison does make some sense with regards to floating points but
seriously complicates things for overloading opCmp. In general, it really
doesn't make sense to return anything other than an integral value, but if
you want to be able to create a type that wraps floats (e.g. Nullable!float)
or emulates them in some manner, then you need more flexibility.

Given that, it's probably sufficient if the spec requires that the type be
comparable with -1, 0, and 1 with the comparison operators being generated
from that rather than requiring a specific type (which IIRC is more or less
what the spec currently says for structs). Even if a class returned some
weird type that took int or float for its opCmp so that you when was
compared against -1, 0, and/or 1 to generate a comparison operator, I don't
_think_ that you could really do anything with that ultimately other than
just get weird results for the comparison.

As long as the code using the comparison operators with a class object is
templated, it really shouldn't matter what the exact signature is so long as
it compiles with the right types - just like with structs. And if the code
isn't templated, then it would likely be operating on whatever the base
class was that implemented opCmp in that particular class hierarchy. Either
way, I don't see any reason for the rules for the signature of opCmp with
classes to be any different from opCmp and structs aside from where a
derived class is restricted by how its base class declared it.

- Jonathan M Davis
May 14 2019
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 14, 2019 at 03:47:18PM -0600, Jonathan M Davis via Digitalmars-d
wrote:

 On Tuesday, May 14, 2019 3:21:56 PM MDT Mike Franklin via Digitalmars-d 
 wrote:


[...]

 Thinking about this a little more, why would the compiler even allow
 comparing two types that aren't comparable?  Shouldn't that be a
 compiler error?


 
 The issue is being able to reproduce the behavior of comparing
 floating point types when one of them is NaN. That design of floating
 point comparison does make some sense with regards to floating points
 but seriously complicates things for overloading opCmp. In general, it
 really doesn't make sense to return anything other than an integral
 value, but if you want to be able to create a type that wraps floats
 (e.g. Nullable!float) or emulates them in some manner, then you need
 more flexibility.


[...]

Moreover, Andrei has mentioned before that opCmp can technically be used
for implementing partial orders. I had thought otherwise in the past,
because I only considered opCmp that returns int. However, if opCmp is
allowed to return float, then you can return float.nan for the
incomparable case (e.g., two sets that are not subsets of each other)
and thus achieve a non-linear partial ordering, such as the subset
relation.

Whether or not this is a *good* way of implementing the subset operation
is a different question, of course. If we restricted opCmp to only
linear orderings, then this wouldn't be an issue.


T

-- 
Curiosity kills the cat. Moral: don't be the cat.
May 14 2019
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 12:13 AM, H. S. Teoh wrote:

 Moreover, Andrei has mentioned before that opCmp can technically be used
 for implementing partial orders. I had thought otherwise in the past,
 because I only considered opCmp that returns int. However, if opCmp is
 allowed to return float, then you can return float.nan for the
 incomparable case (e.g., two sets that are not subsets of each other)
 and thus achieve a non-linear partial ordering, such as the subset
 relation.
 
 Whether or not this is a*good*  way of implementing the subset operation
 is a different question, of course. If we restricted opCmp to only
 linear orderings, then this wouldn't be an issue.


opCmp returning float has become a popular D idiom, and banking on that 
is the right thing to do.
May 14 2019
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 10:21 PM, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:
 

 Should `opCmp` return a float?

 The reason: when we attempt to compare two types that aren't 
 comparable (an unordered relationship) we can return float.NaN. Thus 
 we can differentiate between a valid -1, 0, 1 and an invalid float.NaN 
 comparison.


 
 Thinking about this a little more, why would the compiler even allow 
 comparing two types that aren't comparable?  Shouldn't that be a 
 compiler error?


Their dynamic types may be comparable.
May 14 2019
parent Mike Franklin <slavo5150 yahoo.com> writes:
On Wednesday, 15 May 2019 at 00:15:38 UTC, Andrei Alexandrescu 
wrote:


 Thinking about this a little more, why would the compiler even 
 allow comparing two types that aren't comparable?  Shouldn't 
 that be a compiler error?


 Their dynamic types may be comparable.


Then shouldn't the author be using their comparable dynamic types 
explicitly when performing a comparison?
May 14 2019
prev sibling next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:

 Adding some more context to this


thanks, yeah I missed most of dconf for various reasons 
(hopefully will catch up when the videos released though) so this 
is good to read.


 Jonathan's question got us to the point raised: maybe it 
 doesn't make much sense to be able to compare two 
 `ProtoObjects`, so maybe you shouldn't be able to. This would 
 change the interface to


Yeah, I would agree with that. It is hard to imagine a class that 
should actually be ordered with respect to a totally separate and 
unknown class. How would you possibly compare `MyDomElement < 
MySimpleWindow`? It's absurd.

Let's try to think of a case where it might make sense. Maybe I 
define class MyString. That can be sorted along side with other 
MyStrings. Ditto with char[].

class MyString : Ordered!MyString, Ordered!(char[])

So what if you defined YourString that is basically the same. I 
can see the argument where maybe someone, using our two libraries 
together, would want to:

ProtoObject[] objs;
objs ~= new MyString();
objs ~= new YourString();
sort(objs);

But how would you even implement that now? You have to cast 
inside opCmp... and that means one of the two classes must know 
about the other to realize that cast.

And if they knew about the other, they could explicitly declare 
that in the interface list.

And then you would store `Ordered!YourString[] objs;` instead of 
`ProtoObject`; make an array of the least common ancestor that 
actually defines the necessary interface.

So...


 ```
 interface Ordered(T)
 {
     int opCmp(scope const T rhs);
 }
 ```


Yeah, I don't think we actually lose anything of value going this 
way. Let's do it.



 Since we are here, I want to raise another question:
 Should `opCmp` return a float?


My view is if they cannot be compared, they shouldn't implement 
the interface.

For cases where some values are comparable and some aren't (like 
float.nan or maybe null), I'm kinda ok just saying you return -1 
or whatever and it is undefined order.
May 14 2019
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 10:29 PM, Adam D. Ruppe wrote:

 thanks, yeah I missed most of dconf for various reasons (hopefully will 
 catch up when the videos released though) so this is good to read.


Aren't the unedited streams already available?
May 14 2019
prev sibling next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
So, going back to where the int/float/enum tangent started....

On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:

 interface Ordered(T)
 {
     int opCmp(scope const T rhs);
 }

 Since we are here, I want to raise another question:
 Should `opCmp` return a float?



We'd then have two interfaces: Ordered!T, which returns the int, 
and then PartiallyOrdered!T that can return the float. You pick 
which one works best for your particular class.
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 2:03 AM, Adam D. Ruppe wrote:

 So, going back to where the int/float/enum tangent started....
 
 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:

 interface Ordered(T)
 {
     int opCmp(scope const T rhs);
 }

 Since we are here, I want to raise another question:
 Should `opCmp` return a float?


 
 
 We'd then have two interfaces: Ordered!T, which returns the int, and 
 then PartiallyOrdered!T that can return the float. You pick which one 
 works best for your particular class.


Wait, if we go with the statically-checked solution all interfaces are 
no longer necessary. Or maybe I'm misunderstanding?
May 14 2019
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 15 May 2019 at 01:16:56 UTC, Andrei Alexandrescu 
wrote:

 Wait, if we go with the statically-checked solution all 
 interfaces are no longer necessary. Or maybe I'm 
 misunderstanding?


interfaces are just one strategy for static checking, not a 
requirement. There'd be nothing special about these.

Realistically, the compiler wouldn't care if there's an interface 
or not. It just wants to see if the opCmp method is there and can 
be called, exactly the same as it does for structs.

The interfaces are just a way of communicating this to the user, 
documenting and formalizing the convention.
May 14 2019
prev sibling next sibling parent reply Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:

 Now the attributes of `opCmp` will be inferred. The implication 
 of this is that now, if we are in the worst case scenario 
 (comparing two `ProtoObject`s) we can not establish any 
 relationship between the two, the `__cmp` lowering won't be 
 able to compare two.


That's ok. Why should anybody expect that two arbitrary things 
should have an ordered relation? Is egg > apple? And in what way? 
Is it heavier? longer? older? better? has more calories?
Stupid.

 Since we are here, I want to raise another question:
 Should `opCmp` return a float?


Yes, please!
I need unordered relations so often (see above)!
May 15 2019
parent SimonN <eiderdaus gmail.com> writes:
On Wednesday, 15 May 2019 at 07:10:44 UTC, Dominikus Dittes 
Scherkl wrote:

 On Tuesday, 14 May 2019 at 20:36:08 UTC, Eduard Staniloiu wrote:

 (comparing two `ProtoObject`s) we can not establish any 
 relationship between the two, the `__cmp` lowering won't be 
 able to compare two.


 That's ok. Why should anybody expect that two arbitrary things 
 should have an ordered relation? Is egg > apple? And in what 
 way? Is it heavier? longer? older? better? has more calories?

 Since we are here, I want to raise another question:
 Should `opCmp` return a float?


 Yes, please!
 I need unordered relations so often (see above)!


It's fine if we can add a partial order to some classes, or a 
linear order to other classes. There can be two static 
introspections/two interfaces for these two orderings. (And 
linear orders also qualify as partial orders during 
introspection.)

Comparing two objects from a partial order, such a comparison 
should be able to yield uncomparable, no problem.

Comparing two objects from two different class hierarchies that 
define two unrelated partial orders, I don't have an opinion on 
whether this should compile, or whether it may even return that 
one is greater than the other.

Comparing two ProtoObjects should always be a compilation error.

We should not assume partial orders everywhere. That can lead to 
roundabout code: Linear orders are common, and I don't want to 
handle any uncomparable case for linear orders. And readers of my 
code should immediately see that there is no bug here, i.e., that 
I didn't forget to think about the uncomparable case.

Thus I wouldn't change int opCmp to float opCmp -- for linear 
orders, I like a static guarantee that different objects are 
always comparable and never NaN.

-- Simon
May 15 2019
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/14/19 9:36 PM, Eduard Staniloiu wrote:


 Jonathan's question got us to the point raised: maybe it doesn't make 
 much sense to be able to compare two `ProtoObjects`, so maybe you 
 shouldn't be able to. This would change the interface to
 ```
 interface Ordered(T)
 {
      int opCmp(scope const T rhs);
 }
 ```
 
 Now the attributes of `opCmp` will be inferred.


Just wanted to make sure you understand this is not the case. opCmp in 
this instance is a virtual call, and will NOT have attributes inferred.

There isn't really a way to define an interface for this, nor do you 
need to.

Just define the opCmp you want in your own interface/base object, and 
then you can compare those. Almost nobody wants to compare 2 completely 
unrelated objects.

-Steve
May 15 2019
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, May 15, 2019 2:56:53 AM MDT Steven Schveighoffer via 
Digitalmars-d wrote:

 On 5/14/19 9:36 PM, Eduard Staniloiu wrote:

 Jonathan's question got us to the point raised: maybe it doesn't make
 much sense to be able to compare two `ProtoObjects`, so maybe you
 shouldn't be able to. This would change the interface to
 ```
 interface Ordered(T)
 {

      int opCmp(scope const T rhs);

 }
 ```

 Now the attributes of `opCmp` will be inferred.


 Just wanted to make sure you understand this is not the case. opCmp in
 this instance is a virtual call, and will NOT have attributes inferred.

 There isn't really a way to define an interface for this, nor do you
 need to.

 Just define the opCmp you want in your own interface/base object, and
 then you can compare those. Almost nobody wants to compare 2 completely
 unrelated objects.


Indeed. Inference comes when the code around the member function is
templated. For instance, if you have phobos' RedBlackTree, it uses opCmp,
and it's templated. So, opCmp on the class can then have whatever attributes
are appropriate and the code in RedBlack that uses opCmp will infer those
attributes rather than forcing  safe or nothrow or whatever.

Similarly, with the free functions opEquals being templated, it would have
its attributes inferred based on how opEquals was defined on the classes
being compared, allowing == to be  safe, pure, etc. - or not - based on how
opEquals was declared on those classes, thereby allowing classes with an
 safe opEquals to be used in  safe code.

The functions on the class itself can only have their attributes inferred if
they're templated (which means that they can't be virtual), or they return
auto. So, in most cases, the attributes on these functions on classes
probably won't use inferrence, but the code that uses them will.

- Jonathan M Davis
May 15 2019
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, May 15, 2019 at 09:56:53AM +0100, Steven Schveighoffer via
Digitalmars-d wrote:

 On 5/14/19 9:36 PM, Eduard Staniloiu wrote:

 Jonathan's question got us to the point raised: maybe it doesn't
 make much sense to be able to compare two `ProtoObjects`, so maybe
 you shouldn't be able to. This would change the interface to
 ```
 interface Ordered(T)
 {
      int opCmp(scope const T rhs);
 }
 ```
 
 Now the attributes of `opCmp` will be inferred.


 
 Just wanted to make sure you understand this is not the case. opCmp in
 this instance is a virtual call, and will NOT have attributes
 inferred.
 
 There isn't really a way to define an interface for this, nor do you
 need to.
 
 Just define the opCmp you want in your own interface/base object, and
 then you can compare those. Almost nobody wants to compare 2
 completely unrelated objects.


[...]

+1.  *This* is the right way to go.  Forget about using interfaces or
other such inferior hacks; D has powerful compile-time introspection,
why aren't we taking full advantage of it??  Let the user define their
own base class (or interface) with whatever definition of opCmp they
wish to have. This solves a host of issues:

1) How to define opCmp in a way that satisfies everyone: some people
want int opCmp, some want float opCmp, etc.. Why make the decision for
them? Let them decide themselves which version their opCmp wants. Pass
the buck to the user.

2) How to attribute opCmp in a non-restrictive way: pass the buck to the
user.

3) How to compare two ProtoObjects?  If the user wants to compare two
disparate objects, let them define their own common base class with an
appropriate version of opCmp. Pass the buck to the user.

4) What if this doesn't work? (I.e., the user has two objects from two
completely unrelated, opaque, binary-only libraries whose opCmp's are
not compatible with each other.)  Easy, you already know nothing about
the two objects, and since they are related they don't have any
meaningfully-comparable state anyway, so just wrap them in a struct
whose opCmp just compares their respective pointer values:

	struct ComparableProtoObject {
		ProtoObject payload;
		int opCmp(in ComparableProtoObject o)  trusted {
			auto a = cast(void*)payload;
			auto b = cast(void*)o.payload;
			return (a < b) ? -1 : (a > b) ? 1 : 0;
		}
	}

IOW, pass the buck to the user.

4) What about inheritance? See (2).  Pass the buck to the user.

5) What about AA's?  For something to be hashable, you need .toHash,
.opEquals, and perhaps .opCmp (depending on whether the AA's buckets
needs stuff to be orderable).  So either the user creates a Hashable
interface for their objects with appropriate definitions of toHash,
opEquals, and opCmp, or see (4). IOW, pass the buck to the user.


The user is not an idiot; give him the tools to do what he wants instead
of making decisions for him and handing it down from on high.


T

-- 
This sentence is false.
May 15 2019
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 14, 2019 at 08:00:09PM +0000, Adam D. Ruppe via Digitalmars-d wrote:

 On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu wrote:

 In designing ProtoObject


 
 I think ProtoObject should define *absolutely nothing*. If an object
 wants to be comparable, let it implement opEquals and opCmp itself
 (and this is D, we can use template mixins too).


[...]

Yeah, from the Dconf slides, I was under the impression that ProtoObject
is supposed to contain absolute nothing at all, with a bunch of optional
interfaces like Comparable, Hashable, Stringifiable, Synchronizable,
etc., that define the corresponding operations *for those classes that
need it*.

But going with the static approach is even better than using interfaces,
because then you can have the compiler infer attributes for opEquals,
opCmp, etc., without suffering the limitations of the current
Object.opXXX and the associated attributes.

So yeah, I also vote for the static approach.


T

-- 
Dogs have owners ... cats have staff. -- Krista Casada
May 14 2019
prev sibling next sibling parent reply Mike Franklin <slavo5150 yahoo.com> writes:
On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu 
wrote:

 In designing ProtoObject and comparison for equality and 
 ordering, we've assumed all class objects are supposed to be 
 comparable (including ProtoObject themselves).


What's the rationale for that?  And are you talking about 
reference equality or value equality?


 That means code like this should always compile:

 bool fun(C, D)(C x, D y) if (is(C == class) && is(D == class))
 {
    return x < y && x == y;
 }

 That is, any two class objects should be comparable for 
 equality (==, !=) and ordering (<. >, <=, >=). The decision 
 whether comparison actually works for the types involved is 
 deferred to runtime.


IMO, objects should only support reference equality out of the 
box.



 has built-in means for comparison.



https://dotnetfiddle.net/AOQ0Ry


 However the question Jonathan M Davis asked got me thinking -




 perhaps we should break with tradition and opt for a more 
 statically-checked means of comparison.


Yes, please.


 The drawback is that some objects would NOT be comparable, 
 which may surprise some users.


Not me.


 As a consequence, for example, creating hash tables keyed on 
 certain types will not work. This is not quite unheard of as a 
 type could disable opEquals. Also, by default struct types 
 cannot be compared for ordering - they must define opCmp.

 Should we go with a more statically-checked/imposed approach 
 with comparison, or stick with OOP tradition? Ideas welcome.


I don't agree that there is such a tradition, and even if there 
was, we should be questioning it.

I would like to distinguish between reference equality and value 
equality.  Reference equality, I think, should be done with the 
`is` operator, and should probably work out of the box. And I 
like the idea of users opting into any feature.  If users want to 
support value equality, they should implement `opEquals`.  If 
they want comparability they should implement `opCmp`.  If they 
want to support hashability, the should be required to implement 
a `getHash` or something along that line of thinking.


 The question is whether the global __cmp accepts ProtoObjects.


No, but it could accept something derived from `ProtObject` that 
has the necessary requisites, namely `opCmp`, which I believe can 
be checked statically.

Final thought.  Other languages don't have the 
design-by-introspection features that D has.  If they did, maybe 
they wouldn't have chosen the path they did.  D has an 
opportunity here to lead instead of follow.

Mike
May 14 2019
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 9:37 PM, Mike Franklin wrote:

 On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu wrote:

 In designing ProtoObject and comparison for equality and ordering, 
 we've assumed all class objects are supposed to be comparable 
 (including ProtoObject themselves).


 
 What's the rationale for that?


Pretty much principle of least surprise for existing D users.


 And are you talking about reference 
 equality or value equality?


Depends on how the user implements it. The intent is to support 
meaningful comparison of the content of objects.


 IMO, objects should only support reference equality out of the box.


So that means "x is y" works but not "x == y"?



 built-in means for comparison.


 

 https://dotnetfiddle.net/AOQ0Ry


Affirmative. Same in Java, is that correct?


 I would like to distinguish between reference equality and value 
 equality.  Reference equality, I think, should be done with the `is` 
 operator, and should probably work out of the box. And I like the idea 
 of users opting into any feature.  If users want to support value 
 equality, they should implement `opEquals`.  If they want comparability 
 they should implement `opCmp`.  If they want to support hashability, the 
 should be required to implement a `getHash` or something along that line 
 of thinking.


Sounds good. If we go with the notion "you can't key a built-in 
hashtable on any class type" that should work.
May 14 2019
next sibling parent Mike Franklin <slavo5150 yahoo.com> writes:
On Tuesday, 14 May 2019 at 21:05:02 UTC, Andrei Alexandrescu 
wrote:


 And are you talking about reference equality or value equality?


 Depends on how the user implements it. The intent is to support 
 meaningful comparison of the content of objects.



and I hate it because it allows the author to effectively change 
the semantics of the `==` operator.  I like that D has a clear 
distinction between `is` and `==`.  Please keep them distinctly 
separate.


 IMO, objects should only support reference equality out of the 
 box.


 So that means "x is y" works but not "x == y"?


Yes.



 https://dotnetfiddle.net/AOQ0Ry


 Affirmative. Same in Java, is that correct?


Sorry, I don't have any experience with Java in this regard.

Mike
May 14 2019
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 14, 2019 at 05:05:02PM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 5/14/19 9:37 PM, Mike Franklin wrote:


[...]

 IMO, objects should only support reference equality out of the box.


 
 So that means "x is y" works but not "x == y"?


That makes sense to me if x and y are two completely unrelated classes.
Yes they are "related" in the sense that both inherit from ProtoObject,
but they have no meaningful relationship as far as the application
domain is concerned.  If the user wants to compare them, let him
implement the Comparable interface and the corresponding opCmp(). This
shouldn't be in ProtoObject.


[...]

 I would like to distinguish between reference equality and value
 equality.  Reference equality, I think, should be done with the `is`
 operator, and should probably work out of the box. And I like the
 idea of users opting into any feature.  If users want to support
 value equality, they should implement `opEquals`.  If they want
 comparability they should implement `opCmp`.  If they want to
 support hashability, the should be required to implement a `getHash`
 or something along that line of thinking.


 
 Sounds good. If we go with the notion "you can't key a built-in
 hashtable on any class type" that should work.


I think it would make more sense to have to implement a Hashable
interface (defining an opHash and possibly also inheriting from
Comparable if we want to allow AA implementations that require ordering,
e.g., to use tree buckets) for this purpose.  While being able to throw
any arbitrary object into an AA and having it Just Work is kinda nice,
that's an optional extra and we shouldn't be bending over backwards just
to support that.

Besides, realistically speaking, how useful is an AA that may contain
any arbitrary class, where looking up one key might give you a GuiWidget
but looking up a different key gives you a CryptoAlgorithm and looking
up a third key gives you a GeometricShape?  I can't see how such a thing
could be useful in any meaningful way.  I'd expect that if the user
wanted to put two different classes in the same AA he'd at least bother
to define a common base class that implements the appropriate Hashable
interface.


T

-- 
The volume of a pizza of thickness a and radius z can be described by the
following formula: pi zz a. -- Wouter Verhelst
May 14 2019
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/19 12:24 AM, H. S. Teoh wrote:

 Besides, realistically speaking, how useful is an AA that may contain
 any arbitrary class, where looking up one key might give you a GuiWidget
 but looking up a different key gives you a CryptoAlgorithm and looking
 up a third key gives you a GeometricShape?  I can't see how such a thing
 could be useful in any meaningful way.


Definitely meaningful. The key would be an object, not the value. There 
are many applications in which you'd want to associate data with a 
variety of objects.
May 14 2019
prev sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, May 14, 2019 5:24:58 PM MDT H. S. Teoh via Digitalmars-d wrote:

 On Tue, May 14, 2019 at 05:05:02PM -0400, Andrei Alexandrescu via


Digitalmars-d wrote:

 On 5/14/19 9:37 PM, Mike Franklin wrote:


 [...]


 IMO, objects should only support reference equality out of the box.


 So that means "x is y" works but not "x == y"?


 That makes sense to me if x and y are two completely unrelated classes.
 Yes they are "related" in the sense that both inherit from ProtoObject,
 but they have no meaningful relationship as far as the application
 domain is concerned.  If the user wants to compare them, let him
 implement the Comparable interface and the corresponding opCmp(). This
 shouldn't be in ProtoObject.


Even an interface is a problem, because then that locks in the attributes.
Containers and the code in druntime can be templated, and any user code that
can't be templated can operate on a base class that implements opCmp (or
opEquals or whatever function we're talking about) where that base class is
whatever is appropriate for that particular class hierarchy. Code bases
could even still have interfaces with opEquals or opCmp if appropriate. We
just don't want standard interfaces, because that would lock in the
attributes, and not all attributes are going to work for all code bases (a
prime example of that being const; requiring const for opEquals, opCmp,
toString, or toHash would make it so that lazy initialization pretty much
wouldn't work with classes).

By templatizing all of the relevant code in druntime, the attributes will be
inferred, and we can define these functions on classes in the same way that
we do with structs - just with the caveat that any class derived from a
class that defines such a function will be restricted by how the base class
defined it. However, whereas Object forces all D classes to stick to a
particular set of attributes for those functions, they would only be locked
in for that particular class hierarchy, and other class hierarchies could
make other choices. And by having the relevant druntime code be templated,
standard interfaces shouldn't be necessary, whereas if we created such
interfaces, we'd basically be making the same mistake that we made with
Object except with a different set of attributes.

- Jonathan M Davis
May 14 2019
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 15 May 2019 at 06:19:19 UTC, Jonathan M Davis wrote:

 Even an interface is a problem, because then that locks in the 
 attributes.


That's not completely true in general, and only sort of true in 
this specific situation.

In general, attributes are semi-locked, accordance to the Liskov 
substitution principle: you can tighten constraints, but not 
loosen them on child classes.

(Like with current Object, which has no attributes, you are 
allowed to define a child class with `override  nogc  safe 
nothrow` etc. But once you do that, you can never remove them in 
child classes, since then you'd be breaking the promise of the 
parent class' interface)


In this specific situation, the attributes are only locked in 
after you define them - which is the same if you did it with or 
without the interface. The interface itself does not demand 
anything unless it specifically lists them.

But, note, they also are not inferred.


 By templatizing all of the relevant code in druntime


There should be NO code in druntime! All `a < b` is is syntax 
sugar for a method call. It does not need and should not use any 
other function. Just let the compiler rewrite the syntax to the 
call and then do its thing.

The ProtoObject version of __cmp should simply not exist.
May 15 2019
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, May 15, 2019 6:40:46 AM MDT Adam D. Ruppe via Digitalmars-d 
wrote:

 On Wednesday, 15 May 2019 at 06:19:19 UTC, Jonathan M Davis wrote:

 Even an interface is a problem, because then that locks in the
 attributes.


 That's not completely true in general, and only sort of true in
 this specific situation.

 In general, attributes are semi-locked, accordance to the Liskov
 substitution principle: you can tighten constraints, but not
 loosen them on child classes.

 (Like with current Object, which has no attributes, you are
 allowed to define a child class with `override  nogc  safe
 nothrow` etc. But once you do that, you can never remove them in
 child classes, since then you'd be breaking the promise of the
 parent class' interface)


 In this specific situation, the attributes are only locked in
 after you define them - which is the same if you did it with or
 without the interface. The interface itself does not demand
 anything unless it specifically lists them.

 But, note, they also are not inferred.


Yeah. My point isn't that the exact list of attributes you put on opEquals,
opCmp, etc. is exactly what must be on derived classes. My point is that
once you do or don't put some of those attributes on the function in a base
class, that restricts which attributes can be put on the overrides in
derived classes. The interfaces proposed in Eduard's dconf talk this year
involved making all of the relevant functions  safe const pure nothrow, and
that's a serious problem for any classes that want to do something with
those functions that is incompatible with those attributes. By just letting
user-defined classes define those functions more or less however they want
(like with structs), we make it possible for each class hierarchy to define
them in whatever way is appropriate for that class hierarchy, whereas if we
create an interface, we're restricting what _every_ class can do with
attributes on those functions - which is part of the problem that we have
with Object right now.


 By templatizing all of the relevant code in druntime


 There should be NO code in druntime! All `a < b` is is syntax
 sugar for a method call. It does not need and should not use any
 other function. Just let the compiler rewrite the syntax to the
 call and then do its thing.

 The ProtoObject version of __cmp should simply not exist.


That's not true for everything (opEquals specifically has a free function
druntime that calls the opEquals on classes), but what it comes down to in
general is that code that uses opCmp (or any of these functions) in druntime
needs to be templatized rather than being designed to operate on a specific
base class. So, even if opCmp itself doesn't require that code be in
druntime to work, there potentially is relevant code in druntime which would
need to be templatized. Certainly, that's true for opEquals and toHash
because of AAs if nothing else. Regarldess, yeah, ProtoObject shouldn't have
any form of any of these functions on it.

- Jonathan M Davis
May 15 2019
prev sibling next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, May 14, 2019 1:34:12 PM MDT Andrei Alexandrescu via Digitalmars-
d wrote:

 In designing ProtoObject and comparison for equality and ordering, we've
 assumed all class objects are supposed to be comparable (including
 ProtoObject themselves). That means code like this should always compile:

 bool fun(C, D)(C x, D y) if (is(C == class) && is(D == class))
 {
     return x < y && x == y;
 }

 That is, any two class objects should be comparable for equality (==,
 !=) and ordering (<. >, <=, >=). The decision whether comparison
 actually works for the types involved is deferred to runtime.


 built-in means for comparison.

 However the question Jonathan M Davis asked got me thinking - perhaps we
 should break with tradition and opt for a more statically-checked means
 of comparison. The drawback is that some objects would NOT be
 comparable, which may surprise some users.

 As a consequence, for example, creating hash tables keyed on certain
 types will not work. This is not quite unheard of as a type could
 disable opEquals. Also, by default struct types cannot be compared for
 ordering - they must define opCmp.

 Should we go with a more statically-checked/imposed approach with
 comparison, or stick with OOP tradition? Ideas welcome.


Well, I think that my stance on it is pretty clear at this point. Languages

have templates and thus had to have containers and the like contain Object
rather than the actual type. D does not have that problem.

By templatizing the core infrastructure such as the free function opEquals
that == gets lowered to for classes, any class that defined the appropriate
function could then work with whatever attributes were on it (basically like
we have now for structs). As soon as a class defined opEquals or toString or
whatever, any classes derived from that class would then be restricted by
the attribute choices on the base class, but only that class hierarchy would
then have to live with that decision rather than the entire language like
what we have now with Object or what was shown with interfaces in Eduard's
talk. So, each class hierarchy could use whichever set of attributes made
sense for it.

All we'd really lose that I can see is the ability to compare classes from
disparate hierarchies, which has never really worked properly or made much
sense anyway. You just end up with unrelated objects not being considered
equal instead of statically knowing that you're comparing objects that
aren't really logically comparable. The full dynamic capabilities of
inheritance and polymorphism are still there within class hierarchies. They
just aren't at the root object level and thus would require casting to more
specific types to use them. And by not having them at the root object level,
we avoid the problem of locking in a particular set of attributes.

I think that all of this fits in quite well with how we've already been
discussing templatizing more of druntime so that it's pay as you go. The
only serious implementation issue that I'm aware of would be the built-in
AAs, since there would be no common base class or interface with opEquals or
toHash (meaning that at least for now, only Object could be put in the
built-in AAs and not classes that aren't derived from Object). But that
would be fixed by templatizing the AA implementation, which is already
something that we've wanted to do. IIRC, Martin Nowak was working on
something along those lines previously, but I don't know where that work
currently stands.

- Jonathan M Davis
May 14 2019
prev sibling next sibling parent Sebastiaan Koppe <mail skoppe.eu> writes:
On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu 
wrote:

 Should we go with a more statically-checked/imposed approach 
 with comparison, or stick with OOP tradition? Ideas welcome.


I am all in on the no-change just-addition static version. And 
thanks for Jonathan for bringing this up.
May 15 2019
prev sibling next sibling parent Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Tuesday, 14 May 2019 at 19:34:12 UTC, Andrei Alexandrescu 
wrote:

 In designing ProtoObject and comparison for equality and 
 ordering, we've assumed all class objects are supposed to be 
 comparable (including ProtoObject themselves). That means code 
 like this should always compile:

 bool fun(C, D)(C x, D y) if (is(C == class) && is(D == class))
 {
    return x < y && x == y;
 }

 That is, any two class objects should be comparable for 
 equality (==, !=) and ordering (<. >, <=, >=). The decision 
 whether comparison actually works for the types involved is 
 deferred to runtime.


 has built-in means for comparison.

 However the question Jonathan M Davis asked got me thinking - 
 perhaps we should break with tradition and opt for a more 
 statically-checked means of comparison. The drawback is that 
 some objects would NOT be comparable, which may surprise some 
 users.

 As a consequence, for example, creating hash tables keyed on 
 certain types will not work. This is not quite unheard of as a 
 type could disable opEquals. Also, by default struct types 
 cannot be compared for ordering - they must define opCmp.

 Should we go with a more statically-checked/imposed approach 
 with comparison, or stick with OOP tradition? Ideas welcome.


The idea is to determine if traditional OOP didn't do it 
statically because they couldn't or because it was for a sound 
semantical reason.

because the language does lack the capability to do it at compile 
time.
I don't have specifically the answer here, but I think that is 
one question that has to be evaluated here.
May 15 2019
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
OK! I finally remembered why we went with the design "any two 
ProtoObjects must be comparable". We should have a way to document this 
stuff, I'd internalized it so much I'd forgotten the reason.

It has to do with the way D implements built-in tables. They use 
indirect calls via TypeInfo classes that essentially require the 
existence of equality and hashing in class objects as virtual functions 
with fixed signatures.

So if we go with a statically-driven solution we lose hashtables keyed 
on any class not derived from Object. That would be awkward but 
hopefully acceptable until we have good containers (which are becoming 
possible only now with copy ctors and the upcoming __RefCounted type in 
druntime).

A possibility to bridge us is to create a wrapper struct:

struct HashKey(T) if(is(T == class)) {
     private T payload;
     bool opEquals(HashKey rhs) { ... }
     size_t toHash() { ... }
     alias payload this;
}

Inside the implementations introspection would be used to figure out how 
type T chose to implement comparison and hashing.

My thinking is, built-in hashtables are overdue for improvement anyway 
so keeping compatibility with them isn't awfully motivating.

Satisfactory or not?
May 15 2019
next sibling parent Adam D. Ruppe <destructionator gmail.com> writes:
On Wednesday, 15 May 2019 at 22:51:11 UTC, Andrei Alexandrescu 
wrote:

 It has to do with the way D implements built-in tables.


Huh, that is a kinda weird implementation, but it makes sense 
now...


 So if we go with a statically-driven solution we lose 
 hashtables keyed on any class not derived from Object.


But I'm OK with that. I virtually never use classes in a hash 
table anyway... and if I did, I think I'd be fine using the 
workaround or just inheriting from Object.

Let's do it.
May 15 2019
prev sibling next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Wednesday, May 15, 2019 4:51:11 PM MDT Andrei Alexandrescu via 
Digitalmars-d wrote:

 OK! I finally remembered why we went with the design "any two
 ProtoObjects must be comparable". We should have a way to document this
 stuff, I'd internalized it so much I'd forgotten the reason.

 It has to do with the way D implements built-in tables. They use
 indirect calls via TypeInfo classes that essentially require the
 existence of equality and hashing in class objects as virtual functions
 with fixed signatures.

 So if we go with a statically-driven solution we lose hashtables keyed
 on any class not derived from Object. That would be awkward but
 hopefully acceptable until we have good containers (which are becoming
 possible only now with copy ctors and the upcoming __RefCounted type in
 druntime).

 A possibility to bridge us is to create a wrapper struct:

 struct HashKey(T) if(is(T == class)) {
      private T payload;
      bool opEquals(HashKey rhs) { ... }
      size_t toHash() { ... }
      alias payload this;
 }

 Inside the implementations introspection would be used to figure out how
 type T chose to implement comparison and hashing.

 My thinking is, built-in hashtables are overdue for improvement anyway
 so keeping compatibility with them isn't awfully motivating.

 Satisfactory or not?


I didn't realize that that was quite what the built-in AAs were doing, but I
was aware that their implementation isn't templatized, so I didn't expect
them to work with any classes not derived from Object without them being
improved. Either way, that does seem like a good workaround, and I certainly
wouldn't want to hurt what we're doing to improve classes because of
internal issues with our AA implementation.

Having built-in AAs is nice, but given all of the problems that we've had
with their implementation over the years, I'm inclined to think that having
them built into the language was ultimately a mistake anyway. We probably
should figure out how to make AA literals work with user-defined types
(without actually creating a built-in AA) at some point here, since that's
the really the only thing that built-in AAs can do that a user-defined hash
table type couldn't.

- Jonathan M Davis
May 15 2019
prev sibling next sibling parent Jesse Phillips <Jesse.K.Phillips+D gmail.com> writes:
On Wednesday, 15 May 2019 at 22:51:11 UTC, Andrei Alexandrescu 
wrote:

 OK! I finally remembered why we went with the design "any two 
 ProtoObjects must be comparable". We should have a way to 
 document this stuff, I'd internalized it so much I'd forgotten 
 the reason.

 It has to do with the way D implements built-in tables. They 
 use indirect calls via TypeInfo classes that essentially 
 require the existence of equality and hashing in class objects 
 as virtual functions with fixed signatures.


Static logic is still preferable from my point of view. I wonder 
how often I use objects as keys.
May 16 2019
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/15/19 11:51 PM, Andrei Alexandrescu wrote:

 OK! I finally remembered why we went with the design "any two 
 ProtoObjects must be comparable". We should have a way to document this 
 stuff, I'd internalized it so much I'd forgotten the reason.
 
 It has to do with the way D implements built-in [hash]tables. They use 
 indirect calls via TypeInfo classes that essentially require the 
 existence of equality and hashing in class objects as virtual functions 
 with fixed signatures.


Yes, but that can be redone. Basically the TypeInfo for an object uses 
Object.toHash expecting the base to be object (and BTW is calling this 
on a specifically non-CONST object, even though keys are supposed to be 
const!)

The TypeInfo_ProtoObject (which would be what we are talking about 
here), can use the same technique as structs -- the compiler writes an 
xtoHash function for it, and puts it in the TypeInfo as a function pointer.


 My thinking is, built-in hashtables are overdue for improvement anyway 
 so keeping compatibility with them isn't awfully motivating.


We need to redo builtin hash tables. As I understand it, the biggest 
hurdle is this feature of builtin hashtables which isn't exactly easy to 
do with our current operator overloading scheme:

int[int[int]] nestedAA;

nestedAA[1][2] = 3; // magically knows to create the intermediate AA if 
it doesn't exist.

-Steve
May 16 2019
next sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Thursday, May 16, 2019 7:53:45 AM MDT Steven Schveighoffer via 
Digitalmars-d wrote:

 On 5/15/19 11:51 PM, Andrei Alexandrescu wrote:

 OK! I finally remembered why we went with the design "any two
 ProtoObjects must be comparable". We should have a way to document this
 stuff, I'd internalized it so much I'd forgotten the reason.

 It has to do with the way D implements built-in [hash]tables. They use
 indirect calls via TypeInfo classes that essentially require the
 existence of equality and hashing in class objects as virtual functions
 with fixed signatures.


 Yes, but that can be redone. Basically the TypeInfo for an object uses
 Object.toHash expecting the base to be object (and BTW is calling this
 on a specifically non-CONST object, even though keys are supposed to be
 const!)


Really, they need to be immtable if you want to guarantee that they don't
change. Having them be const doesn't really buy you anything other than
ensuring that the AA implementation doesn't modify it (and that sort of
thing in druntime has a nasty habit of casting to get around such things).
If the key is not a value type, then other, mutable references to the data
could change it. So, either the key has to be immutable, or you have to rely
on other code not mutating the key via another reference.

- Jonathan M Davis
May 16 2019
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/16/19 3:15 PM, Jonathan M Davis wrote:

 On Thursday, May 16, 2019 7:53:45 AM MDT Steven Schveighoffer via
 Digitalmars-d wrote:

 On 5/15/19 11:51 PM, Andrei Alexandrescu wrote:

 OK! I finally remembered why we went with the design "any two
 ProtoObjects must be comparable". We should have a way to document this
 stuff, I'd internalized it so much I'd forgotten the reason.

 It has to do with the way D implements built-in [hash]tables. They use
 indirect calls via TypeInfo classes that essentially require the
 existence of equality and hashing in class objects as virtual functions
 with fixed signatures.


 Yes, but that can be redone. Basically the TypeInfo for an object uses
 Object.toHash expecting the base to be object (and BTW is calling this
 on a specifically non-CONST object, even though keys are supposed to be
 const!)


 
 Really, they need to be immtable if you want to guarantee that they don't
 change. Having them be const doesn't really buy you anything other than
 ensuring that the AA implementation doesn't modify it (and that sort of
 thing in druntime has a nasty habit of casting to get around such things).


That's beside the point. You shouldn't call a non-const function on 
something that is const *or* immutable. Which is what druntime is 
currently doing.

For most intents and purposes, I think it should be fine to use 
non-const keys, as long as the keys are not modified while they are used 
as keys. You could, for instance, have a key that has some mutable data 
that doesn't affect the hash/equality. The language shouldn't impose 
restrictions that don't make sense for some cases, it just reduces the 
code you can write, even if that code would be perfectly valid.

-Steve
May 16 2019
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Thursday, May 16, 2019 8:41:09 AM MDT Steven Schveighoffer via 
Digitalmars-d wrote:

 On 5/16/19 3:15 PM, Jonathan M Davis wrote:

 On Thursday, May 16, 2019 7:53:45 AM MDT Steven Schveighoffer via

 Digitalmars-d wrote:

 On 5/15/19 11:51 PM, Andrei Alexandrescu wrote:

 OK! I finally remembered why we went with the design "any two
 ProtoObjects must be comparable". We should have a way to document
 this
 stuff, I'd internalized it so much I'd forgotten the reason.

 It has to do with the way D implements built-in [hash]tables. They use
 indirect calls via TypeInfo classes that essentially require the
 existence of equality and hashing in class objects as virtual
 functions
 with fixed signatures.


 Yes, but that can be redone. Basically the TypeInfo for an object uses
 Object.toHash expecting the base to be object (and BTW is calling this
 on a specifically non-CONST object, even though keys are supposed to be
 const!)


 Really, they need to be immtable if you want to guarantee that they
 don't
 change. Having them be const doesn't really buy you anything other than
 ensuring that the AA implementation doesn't modify it (and that sort of
 thing in druntime has a nasty habit of casting to get around such
 things).


 That's beside the point. You shouldn't call a non-const function on
 something that is const *or* immutable. Which is what druntime is
 currently doing.


Well, as I said, druntime has a nasty habit of using casts to work around
problems. The type safety of druntime code in general is likely suspect as a
result. And that really should be fixed.


 For most intents and purposes, I think it should be fine to use
 non-const keys, as long as the keys are not modified while they are used
 as keys. You could, for instance, have a key that has some mutable data
 that doesn't affect the hash/equality. The language shouldn't impose
 restrictions that don't make sense for some cases, it just reduces the
 code you can write, even if that code would be perfectly valid.


I don't really care whether we require that the keys be immutable. My point
was that requiring const makes no sense, because it doesn't guarantee
anything that matters to the AA implementation. Either we require immutable,
or we don't care and let the user shoot themselves in the foot if they use a
mutable object and then mutate it, because requiring immutable is too
restrictive. Either way, I completely agree that druntime shouldn't be
casting away const.

- Jonathan M Davis
May 16 2019
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, May 16, 2019 at 09:11:48AM -0600, Jonathan M Davis via Digitalmars-d
wrote:

 On Thursday, May 16, 2019 8:41:09 AM MDT Steven Schveighoffer via 
 Digitalmars-d wrote:


[...]

 For most intents and purposes, I think it should be fine to use
 non-const keys, as long as the keys are not modified while they are
 used as keys. You could, for instance, have a key that has some
 mutable data that doesn't affect the hash/equality. The language
 shouldn't impose restrictions that don't make sense for some cases,
 it just reduces the code you can write, even if that code would be
 perfectly valid.




That's a good point.  So really, what matters is that once a key is
inserted into the AA, there must be no changes visible through .opEquals
(and possibly .opCmp) and .toHash.

Although TBH, that smells like bending over backwards to do something
that's ill-advised to begin with. If you're writing a custom type as an
AA key, why would you deliberately write it so that it has external
mutators and extra state?  If only part of the object is actually the
effective key, then it should be factored out into an immutable object
and *that* should be used as key instead of the entire object.



 I don't really care whether we require that the keys be immutable. My
 point was that requiring const makes no sense, because it doesn't
 guarantee anything that matters to the AA implementation. Either we
 require immutable, or we don't care and let the user shoot themselves
 in the foot if they use a mutable object and then mutate it, because
 requiring immutable is too restrictive.


At the very least I'd appreciate a warning that a non-immutable key is
being used to create AA entries.  There have been a number of bugs filed
in the past, caused by "ghost" entries in the AA that exist when you
iterate but otherwise are inaccessible, because their keys have mutated
and no longer match the stored hash value in the AA.



 Either way, I completely agree that druntime shouldn't be casting away
 const.


[...]

Yeah, that has the potential of blowing up if we ever implement
compile-time AA literals that get put into ROM. (Very distant
possibility, though, granted.)


T

-- 
Latin's a dead language, as dead as can be; it killed off all the Romans, and
now it's killing me! -- Schoolboy
May 16 2019
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/16/19 5:24 PM, H. S. Teoh wrote:

 On Thu, May 16, 2019 at 09:11:48AM -0600, Jonathan M Davis via Digitalmars-d
wrote:

 On Thursday, May 16, 2019 8:41:09 AM MDT Steven Schveighoffer via
 Digitalmars-d wrote:


 [...]

 For most intents and purposes, I think it should be fine to use
 non-const keys, as long as the keys are not modified while they are
 used as keys. You could, for instance, have a key that has some
 mutable data that doesn't affect the hash/equality. The language
 shouldn't impose restrictions that don't make sense for some cases,
 it just reduces the code you can write, even if that code would be
 perfectly valid.




 
 That's a good point.  So really, what matters is that once a key is
 inserted into the AA, there must be no changes visible through .opEquals
 (and possibly .opCmp) and .toHash.


Since we went to non-tree-based buckets, we have not required opCmp 
anymore. That requirement is not going to come back.


 Although TBH, that smells like bending over backwards to do something
 that's ill-advised to begin with. If you're writing a custom type as an
 AA key, why would you deliberately write it so that it has external
 mutators and extra state?  If only part of the object is actually the
 effective key, then it should be factored out into an immutable object
 and *that* should be used as key instead of the entire object.


Sometimes the custom type isn't really meant ONLY to be a hash key. 
Sometimes you use an object as one thing somewhere, and a key somewhere 
else. Having to painstakingly separate the immutable and mutable parts 
makes things unpleasant. Especially if the immutable parts are 
semantically immutable, and not actually marked immutable (for obvious 
reasons). In other words, we live in the real world ;)

I'm pretty sure in the past I had a good use case for this, but it was 
way in the past (like over 10 years ago), and it was with Tango. And 
dcollections.

In any case, I agree requiring const does zero to guarantee anything. My 
solution just differs from yours in that I think you should not require 
any modifiers to make it work. Don't restrict the developer, you don't 
know what he is doing, or why he needs to do it that way. Sometimes the 
contract between the library and user code cannot be expressed in the 
type system.

-Steve
May 16 2019
prev sibling parent Mike Franklin <slavo5150 yahoo.com> writes:
On Thursday, 16 May 2019 at 14:41:09 UTC, Steven Schveighoffer 
wrote:


 That's beside the point. You shouldn't call a non-const 
 function on something that is const *or* immutable. Which is 
 what druntime is currently doing.


I'd be interested in knowing more about this.  Would you be 
willing to show me the specific function where this is occurring?

I've been working over the past few years to learn how to convert 
many runtime hooks to templates, and in that process I've 
discovered that the runtime hooks are not abiding by their 
contracts.

The runtime hooks are added to the binary in e2ir.d which is 
after the semantic phase, so purity, safety, throwability, etc... 
is not enforced. For example, code in a `pure` function is 
lowered to an impure runtime hook, and the compiler doesn't catch 
it. Is that what's going on here as well?

Mike
May 16 2019
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, May 16, 2019 at 08:15:07AM -0600, Jonathan M Davis via Digitalmars-d
wrote:

 On Thursday, May 16, 2019 7:53:45 AM MDT Steven Schveighoffer via 
 Digitalmars-d wrote:


[...]

 Yes, but that can be redone. Basically the TypeInfo for an object
 uses Object.toHash expecting the base to be object (and BTW is
 calling this on a specifically non-CONST object, even though keys
 are supposed to be const!)


 
 Really, they need to be immtable if you want to guarantee that they
 don't change. Having them be const doesn't really buy you anything
 other than ensuring that the AA implementation doesn't modify it


[...]

Yes, AA keys must be immutable. The current const requirement guarantees
nothing.

There is more to this, though. Lookups using non-immutable (even
mutable) keys ought to be allowed, since you only need to compare keys
in that case. But assignment must require immutable. IOW:

	// Key is any type that contains references
	Key mk;
	const Key ck;
	immutable Key ik;

	//int[Key] aa; // not allowed, require immutable
	//int[const(Key)] aa; // not allowed, require immutable
	int[immutable(Key)] aa; // OK
	// Of course, to reduce verbosity we could simply define V[Key]
	// to mean V[immutable(Key)] implicitly.

	//aa[mk] = 1;	// not allowed, require immutable
	//aa[ck] = 1;	// not allowed, require immutable
	aa[ik] = 1;	// OK

	int i;
	i = aa[mk]; // OK: lookup only
	i = aa[ck]; // OK: lookup only
	i = aa[ik]; // OK

	i = aa.get(mk, 0); // OK: lookup only
	i = aa.get(ck, 0); // OK: lookup only
	i = aa.get(ik, 0); // OK

	int* p;
	p = mk in aa;	// OK: lookup only
	p = ck in aa;	// OK: lookup only
	p = ik in aa;	// OK

	aa.remove(mk); // OK: lookup only
	aa.remove(ck); // OK: lookup only
	aa.remove(ik); // OK


T

-- 
Let's not fight disease by killing the patient. -- Sean 'Shaleh' Perry
May 16 2019
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/16/19 9:53 AM, Steven Schveighoffer wrote:

 On 5/15/19 11:51 PM, Andrei Alexandrescu wrote:

 OK! I finally remembered why we went with the design "any two 
 ProtoObjects must be comparable". We should have a way to document 
 this stuff, I'd internalized it so much I'd forgotten the reason.

 It has to do with the way D implements built-in [hash]tables. They use 
 indirect calls via TypeInfo classes that essentially require the 
 existence of equality and hashing in class objects as virtual 
 functions with fixed signatures.


 
 Yes, but that can be redone. Basically the TypeInfo for an object uses 
 Object.toHash expecting the base to be object (and BTW is calling this 
 on a specifically non-CONST object, even though keys are supposed to be 
 const!)
 
 The TypeInfo_ProtoObject (which would be what we are talking about 
 here), can use the same technique as structs -- the compiler writes an 
 xtoHash function for it, and puts it in the TypeInfo as a function pointer.
 

 My thinking is, built-in hashtables are overdue for improvement anyway 
 so keeping compatibility with them isn't awfully motivating.


 
 We need to redo builtin hash tables. As I understand it, the biggest 
 hurdle is this feature of builtin hashtables which isn't exactly easy to 
 do with our current operator overloading scheme:
 
 int[int[int]] nestedAA;
 
 nestedAA[1][2] = 3; // magically knows to create the intermediate AA if 
 it doesn't exist.


Good reminder. Wasn't also the magical rebinding of immutable keys?

string[immutable int[]] t;
foreach (k, v; t) { ... }

Or/also something having to do with fixed-size arrays as keys?

string[immutable int[4]] t;
foreach (k, v; t) { ... }

We should document this institutional memory in a wiki somewhere.
May 16 2019
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2019-05-16 00:51, Andrei Alexandrescu wrote:


 So if we go with a statically-driven solution we lose hashtables keyed 
 on any class not derived from Object. That would be awkward but 
 hopefully acceptable until we have good containers (which are becoming 
 possible only now with copy ctors and the upcoming __RefCounted type in 
 druntime).


Can we use both?

-- 
/Jacob Carlborg
May 16 2019