> On Oct 24, 2017, at 9:06 PM, Xiaodi Wu via swift-dev <swift-dev@swift.org>
> wrote:
>
> On Tue, Oct 24, 2017 at 10:08 PM, Ben Cohen <ben_co...@apple.com
> <mailto:ben_co...@apple.com>> wrote:
>
>
> On Oct 24, 2017, at 6:48 PM, Xiaodi Wu <xiaodi...@gmail.com
> <mailto:xiaodi...@gmail.com>> wrote:
>
>> On Tue, Oct 24, 2017 at 1:55 PM, Ben Cohen <ben_co...@apple.com
>> <mailto:ben_co...@apple.com>> wrote:
>>
>>
>>> On Oct 19, 2017, at 4:29 PM, Xiaodi Wu via swift-dev <swift-dev@swift.org
>>> <mailto:swift-dev@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.
>
> Honestly, I don't know that most users have thought about this possibility at
> all. Sure, a sort that matches IEEE total order _might_ be justifiable. But
> users are as likely to expect that the last item in the sorted collection
> will be the greatest and that the first item in the sorted collection will be
> the smallest. Now, you can say that NaN compares larger than everything,
> everywhere. But the moment that they try to plug that last element into, say,
> an AppKit UI function, they're toast.
>
> I certainly disagree with ideas of trapping on NaN inside `==` or similar
> functions, but I really do think that an argument can be made that it is not
> reasonable to proceed with sorting an array that contains NaN.
>
>
>> 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.
>
> Well, to my mind, this problem you state really works out to:
>
> (a) People expect generic algorithms that operate on Comparable types to work
> correctly with floating-point types
> (b) Generic algorithms that operate on Comparable types don't work correctly
> with floating-point types unless the author is very, very careful
> (c) People shouldn't have to be very, very careful to write working generic
> algorithms that work with floating-point types
>
> Which, in turn, really boils down to:
>
> (d) People expect floating-point types not to have numerous unintuitive (but
> learnable) properties, including NaN being unordered
> (e) Floating-point types have numerous unintuitive (but learnable)
> properties, including NaN being unordered
>
> The reason I'm writing to swift-dev (rather than evolution) is that my
> interest is in fixing the standard library. I'm not even convinced that this
> problem you state is fixable, at least on your terms. In the interest of not
> increasing the API surface area, you would propose to blow away (e) in the
> generic but not concrete context. Now, while it's true that an alternative to
> increasing the API surface area is to have the same API exhibit
> context-specific behaviors, that certainly isn't any less complicated
> conceptually, as we would then be faced with the notion that floating-point
> types both have and do not have numerous unintuitive properties, depending on
> the context in which they are used.
>> 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 syntax here is not the point (or if it is, it can be bikeshedded). The
> point I'm trying to make is that what you're criticizing as _incoherent_ is
> also _inescapable_. Floating-point types have a notion of equivalence that
> isn't full equivalence. For certain use cases (both concrete and generic), we
> want that partial equivalence, while for other use cases (both concrete and
> generic), we truly want full equivalence. To work with floating-point types
> correctly, a user must know that there is a difference between the two. If
> there is no hope of "most people" understanding this distinction when one
> relation is named `==` and the other is named `~`, then _a fortiori_ there is
> no hope of "most people" understanding the distinction when they're conflated
> into one operator `==` that has different behaviors in different contexts.
>
> 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 < isexposed 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.
>
> A true C# model would be fine, but the key point of that model to my mind is
> that partial equivalence and full equivalence are spelled differently (that
> is, `==` and `Equals`, respectively). It would not work with IEEE `==` being
> spelled the same way as Comparable `==`. If we were to rename the IEEE
> operation `&==` instead, then we'd functionally have a design that's broadly
> similar to the earlier version, only with different names:
>
> Equatable would vend `==`, a full equivalence relation (and `!=`)
> Comparable would vend `<`, `>`, `<=`, `>=`, now operators that reflect a
> total order over the set of all values; and maybe `<=>`
> Floating point would additionally vend `&==` and `&<` (and `&!=`, `&<`, `&>`,
> `&<=`, `&>=`)
>
> One key difference here would be that the partial equivalence relation would
> now only be found on floating-point types, and it would not be possible to
> write a generic algorithm that operates on any partially equatable or
> equatable type. But the other--and major--issues would be (a) that all
> concrete uses of floating-point comparison operators would have to be
> migrated to append an extra `&`; and (b) this syntax suggests that most users
> want to use `==` *instead of* `&==`, which I'm not sure is the case--and
> certainly isn't the case if they're trying to do the same things they're used
> to doing with floating-point values in other languages.
What about having the protocol hierarchy look like this? (All names subject to
bikeshedding, of course)
protocol MaybeEquatable {
static func ?== (lhs: Self, rhs: Self) -> Bool?
}
protocol MostlyEquatable : MaybeEquatable {
static func == (lhs: Self, rhs: Self) -> Bool
}
extension MostlyEquatable {
static func ?== (lhs: Self, rhs: Self) -> Bool? { return lhs == rhs }
// allows a `MostlyEquatable` or `Equatable` to function as a `MaybeEquatable`
without any extra code
}
protocol Equatable : MostlyEquatable {} // purely a semantic difference, no
extra syntax
protocol MaybeComparable : MaybeEquatable {
static func ?< (lhs: Self, rhs: Self) -> Bool?
// plus the rest of them
}
protocol MostlyComparable : MaybeComparable, MostlyEquatable {
static func < (lhs: Self, rhs: Self) -> Bool
// plus the rest of them
}
extension MostlyComparable {
static func ?< (lhs: Self, rhs: Self) -> Bool? { return lhs < rhs } //
allows a `MostlyComparable` or `Comparable` to function as a `MaybeComparable`
without any extra code
// plus the rest of them
}
protocol Comparable : MostlyComparable, Equatable {} // purely a semantic
difference, no extra syntax
extension Double : MostlyComparable {
static func ?== (lhs: Double, rhs: Double) -> Bool? {
return lhs.isNaN || rhs.isNaN ? nil : lhs == rhs
}
static func ?< (lhs: Double, rhs: Double) -> Bool? {
return lhs.isNaN || rhs.isNaN || (lhs.isInfinite == true &&
rhs.isInfinite == true && lhs.sign == rhs.sign) ? nil : lhs < rhs
}
static func == (lhs: Double, rhs: Double) -> Bool {
// whatever current impl is
}
static func < (lhs: Double, rhs: Double) -> Bool {
// whatever current impl is
}
}
This would let people easily switch between the two kinds of "correct" generic
comparisons (returning a `Bool?` for types that could have invalid comparisons
and a `Bool` for types that can't), as well as easily opting into using
IEEE-754's current "arguably incompatible with sane generic programming"
behavior (by constraining T to "MostlyComparable" instead of "Comparable") if
that's what they really want.
`Collection` could have different implementations of `==` depending on whether
`Element` conforms to "MaybeEquatable" or "MostlyEquatable/Equatable", solving
the "a = [Double.nan]; print(a == a) // prints true" issue.
This doesn't involve trapping on anything, so dunno what the performance
implications would be. All the extra work would be contained in the "?*"
functions, though, so at least existing code wouldn't sudden get slower.
- Dave Sweeris
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev