www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fixing opEquals and opCmp

reply Fool <fool dlang.org> writes:
Is there any interest in fixing opEquals and opCmp in the 
spirit(*) of [1]?

Translating the basic idea into the D world would mean:
  - Drop opEquals
  - Encode the type of comparison in the return type of opCmp
  - Adapt lowering

Why?
  - Simplicity: there is always only one function that needs to be 
implemented;
  - Consistency: implementation at a single place makes it more 
difficult to get it wrong;
  - Expressivity: through the return type implementors can 
unambiguously specify the properties of comparison relations 
(Equivalence, Equality, PartialOrdering, LinearOrdering, etc.) 
and algorithms can more precisely specify their requirements 
(e.g. general sorting requires a weak ordering whereas 
topological sorting requires a preorder, only);

[1] Herb Sutter: Consistent comparison, P0515 R0, 2017-02-05
     URL 
http://open-std.org/JTC1/SC22/WG21/docs/papers/2017/p0515r0.pdf

(*) Some aspects of the proposal are unsound but those can be 
easily fixed.
May 13 2017
next sibling parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Saturday, 13 May 2017 at 12:11:49 UTC, Fool wrote:

 Is there any interest in fixing opEquals and opCmp in the 
 spirit(*) of [1]?

 Translating the basic idea into the D world would mean:
  - Drop opEquals
  - Encode the type of comparison in the return type of opCmp
  - Adapt lowering

 Why?
  - Simplicity: there is always only one function that needs to 
 be implemented;
  - Consistency: implementation at a single place makes it more 
 difficult to get it wrong;
  - Expressivity: through the return type implementors can 
 unambiguously specify the properties of comparison relations 
 (Equivalence, Equality, PartialOrdering, LinearOrdering, etc.) 
 and algorithms can more precisely specify their requirements 
 (e.g. general sorting requires a weak ordering whereas 
 topological sorting requires a preorder, only);

 [1] Herb Sutter: Consistent comparison, P0515 R0, 2017-02-05
     URL 
 http://open-std.org/JTC1/SC22/WG21/docs/papers/2017/p0515r0.pdf

 (*) Some aspects of the proposal are unsound but those can be 
 easily fixed.


For most types equality exists (i.e. are all members equal?), but 
ordering is nonsensical.

to answer your why questions:
1) see above, we're still doing better than C++ (although in the 
contexts of DLSs individual operator overloading is useful.
2) see 1. you need only define both if opEquals is a requirement 
for performance. defining opCmp suffices for (in)equality. and 
you don't define opCmp unless your type has sensible ordering.
3) you can do that already. w.r.t sort you pass a predicate 
(defaulting to "less") for which ordering is assumed to exist, if 
it doesn't then you get a partition according to that predicate.
May 13 2017
parent reply Fool <fool dlang.org> writes:
On Saturday, 13 May 2017 at 12:53:33 UTC, Nicholas Wilson wrote:

 For most types equality exists (i.e. are all members equal?), 
 but ordering is nonsensical.


How does this relate to what I wrote?

If you want to support equality only, implement opCmp with return 
type Equality. (In Herb's proposal uses the spaceship operator 
<=> instead of opCmp and strong_equality for Equality.)



 to answer your why questions:
 1) see above, we're still doing better than C++ (although in 
 the contexts of DLSs individual operator overloading is useful.


It's not about C++, it's about D.

If Herb's proposal is accepted (after being corrected) then - 
indeed - C++ will be doing better than D. ;-)



 2) see 1. you need only define both if opEquals is a 
 requirement for performance. defining opCmp suffices for 
 (in)equality. and you don't define opCmp unless your type has 
 sensible ordering.


What I was saying is: defining opCmp implies a definition of 
equivalence which now needs to be specified redundantly in 
opEquals. The developer now is responsible to ensure consistency 
between opCmp and opEquals.



 3) you can do that already. w.r.t sort you pass a predicate 
 (defaulting to "less") for which ordering is assumed to exist, 
 if it doesn't then you get a partition according to that 
 predicate.


Another misunderstanding. Currently, there is no means to express 
that 'less' models a partial order vs. a linear order.
May 13 2017
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sat, May 13, 2017 at 01:21:12PM +0000, Fool via Digitalmars-d wrote:

 On Saturday, 13 May 2017 at 12:53:33 UTC, Nicholas Wilson wrote:


[...]

 3) you can do that already. w.r.t sort you pass a predicate
 (defaulting to "less") for which ordering is assumed to exist, if it
 doesn't then you get a partition according to that predicate.


 
 Another misunderstanding. Currently, there is no means to express that
 'less' models a partial order vs. a linear order.


Wrong.  Andrei specifically stated before that opCmp may model a partial
order, i.e., returning 0 may indicate "not comparable" rather than
"equal".  And this is why opEquals is necessary: to distinguish between
"not comparable" and "equal".


T

-- 
A computer doesn't mind if its programs are put to purposes that don't match
their names. -- D. Knuth
May 13 2017
next sibling parent Fool <fool dlang.org> writes:
On Saturday, 13 May 2017 at 14:17:24 UTC, H. S. Teoh wrote:

 Another misunderstanding. Currently, there is no means to 
 express that 'less' models a partial order vs. a linear order.


 Wrong.  Andrei specifically stated before that opCmp may model 
 a partial order, i.e., returning 0 may indicate "not 
 comparable" rather than "equal".  And this is why opEquals is 
 necessary: to distinguish between "not comparable" and "equal".


How is this reflected in the interface?
May 13 2017
prev sibling next sibling parent reply Fool <fool dlang.org> writes:
On Saturday, 13 May 2017 at 14:17:24 UTC, H. S. Teoh wrote:

 Andrei specifically stated before that opCmp may model a 
 partial order, i.e., returning 0 may indicate "not comparable" 
 rather than "equal".


Well, that's unsound.

Example: 'is (proper) subset of'

Given the sets a:= {1} and b:= {2}, we have

  a is not a proper subset of b;
  b is not a proper subset of a;

If a.opCmp(b) returns 0 in this situation then, due to the rewrite

  a <= b   a.opCmp(b) <= 0,

we have:

  a is a subset of b
May 13 2017
parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Saturday, 13 May 2017 at 15:00:27 UTC, Fool wrote:

 On Saturday, 13 May 2017 at 14:17:24 UTC, H. S. Teoh wrote:

 Andrei specifically stated before that opCmp may model a 
 partial order, i.e., returning 0 may indicate "not comparable" 
 rather than "equal".


 Well, that's unsound.

 Example: 'is (proper) subset of'

 Given the sets a:= {1} and b:= {2}, we have

  a is not a proper subset of b;
  b is not a proper subset of a;

 If a.opCmp(b) returns 0 in this situation then, due to the 
 rewrite

  a <= b   a.opCmp(b) <= 0,

 we have:

  a is a subset of b


In this case, typeof(a) should not be the same as typeof(b), 
which can be handled correctly by opCmp.
May 13 2017
parent Fool <fool dlang.org> writes:
On Saturday, 13 May 2017 at 15:05:02 UTC, Stanislav Blinov wrote:

 In this case, typeof(a) should not be the same as typeof(b), 
 which can be handled correctly by opCmp.


Now you are trolling me. ;-)

Obviously a and b share the same type. They are sets.
May 13 2017
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 13.05.2017 16:17, H. S. Teoh via Digitalmars-d wrote:

 On Sat, May 13, 2017 at 01:21:12PM +0000, Fool via Digitalmars-d wrote:

 On Saturday, 13 May 2017 at 12:53:33 UTC, Nicholas Wilson wrote:


 [...]

 3) you can do that already. w.r.t sort you pass a predicate
 (defaulting to "less") for which ordering is assumed to exist, if it
 doesn't then you get a partition according to that predicate.


 Another misunderstanding. Currently, there is no means to express that
 'less' models a partial order vs. a linear order.


 Wrong.  Andrei specifically stated before that opCmp may model a partial
 order, i.e., returning 0 may indicate "not comparable" rather than
 "equal".  And this is why opEquals is necessary: to distinguish between
 "not comparable" and "equal".


 T


I can't seem to find the post you are referring to but IIRC it was 
immediately destroyed completely.
May 13 2017
next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Saturday, May 13, 2017 20:52:48 Timon Gehr via Digitalmars-d wrote:

 On 13.05.2017 16:17, H. S. Teoh via Digitalmars-d wrote:

 On Sat, May 13, 2017 at 01:21:12PM +0000, Fool via Digitalmars-d wrote:

 On Saturday, 13 May 2017 at 12:53:33 UTC, Nicholas Wilson wrote:


 [...]


 3) you can do that already. w.r.t sort you pass a predicate
 (defaulting to "less") for which ordering is assumed to exist, if it
 doesn't then you get a partition according to that predicate.


 Another misunderstanding. Currently, there is no means to express that
 'less' models a partial order vs. a linear order.


 Wrong.  Andrei specifically stated before that opCmp may model a partial
 order, i.e., returning 0 may indicate "not comparable" rather than
 "equal".  And this is why opEquals is necessary: to distinguish between
 "not comparable" and "equal".


 T


 I can't seem to find the post you are referring to but IIRC it was
 immediately destroyed completely.


I remember that coming up and a number of us (most of us?) thinking that
what Andrei was suggesting was a bad idea, but I don't recall if there was
ever an agreement about it. I'm terrible at finding old threads though, so I
don't know where the thread on that is either.

With opEquals and opCmp (and operator overloading in general) are designed,
I wouldn't expect it to be reasonable for opCmp == 0 to be different from
opEquals == true, and opCmp != 0 equal to opEquals == false. They're
basically supposed to be model how it works with integers (though floating
point values do muck with it a bit thanks to NaN).

- Jonathan M Davis
May 13 2017
prev sibling parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Saturday, 13 May 2017 at 18:52:48 UTC, Timon Gehr wrote:

 I can't seem to find the post you are referring to but IIRC it 
 was immediately destroyed completely.


It was probably in this thread:

http://forum.dlang.org/post/dhrtitehdkcgnlmukufb forum.dlang.org

And as one can see generic support for comparison relations is 
non-trivial.
May 14 2017
prev sibling parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Saturday, 13 May 2017 at 14:17:24 UTC, H. S. Teoh wrote:

 Andrei specifically stated before that opCmp may model a 
 partial order, i.e., returning 0 may indicate "not comparable" 
 rather than "equal".  And this is why opEquals is necessary: to 
 distinguish between "not comparable" and "equal".


As others have pointed out, that seems wrong. However, returning 
float.nan does make a bit of sense. Given a nan return value, a 
<= b and a >= b will both be false.
May 13 2017
prev sibling parent reply Fool <fool dlang.org> writes:
I apologize for even thinking about the possibility that 
something could be wrong and might require a fix.

Have a good time!
May 13 2017
parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Saturday, 13 May 2017 at 15:31:40 UTC, Fool wrote:

 I apologize for even thinking about the possibility that 
 something could be wrong and might require a fix.

 Have a good time!


A "discussion" 3 hours long, with 62.5% of posts in it being your 
own. One can understand how you'd give up after such a challenge.
You do realize that now it looks more like "implement it 
immediately or I ragequit!" kind of thing?
May 13 2017