Thread overview | ||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
January 12, 2016 opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Background: Some important properties for binary relations on sets that are somewhat similar to the normal ≤/≥ on the real numbers or integers are: a ≤ a (reflexivity); if a ≤ b and b ≤ a, then a = b (antisymmetry); if a ≤ b and b ≤ c, then a ≤ c (transitivity); a ≤ b or b ≤ a (totality, implies reflexivity); Definitions: A preorder obeys reflexivity and transitivity. A partial order obeys reflexivity, transitivity and antisymmetry. A total order obeys transitivity, antisymmetry and totality. A total preorder obeys transitivity and totality but not antisymmetry Examples: Arrays ordered by length, vectors ordered by euclidian length, complex numbers ordered by absolute value etc. are all total preorders. Integers with ≤ or ≥ form a total order. float/double/real obey antisymmetry and transitivity but not reflexivity or totality. Implementations in D: Total order: opCmp with "consistent" opEquals to enforce antisymmetry. Total preorder: opCmp with "inconsistent" opEquals to break antisymmetry. Preorder or partial order: not possible in D, opCmp insists on totality. Antisymmetry and transitivity but not reflexivity or totality, e.g. custom float: not possible in D, opCmp insists on totality (no way for opCmp to signify nan comparisons, either with nan (reflexivity) or others (totality & reflexivity)). Solutions to the above problems: 1) opCmp - or some extended, renamed version of it - needs 4 return values: greater, lesser, equal and neither/unequal/incomparible. This would be the value that is returned when e.g. either side is nan. or, less intrusively and more (runtime) efficiently: 2) Introduce a new special function `bool opCmpOrdered(T rhs)` that, if defined, is used to shortcircuit a comparison. Any previous lowering to `a.opCmp(b) [<>]=? 0` (as in https://dlang.org/spec/operatoroverloading.html#compare) would now lower to `a.opCmpOrdered(b) && a.opCmp(b) [<>]=? 0`. E.g. `a >= b` becomes `a.opCmpOrdered(b) && a.opCmp(b) >= 0`. If opCmpOrdered isn't defined the lowering is unchanged from before (or opCmpOrdered defaults to true, same thing...). Bigger example: a custom float type struct MyFloat { // ... bool isNaN() { /* ... */ } bool opCmpOrdered(MyFloat rhs) { if (this.isNaN || rhs.isNaN) return false; else return true; } int opCmp(MyFloat rhs) { //can assume neither are nan /* ... */ } bool opEquals(MyFloat rhs) { if (this.isNaN || rhs.isNaN) return false; else /* ... */ } } unittest { MyFloat a, b; // has .init as nan, of course :) static allFail(MyFloat a, MyFloat b) { // all of these should short-circuit because // opCmpOrdered will return false assert(!(a==b)); assert(!(a<b)); assert(!(a<=b)); assert(!(a>b)); assert(!(a>=b)); } allFail(a, b); a = 3; allFail(a, b); b = 4; assert(a!=b); assert(a<b); assert(a<=b); assert(!(a>b)); assert(!(a>=b)); a = 4; assert(a==b); assert(!(a<b)); assert(a<=b); assert(!(a>b)); assert(a>=b); } P.S. This is not just about floats! It is also very useful for making types that represent missing data (e.g. encapsulating using int.min for a missing value). I can only come up with strained examples for preorders and partial orders that I would want people using < and > for, so I won't speak of them here. P.P.S. Note that I am *not* trying to extend D's operator overloading to make > and < usable for arbitrary binary relations, like in C++. This small change is strictly within the realm of what <, > and = are already used for (in D, with floats). I'm convinced that if you wouldn't read it out loud as something like "less/fewer/smaller than" or "greater/more/bigger than", you shouldn't be using < or >, you should name a separate function; I don't think this proposal encourages violating that principle. |
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | On Tuesday, 12 January 2016 at 18:27:15 UTC, John Colvin wrote: > Background: > Some important properties for binary relations on sets that are somewhat similar to the normal ≤/≥ on the real numbers or integers are: > > [...] http://dlang.org/phobos/std_math.html#.cmp ? --Ilya |
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ilya Yaroshenko | On Tuesday, 12 January 2016 at 18:36:32 UTC, Ilya Yaroshenko wrote:
> On Tuesday, 12 January 2016 at 18:27:15 UTC, John Colvin wrote:
>> Background:
>> Some important properties for binary relations on sets that are somewhat similar to the normal ≤/≥ on the real numbers or integers are:
>>
>> [...]
>
> http://dlang.org/phobos/std_math.html#.cmp ? --Ilya
That doesn't solve the whole problem, because std.math.cmp isn't the default comparator you can't use a totally ordered float type as a drop-in for the builtin float types.
A more interesting question it bring up though is:
does the approach of imposing a (somewhat arbitrary) total order work for other types where you would normally use a less "strict" ordering? Does it work well for missing data representations?
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | On 01/12/2016 01:27 PM, John Colvin wrote:
> Preorder or partial order: not possible in D, opCmp insists on totality.
The way I look at it, a partial order would implement opCmp and opEqual such that a < b, b < a, and a == b are simultaneously false for unordered objects. Would that float your boat? -- Andrei
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | On Tuesday, 12 January 2016 at 18:27:15 UTC, John Colvin wrote:
> P.S. This is not just about floats!
This also affects any custom numeric type which should be comparable with float - while working on a checked integer type for Phobos, one of the (minor) problems I have run into is that it is impossible to reproduce the comparison behaviour of the built-in integers with respect to floating-point values - even though the latest version of my checked integer type actually has no "NaN" state of its own.
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Tuesday, 12 January 2016 at 19:00:11 UTC, Andrei Alexandrescu wrote:
> On 01/12/2016 01:27 PM, John Colvin wrote:
>> Preorder or partial order: not possible in D, opCmp insists on totality.
>
> The way I look at it, a partial order would implement opCmp and opEqual such that a < b, b < a, and a == b are simultaneously false for unordered objects. Would that float your boat? -- Andrei
a<=b and b<=a must also be false. That would work for a partial order, yes. Unfortunately, that's not possible with the current opCmp design, hence my 2 suggestions for improvements (I'm pretty sure the second one is better).
The key thing is to have a design that doesn't enforce totality.
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | On Tuesday, 12 January 2016 at 19:13:29 UTC, John Colvin wrote:
> On Tuesday, 12 January 2016 at 19:00:11 UTC, Andrei Alexandrescu wrote:
>> On 01/12/2016 01:27 PM, John Colvin wrote:
>>> Preorder or partial order: not possible in D, opCmp insists on totality.
>>
>> The way I look at it, a partial order would implement opCmp and opEqual such that a < b, b < a, and a == b are simultaneously false for unordered objects. Would that float your boat? -- Andrei
>
> a<=b and b<=a must also be false. That would work for a partial order, yes. Unfortunately, that's not possible with the current opCmp design, hence my 2 suggestions for improvements (I'm pretty sure the second one is better).
>
> The key thing is to have a design that doesn't enforce totality.
s/totality/reflexivity
which also implies it can't force totality. Note that a non-reflexive <= doesn't imply anything about ==.
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | On 01/12/2016 02:13 PM, John Colvin wrote:
> a<=b and b<=a must also be false.
Would the advice "Only use < and == for partially-ordered data" work? -- Andrei
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | On Tuesday, 12 January 2016 at 19:21:47 UTC, John Colvin wrote:
> Note that a non-reflexive <= doesn't imply anything about ==.
Non-reflexive '<=' does not make any sense at all.
|
January 12, 2016 Re: opCmp, [partial/total/pre]orders, custom floating point types etc. | ||||
---|---|---|---|---|
| ||||
Posted in reply to Fool | On Tuesday, 12 January 2016 at 19:44:18 UTC, Fool wrote:
> On Tuesday, 12 January 2016 at 19:21:47 UTC, John Colvin wrote:
>> Note that a non-reflexive <= doesn't imply anything about ==.
>
> Non-reflexive '<=' does not make any sense at all.
It might be a bit of a mess, agreed, but nonetheless:
assert(!(float.nan <= float.nan));
|
Copyright © 1999-2021 by the D Language Foundation