[swift-evolution] [pitch] Comparison Reform

[Jonathan Hull]

As I am thinking about it more, this means that for == and <

NaN == NaN
-0 == +0
+Inf < NaN

Since this would break from IEEE, I think we should also consider taking the opportunity to make == and < work with a default tolerance.  That is, 'a == b' would check that (a - b) < epsilon for some reasonable choice of epsilon that works for common usage.  I know this would make the hash function harder to write, but I think it is worthwhile.

Then, as I mentioned before, people who need strict IEEE conformance would explicitly declare that need by using 'compare(with: other, using: .IEEE)' or whatever we want to call that metric.  We can even provide metrics for different IEEE levels, if desired.

We could also provide a function ‘tolerance(_:Self) -> Comparable.Metric’ on FloatingPoint which returns a comparison metric that defines equality as (a - b) < tolerance, for those who want to specify a specific tolerance for their use-case/algorithm...

Thanks,
Jon



> On Apr 23, 2017, at 7:18 AM, Jonathan Hull via swift-evolution <swift-evolution at swift.org> wrote:
> 
> There is one more option which hasn’t really been considered:
> 
> • == and != are tied to the Equatable protocol, which is essentially the == operation.
> •  <, <=, >, >= are tied to the Comparable protocol (which is kept the same except for minor changes/additions listed below)
> • Hashable still requires Equatable
> • There is a new ComparisonMetric concept which lets an algorithm specify exactly how the comparison is done (see below)
> 
> 
> Tl;dr: There are different definitions of ‘comparison’ which make sense in different domains… so let’s make it explicit so it doesn’t surprise anyone.
> 
> The question then becomes, which metric should be the default (i.e. the one defined by ‘<‘ and ‘==‘), and the answer is: the one which lets us use floats/doubles in dictionaries and sets.  People and algorithms which need full IEEE correctness can use a different metric which specifically guarantees it.  They can even build their own metric if needed.
> 
> 
> ====The Design====
> // (Note: I wrote this code in mail, so it may not compile)
> 
> 
> //This defines the result of a comparison. It would ideally be nested in the protocol below if that becomes possible.
> enum ComparisonResult : Int {
> 	case ascending = -1
> 	case equal = 0
> 	case descending = 1
> }
> 
> protocol Comparable {
> 	typealias Metric = (Self, Self) -> ComparisonResult  //Give ourselves an easy way to refer to this function type
> 
> 	var defaultMetric: Metric
> 	static func <(lhs: Self, rhs: Self) -> Bool
> }
> 
> extension Comparable {
> 	//Not shown: We would define <=, etc… plus ≤,≥,and ≠  (because, hey, it is my proposal)
> 
> 	func compare(with other: Self, using metric: Metric) -> ComparisonResult {
> 		return metric(self, other)
> 	} 
> 
> 	func compare(with other: Self) -> ComparisonResult {
> 		return self.defaultMetric(self, other)
> 	}
> 
> 	static func <=> (lhs: Self, rhs: Self) -> Int {
> 		return self.defaultMetric(lhs, rhs).rawValue
> 	}
> 
> 	var defaultMetric: Metric {
> 		return  { lhs, rhs in
> 			if lhs == rhs {
> 				return .equal
> 			} else if lhs < rhs {
> 				return .ascending
> 			}
> 			return .descending
> 		}
> 	}
> }
> 
> ============
> 
> Then for Double, we would make a second metric for IEEE compliant (or multiple for different levels)
> 
> extension Double : Comparable {
> 
> 	static func < (lhs: Self, rhs: Self) -> Bool {
> 		//define using best for dictionaries / sets / layman understanding
> 	}
> 
> 	static func == (lhs: Self, rhs: Self) -> Bool {
> 		//define using best for dictionaries / sets / layman understanding
> 	}
> 
> 	static var IEEEcompare:Comparable.Metric {
> 		//return function here that does full IEEE comparison 
> 	}
> 
> }
> 
> Then we can call ‘myDouble.compare(with: otherDouble, using: .IEEEcompare)’ when needed.
> 
> 
> Thanks,
> Jon
> 
> 
> 
>> On Apr 22, 2017, at 9:58 PM, Chris Lattner via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> On Apr 22, 2017, at 6:06 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>> but my quick reaction to `&==` is that it would make me quite nervous to have `==` not bound to 754-equals as it is in essentially every other language. In particular, I worry about the risk of people porting numerical code that depends on isnan(x) <—> !(x < y) in non-obvious ways that they are unlikely to test. I’ll try to follow up with more detailed thoughts tomorrow.
>>> 
>>> Indeed, it makes me a little nervous too. That said, `==` being either bound or not bound to 754 depending on the context is what makes me even more nervous.
>>> 
>>> I was once adamantly against a new spelling for `==`, but on reconsideration it's clear to me that few if any numerical recipes can be ported verbatim from C-like languages and we should probably not encourage people to do so. Already, `+` needs to be rewritten as `&+`, `<<` probably should be rewritten as `&<<` (I still haven't had enough time to think about this), and the bitwise operators have differing precedences that require careful proofreading.
>> 
>> 
>> I haven’t been following this proposal or discussion closely, but it seems to me that there are a few workable approaches with different tradeoffs:
>> 
>> 1. The strictly correct but user hostile approach:
>> 
>> * == and != are tied to the Equatable protocol, which is essentially the == operation.
>> * <, <=, >, >= are tied to the Comparable protocol, which is essentially the <=> operation.
>> * Hashable doesn’t require equatable, it requires a related StrictlyEquatable protocol.
>> * StrictlyEquatable refines Equatable (with no other requirements, it is just a marker protocol), in which case FP types can’t conform to it, and thus can’t participate as dictionary keys
>> 
>> => This approach sucks because you can’t have Set<Float>, or Dictionary<Float, String>.
>> 
>> 2. The strictly correct but somewhat user hostile approach:
>> 
>> * == and != are tied to the Equatable protocol, which is essentially the == operation.
>> * <, <=, >, >= are tied to the Comparable protocol, which is essentially the <=> operation.
>> * Hashable doesn’t require equatable, it requires a related StrictlyEquatable protocol.
>> * StrictlyEquatable doesn’t refine Equatable: it has a different requirement, and FP types can therefore implement both Equatable and StrictlyEquatable.
>> 
>> => This approach is suboptimal because implementing your own type requires you to implement the <=> operation, as well as the StrictlyEquatable protocol, both.
>> 
>> 3. The user friendly but incorrect model:
>> 
>> * == and != are tied to the Equatable protocol, which is essentially the == operation.
>> * <, <=, >, >= are tied to the Comparable protocol, which is essentially the <=> operation.
>> * Hashable is defined in terms of Equatable.
>> 
>> => This is easy (types just have to define <=>), but fails for FP types.
>> 
>> 
>> I don’t think that this proposal is acceptable as written.  I think it is really bad that abstracting a concrete algorithm would change its behavior so substantially.  I don’t care about SNaNs, but I do care about the difference between +0/-1 and secondarily that of NaN handling.  It seems really bad that generalizing something like:
>> 
>> func doThing(a : Double, b : Double) -> Bool {
>>  ….
>>  return a != b
>> }
>> 
>> to:
>> 
>> func doThing<T : FloatingPoint> (a : T, b : T) -> Bool {
>>  ….
>>  return a != b
>> }
>> 
>> would change behavior (e.g. when a is -0.0 and b is +0.0).   Likewise, "T : Equatable".
>> 
>> -Chris
>> 
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution