[swift-dev] Rationalizing FloatingPoint conformance to Equatable

[Ben Cohen]

> On Oct 24, 2017, at 6:48 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
> 
>> On Tue, Oct 24, 2017 at 1:55 PM, Ben Cohen <ben_cohen at apple.com> wrote:
>> 
>> 
>>> On Oct 19, 2017, at 4:29 PM, Xiaodi Wu via swift-dev <swift-dev at swift.org> wrote:
>>> 
>>> Differing behavior in generic and concrete contexts is simply too subtle to be understandable to the reader.
>> 
>> Hardly more subtle then the current “Equatable works like this, with these strong guarantees. Oh, except for some cases it doesn’t, in which case ¯\_(ツ)_/¯”
> 
> I'm not saying that the status quo is a superior alternative.
> 
> However, one option is to _weaken_ the guarantees of Equatable such that it guarantees only partial equivalence for `==`. From the perspective of documented semantics, it's not subtle at all but a giant hammer of a change. However, from an actual what-does-the-implementation-do standpoint, it would be acknowledging what is already true. Only code that is already broken when used with floating-point values would become formally "incorrect" in the sense of relying on semantics that are then no longer guaranteed.
> 
> Such a solution would avoid, as you might say, perpetuating the ¯\_(ツ)_/¯ approach to floating point.
> 
>> I realize that Comparable admits an exception for FP. This is, IMO, a serious mistake and needs to be reversed. Equatable has no such exception and rightly so.
>> 
>> The clearest demonstrations of how flawed this approach is can be found in the Standard Library. You can throw a brick at it and hit an example of something that’s broken by the presence of .nan: random sort orders, == implementations that differ based on the identify of the buffer,
> 
> In my view, if a sort algorithm cannot accommodate NaN, it's entirely acceptable to trap on NaN--and that is a trivial change.

I think this would be user-hostile. This isn’t like out-of-bounds subscript where it’s just not possible to reasonably proceed. NaNs crop up and people don’t expect them to trap when you sort – they expect them to sort to one end, like in Excel.

> After all, NaN is unordered with respect to everything and one cannot sort the unsortable. And, as shown, the `Array.==` implementation is trivially fixable. The entire standard library can be made NaN-safe in like manner.
>  

My point was, it’s not about what we can do in the standard library. The std lib only has a handful of methods and sure, we can fix them one by one. It’s about whether the standard library defines types and protocols such that it’s reasonable for programmers to use them to write and use generic algorithms correctly. I’m citing the existing std lib implementations as proof that it’s easy to make mistakes. And I think a more complicated approach, with more operators, more properties, more rules, won’t fix this problem.

>> arbitrary duplication in Set/Dictionary etc. 
> 
> (I disagree that it's arbitrary. If NaN != NaN, then every NaN is properly unique.)
>  
>> The important point to take from this is not “how do we fix the Standard Library?” but rather “these errors are easy to make” by anyone writing generic code using standard protocols. If the Standard Library can’t get these right, how can we expect others to? There are potentially far worse bugs that could result. A differently-written sorting algorithm could corrupt elements (because it relied on substitutability). Other sorting or searching algorithms could easily go into an infinite loop. These problems exist because the code relies on the documented behavior of the protocol, because if you can’t, then what is the point in documenting that behavior?
> 
> It's not that the standard library *can't* get these right, but that it currently *doesn't*, because it documents one set of semantics but implements another, then relies on documented semantics that it knows it does not implement. We both agree that this needs to be fixed.
> 
> The question here is whether it is to be fixed by sticking to the documented semantic guarantees of `==` and bringing all implementations into proper conformance, or alternatively sticking to the implemented behavior of `==` and aligning the documented semantic guarantees to that.
>  
>> I don’t support solutions such as adding a property indicating “containsExceptionalValues” (whatever that means), and expecting every author of a generic algorithm that uses Equatable to remember to call it, and craft custom paranoid behavior (if there is any reasonable behavior) based on it. With recursive conformance landed on master, we finally have a generics system where writing algorithms against Collection can be considered approachable by ordinary users. You no longer have to know things like how Collection.SubSequence needs to be constrained to also be a Collection – it just is. We would be negating this good work to now introduce a whole new set of gotchas that we expect people to know (without the type system even helping them in this case) about how some types, including standard library types, flout the documented rules for Equatable and Comparable, and that you need to use one of a handful of properties to hack in special cases to handle it.
> 
> The gotchas aren't new; they arise when using floating point values, originate with the IEEE definition of floating point equivalence, and exist in some form in every language that has implemented collections of floating point values. Crucially, they exist today in Swift; only, we haven't documented it.
> 
>> And as a user of algorithms, what should you do? If a generic algorithm doesn’t document how it handles these special cases, should you assume it doesn’t? Check the code? Experiment to find out?
>> 
>> This problem also spreads, virus-like, once we have conditional conformance that makes containers equatable when their elements are. [Double] would need to propagate it’s elements’ “exceptionality", to avoid problems with [Double]. Double? will have to do the same.
> 
> This isn't a _problem_. In fact, I consider this to be a key _feature_. Naturally, every protocol conformance (conditional or not) must implement all protocol requirements, so if we add additional requirements they must be implemented. What I'm saying here is that *it may be desirable* to have some protocol-based API to distinguish partial from full equivalence relations. If you accept that premise, then it is the logical consequence that if you conditionally conform `Array` to `Equatable`, you will have to implement any new APIs, and in so doing, document how equivalence of arrays of floating point values relates to floating point equivalence. For me, this is a _good thing_: it documents _in code_ something that today is muddled through.
> 
>>> The explanation that a method on `Float` is a "floating-point context" but a method on `[Float]` is *not a "floating point context"* is, IMO, indefensible.
>> 
>> Nevertheless, I will attempt to defend it :)  
>> 
>> I find it odd that violating the documented requirements of a protocol is considered defensible, but expecting types comply with those requirements is indefensible. A principled stance would be to say that Float shouldn’t conform to Equatable (because… it doesn’t!) and requiring all calls to supply a predicate (and maybe amending types like Dictionary to allow you to supply one). That won’t fly though – users would complain – so instead we are in this murky ground.
> 
> I don't think we should defend violating the documented requirements of a protocol. Either (a) Float should not conform to Equatable (agree, this is a non-starter); (b) how Float conforms to Equatable should be brought into conformance with documented semantics (your stance); or (c) what semantics are documented should be brought into alignment with how conformance is actually implemented (my stance). Naturally, in the last case, additional APIs should be added as needed to make such reduced semantic guarantees useful for generic algorithms.
> 
>> Later in the thread, you mention a possible fix for sort:
>> 
>>> `sort()` is problematic, but not if a custom predicate is supplied.
>> 
>> 
>> So, we are potentially trading off one subtlety (that < behaves differently in generic and non-generic contexts) for another (that you need to know that you need to pass in a special predicate for sorting, or you get nonsense results). Knowing when an algorithm requires you to supply a predicate (like sort) vs when handling for the special case is built in (like equatable) seems far worse complication to me than knowing one rule: that generically when constrained to Comparable, Float adheres to the requirements of Comparable. Always. That is a consistent rule that you need to learn once and that doesn’t vary depending on which algorithm you’re using.
> 
> I would argue that Float should _always_ adhere to the requirements of Comparable, in all contexts. The question is, rather: what can be the requirements of Comparable such that Float can always adhere to them?
> 
>> Another alternative proposed in previous threads is to give Comparable an additional operator (<=> or .compare(to:) that will always enforce a total ordering, and sort can use that. This is, afaict, C#’s solution – double.NaN < 1.0, 1.0 < double.NaN and double.NaN == double.NaN all return false, but Comparer<double>.Default.compare returns -1, 1 and 0 respectively.
> 
> This is, essentially, the endpoint of what I'm proposing.
> 
> Equatable would vend (modulo bikeshedding):
> `==`, a partial equivalence relation
> `~`, a full equivalence relation
> `containsExceptionalValues` (yes, this is a deliberately terrible name, because it's meant to go through bikeshedding), a Boolean value to indicate whether `==` is the same as `~`
> 
> Comparable would vend (modulo bikeshedding):
> `<`, `>`, <=`, `>=`, defined as now
> `<=>`, as in C# `compare` (or maybe, to emphasize the point, `<~>`)
> `containsExceptionalValues`, inherited from `Equatable`, to document the relationship between `<` (etc.) and the spaceship operator
>  

This looks to me to be an absurd mess of operations, none of which will have much hope of being used in a coherent fashion by most people. Should I use == or ~ here? What are the rules again? Will people remember to not use < when they really need <=>? Probably not. Did the author of this framework I’m using remember? Dunno.

The C# model of compare works because < is not available generically. There is no choice between < and <=>, and so the model is simple and easily understood by both algorithm implementors and users. And if you need a different ordering, you can supply your own custom comparator. As far as I can tell, it’s a good model and users are happy with it. Swift is different, since the concrete < is exposed to the generic implementation, but having two possibilities and expecting users to pick is IMO a bad idea. Hence the proposed fix that Float’s Comparable.< is required to be a total order, per the requirements of Comparable, essentially giving us the C# model.

>> This is essentially a backdoor to having one comparison concretely, and another generically, except whether you get that different behavior is left to the whim of the algorithm’s implementor, depending on whether they used < or <=>. And what should sets use? Should a hashed set use == and allow multiple nan, but an ordered set use <=> and exclude them?
> 
> This should absolutely be in the control of the implementor and not the type system. It's superior to have the question of whether `MyCollection.==` uses floating-point equivalence or not be a decision that's made in the implementation of `==` and then explicitly recorded in code (`containsExceptionalValues`); it *shouldn't* be a subtlety of whether it's `MyCollection<T> where T : Equatable` that conditionally conforms to `Equatable` or instead `MyCollection<T> where T : FloatingPoint`.
> 
>>> - `index(of:)` works perfectly sensibly without such a relation; if no NaN is equal to any other NaN, `index(of: .nan)` is appropriately `nil`.
>> 
>> 
>> It works sensibly when you are calling it from a concrete context, and you know that you have is a collection of floating point elements.
>> 
>> But it does not work sensibly if you are using index(of:) as a building block in a wider generic algorithm on Collection, which relies on the rules set out by Equatable. I find myself using index(of:) within generic algorithms frequently, and I really don’t know how I should reason about its use if it’s accepted that the rules of Equatable just don’t hold in the all cases. When operating generically more than one level deep like this, you really need to be able to rely on those rules.
> 
> But, since `index(of:)` is a generic extension method itself, having different behaviors for `==` in the generic vs. concrete context would mean that the behavior of this method *would no longer make sense if you are using `index(of:)` from a concrete context* where you know you have a collection of floating-point elements. And while one may write generic algorithms frequently, I'll bet that the average user of Swift calls `index(of:)` in concrete contexts far more frequently than in generic ones.
> 
> To follow your line of argument, you'd also want `index(of:)` to have different behaviors in the generic vs. concrete context,

There is no concrete context for index(of:), really. There is only a generic context inside its implementation, since it uses Equatable, even if calling it directly from concrete array of floats. If you want “concrete” behavior, you would need to use index(where:), and pass in your own predicate (again, same model as with C#).

> just like `==` does. Carrying this out consistently would ultimately require having an alternative implementation on every collection type of every generic algorithm such as `index(of:)`, using the constraint `Element : FloatingPoint`.
> 
>> This leads to the other argument against having algorithms generic over Equatable behave differently to ones on Float/Double (or FloatingPoint): that when you take your FP algorithm, and then loosen the constraints, it changes behavior in a way that may no longer be correct.
>> 
>> But we aready have the opposite case, where algorithms are written generically and then don’t work correctly for floats. I would argue that is far more harmful and subtle an issue. I honestly don’t think the situation where someone writes an algorithm first against floats, then generalizes it, is a very common path to creating a generic algorithm.  The inverse – where someone writes an algorithm using Equatable, and then people use it with floats – is certainly common, hence this discussion.
>> 
>> There really is no way to square this circle. Every option is going to have downsides. We have to balance correctness, least surprise/most expected behavior for most people, and consistency. For me, making generic use of Equatable and Comparable stick to the documented conformance generically, while keeping FP-specific uses the way they are, is the least bad option.
>   
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171024/73e29858/attachment.html>