[swift-evolution] [Proposal] Formalized Ordering, take 2
Xiaodi Wu
xiaodi.wu at gmail.com
Mon Jul 25 14:06:54 CDT 2016
On Mon, Jul 25, 2016 at 1:52 PM, Stephen Canon via swift-evolution <
swift-evolution at swift.org> wrote:
> First, this is orthogonal to "adhering to the standard".
> isTotallyOrdered( ) provides the total order predicate required by IEEE
> 754. The standard has no opinion about whether or not `<=>` is bound to
> that predicate.
>
> Personally, I would be OK with using the `isTotallyOrdered` semantics for
> `<=>`. However, it leads to some behavior that would be surprising for
> novices: x is NaN, and a set S is { 1, 2, NaN }, but S does not contain x.
> I am skeptical that the distinction between NaN payloads is salient *for
> generic code written on Comparable types*. It *is* salient for some
> (rare!) floating-point specific code, but `isTotallyOrdered` is available
> for floating-point types.
>
> There’s also the issue that if we want to be able to point at IEEE 754 and
> say “<=> implements a total order on Level N”, distinguishing distinct NaNs
> has consequences for other values. In particular, it means that a decimal
> type should distinguish between 1e0 and 10e-1, because it would necessarily
> be an ordering on level 3 or 4. For { 1, 20 } to not contain 2e1 seems
> highly dubious to me.
>
Given your reasoning, I have to agree that ordering on level 2 is the only
sensible option for generic code written on Comparable types.
With this resolution, I think Dave has largely convinced me that the design
as originally proposed (shadowable but not overridable `==` forwards to
`===`, etc.) should be workable for wisely chosen implementations of `===`
and `<=>`.
– Steve
>
> On Jul 25, 2016, at 2:23 PM, Nevin Brackett-Rozinsky <
> nevin.brackettrozinsky at gmail.com> wrote:
>
> Pyry, this proposal looks great to me. My one question is, will I be able
> to write `someCollection.sort(.ascending)` and get the expected
> result? (This could be an additive future direction.)
>
> Stephen, what is your rationale for wanting `<=>` to identify NaN values
> with different payloads as `.equal`?
>
> I believe the IEEE 754 total order specification uses the bit-pattern just
> as Pyry’s proposal does, and there is value is adhering to the standard.
> Besides, if someone intentionally wishes to consider all NaN values as
> equivalent they can use `.isNaN` (or even map them to .nan first for
> uniformity).
>
> Nevin
>
>
> On Mon, Jul 25, 2016 at 1:26 PM, Stephen Canon via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> Hi Pyry —
>>
>> Dave and I spent some time discussing the details of how this applies to
>> floating point earlier today. We’re now in agreement that <=> should treat
>> -0 and +0 as distinct, and treat all NaNs as .equal. There are three
>> motivating considerations:
>>
>> 1. Although -0 and +0 are “IEEE 754 equal”, there is no computation that
>> can produce both of them. In the parlance of IEEE 754, for any rounding
>> mode, the sets of real values that round to them are disjoint. Because of
>> this, if -0 and +0 appear as members of a set, or as keys in a dictionary,
>> they necessarily are the result of distinct computations or data.
>>
>> 2. Substitutability. Adopting these semantics means that if `x <=> y` is
>> `.equal`, `f(x) <=> f(y)` is also `.equal` for any computation `f(x)` that
>> depends on the represented value (as opposed to the encoding) of its
>> argument.
>>
>> 3. 754 defines four “specification levels”, or models:
>>
>> - Level 1: The two-point compactification of the reals, or “extended real
>> numbers”.
>> - Level 2: The set of representable floating-point data: {-inf … -0}
>> union { 0 … inf } union { NaN }.
>> - Level 3: The set of representations of floating-point data:
>> sign-exponent-significand triples, +/-inf, qNaN, sNaN.
>> - Level 4: Floating-point encodings (bit patterns).
>>
>> The `<=>` semantics we propose constitute a total order on level 2, which
>> is the computable model closest to the (reasonably familiar) extended real
>> numbers. Treating -0 and +0 as .equal would put us in a bit of a no-man’s
>> land between levels 1 and 2.
>>
>> Thanks,
>> – Steve
>>
>> On Jul 25, 2016, at 7:41 AM, Pyry Jahkola <pyry.jahkola at iki.fi> wrote:
>>
>> Since we're running short on time, and the previous discussion thread
>> diverged, here's my attempt to fix the Comparable protocol.
>>
>> *Pull request:* https://github.com/apple/swift-evolution/pull/464
>>
>> TL;DR:
>>
>> 1. Equatable remains unchanged, while Comparable bloats a bit to support
>> several use cases.
>> 2. `a <=> b` is well-defined even if either value is NaN. Zero is equal
>> to minus zero.
>> 3. Types are not strictly required to become totally ordered, even if
>> it's strongly recommended.
>>
>> — — —
>>
>> I simply can't see how a pure total order version of Comparable would fit
>> the standard way floating point values are expected to behave. However, I
>> think we can reach a satisfactory conclusion, one that involves no crashing
>> in the standard library, which is what I previously suggested.
>>
>> What I'm trying to fix is so that all operations listed in
>> https://dl.dropboxusercontent.com/u/217402/Comparable.pdf abide to laws
>> for types without incomparable values, and that types with weaker order can
>> still work in *some* well-defined way outside their totally ordered
>> range.
>>
>> PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for
>> time is tight. I can pull back or revise the proposal if you don't want to
>> be involved.
>>
>> — Pyry
>>
>>
>>
>>
>> Formalized Ordering
>>
>> - Proposal: SE-NNNN
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md>
>> - Authors: Robert Widmann <https://github.com/codafi>, Jaden Geller
>> <https://github.com/jadengeller>, Harlan Haskins
>> <https://github.com/harlanhaskins>, Pyry Jahkola
>> <https://github.com/pyrtsa>
>> - Status: Awaiting review
>> - Review manager: TBD
>>
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction>
>> Introduction
>>
>> This proposal cleans up the semantics of ordering relations in the
>> standard library. Our goal is to formalize the total ordering semantics of
>> the Comparable protocol and still provide accessible ordering
>> definitions for types without total ordering semantics.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation>
>> Motivation
>>
>> The standard comparison operators have an intuitive meaning to
>> programmers. Swift encourages encoding that in an implementation of
>> Comparable that respects the rules of a total order
>> <https://en.wikipedia.org/wiki/Total_order>. The standard library takes
>> advantage of these rules to provide consistent implementations for sorting
>> and searching generic collections of Comparable types.
>>
>> Not all types behave so well in this framework, unfortunately. There are
>> cases where the semantics of a total order cannot apply and still maintain
>> the traditional definition of “comparison” over these types. Take, for
>> example, sorting an array of Float s. Today, Float ‘s instance of
>> Comparable follows IEEE-754 and returns false for all comparisons of NaN .
>> In order to sort this array, NaN s are considered outside the domain of < ,
>> and the order of a “sorted” array containing them is undefined.
>>
>> In addition, generic algorithms in the Swift Standard Library that make
>> use of the current Comparable protocol may have to make twice as many
>> comparisons to request the ordering of values with respect to each other
>> than they should. Having a central operation to return information about
>> the ordering of values once should provide a speedup for these operations.
>>
>> In the interest of cleaning up the semantics of Comparable types of all
>> shapes and sizes and their uses in the Swift Standard Library, this
>> proposal is going to re-arrange the requirements of the Comparable and
>> Equatable protocols.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution>Proposed
>> solution
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable>
>> Equatable
>>
>> The interface of Equatable remains unchanged under this proposal.
>> Equatable types should still respect the equivalence laws of
>> *reflexivity* (a == a), *symmetry* (a == b iff b == a), and
>> *transitivity* (if a == b and b == c, then a == c). Further, != remains
>> a top-level binary operator for which a != b iff !(a == b).
>>
>> Types containing properties *inessential to equality*, however, are
>> allowed to retain their notion of identity. For example Array's capacity isn't
>> considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign
>> != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
>>
>> IEEE-754 floating point numbers are allowed to break the reflexivity law
>> by defining that .nan != x for any value of x, which is the standard
>> behaviour documented in IEEE-754 and implemented the same way in other
>> programming languages.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable>
>> Comparable
>>
>> The Comparable protocol will now require (without default implementation
>> provided) a single operator definition: <=> — the comparison operator.
>> From this, all other comparison operators will be derived so as to respect
>> the total order semantics of Comparable:
>>
>> To maintain compatibility with IEEE-754, the interface of Comparable also
>> contains as customization points the operators <, <=, and == (derived
>> from Equatable) as well as the static binary functions _min(_:_:) and
>> _max(_:_:). User-defined types are recommended against overriding the
>> default implementations.
>>
>> The uncustomizable top-level binary comparison operators a > b and a >= b are
>> implemented as synonyms to b < aand b <= a, respectively.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library>Standard
>> Library
>>
>> Unlike a previous revision of this proposal, standard library algorithms
>> specific to FloatingPoint remain unchanged.
>>
>> Overloads of <=> for tuples of Comparable elements are provided up to a
>> library-defined arity.
>>
>> The intent of this proposal is to later augment the standard library so
>> that functions that take an ordering predicate by: (T, T) -> Bool will
>> have an overload ordering: (T, T) -> Ordering that will provide a —
>> potentially — more efficient implementation. A list of such functions is
>> provided in Future directions.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design>Detailed
>> design
>>
>> The Comparable protocol will be amended by taking away > and >=, adding
>> customisation points _min(_:_:), and _max(_:_:), and introducing the
>> ordering operator <=> that makes use of the Ordering enum defined below.
>>
>> enum Ordering : Equatable {
>> case ascending
>> case equal
>> case descending
>> }
>> infix operator <=> { associativity none precedence 130 }
>> public protocol Comparable : Equatable {
>> // Implementation required:
>> static func <=>(lhs: Self, rhs: Self) -> Ordering
>>
>> // Default implementations provided:
>> static func == (lhs: Self, rhs: Self) -> Bool // derived from Equatable
>> static func < (lhs: Self, rhs: Self) -> Bool
>> static func <= (lhs: Self, rhs: Self) -> Bool
>> static func _min(_ lhs: Self, _ rhs: Self) -> Self
>> static func _max(_ lhs: Self, _ rhs: Self) -> Self
>> }
>>
>> The <=> operator defines a relationship between == and <=> such that a
>> == b iff (a <=> b) == .equal, unless Self chooses to break the semantics
>> in the way of IEEE-754. Likewise, it should hold that (a <=> b) ==
>> .ascending iff a < b, and (a <=> b) != .descending iff a <= b.
>>
>> The _min(_:_:) and _max(_:_:) functions should return the lesser or
>> greater of the two operands, respectively, while in case of equal
>> arguments, _min(_:_:) should favour the left-hand side and _max(_:_:) the
>> right-hand side to retain identity, as presently explained in this
>> comment
>> <https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20>.
>> Making them customization points of Comparable, we get to fix their
>> behaviour in the presense of unorderable values (SR-1011
>> <https://bugs.swift.org/browse/SR-1011>).
>>
>> Most user types should only implement <=> and leave the other members of
>> Equatable and Comparable to their default implementations. Note that
>> even == has a sane default implementation if Self is made Comparable:
>>
>> // Default implementations, which should be used for most Comparable types:extension Comparable {
>> static func == (l: Self, r: Self) -> Bool { return (l <=> r) == .equal }
>> static func < (l: Self, r: Self) -> Bool { return (l <=> r) == .ascending }
>> static func <= (l: Self, r: Self) -> Bool { return (l <=> r) != .descending }
>> static func _min(_ l: Self, _ r: Self) -> Self { return r < l ? r : l }
>> static func _max(_ l: Self, _ r: Self) -> Self { return r < l ? l : r }
>> }
>> // Unoverridable top-level operators and functions for Comparable:public func > <T : Comparable>(l: T, r: T) -> Bool { return r < l }public func >= <T : Comparable>(l: T, r: T) -> Bool { return r <= l }public func min<T : Comparable>(_ l: T, _ r: T) -> T { return T._min(l, r) }public func max<T : Comparable>(_ l: T, _ r: T) -> T { return T._max(l, r) }
>>
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons>Handling
>> of floating point comparisons
>>
>> *The following text is written in terms of Double but other
>> floating-point types (Float, Float80) are proposed the same treatment.*
>>
>> The IEEE-754 floating point specification has two oddities when it comes
>> to orderability: there are two zeros (0.0 and -0.0) which are considered
>> equal to each other, and there are *multiple* not-a-number values x for
>> which x.isNaN == true and x != y with any value of y, even x itself.
>> (Remark: the most common NaN value is obtained by the static property
>> Double.nan.)
>>
>> The interface of Comparable is designed so that <=> alone is able to
>> produce a total order among all possible Doublevalues, sorting negative
>> NaNs less than any other values, and positive NaNs greater than any other.
>> Otherwise, within the range of totally ordered floating point values, -Double.infinity
>> ... Double.infinity, the result of a <=> b remains in full agreement
>> with the laws of a < b, a <= b, and a == b.
>>
>> The suggested implementation of Double : Comparable makes <=> distinguish
>> between every different bitPatternof NaN:
>>
>> extension Double : Comparable {
>> public static func <=> (l: Double, r: Double) -> Ordering {
>> func ordinal(_ x: UInt64) -> UInt64 {
>> return x < 0x80000000_00000000 ? x + 0x7fffffff_ffffffff : ~x
>> }
>> return ordinal(l.bitPattern) <=> ordinal(r.bitPattern)
>> }
>> public static func == (l: Double, r: Double) -> Bool { return Builtin.eq(l, r) }
>> public static func < (l: Double, r: Double) -> Bool { return Builtin.lt(l, r) }
>> public static func <= (l: Double, r: Double) -> Bool { return Builtin.le(l, r) }
>> public static func _min(l: Double, r: Double) -> Double { return Builtin.fmin(l, r) }
>> public static func _max(l: Double, r: Double) -> Double { return Builtin.fmax(l, r) }
>> }
>> // Likewise:extension Float : Comparable { ... }extension Float80 : Comparable { ... }
>>
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal>Tuples
>> and order reversal
>>
>> Due to missing language support, tuples of Comparable elements cannot be
>> Comparable themselves, but in the spirit of SE-0015
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md>,
>> such tuples are given their overloads of <=> up to a standard library
>> defined maximum arity:
>>
>> public func <=> <A : Comparable, B : Comparable>(lhs: (A, B), rhs: (A, B)) -> Ordering {
>> let a = lhs.0 <=> rhs.0
>> if a != .equal { return a }
>> let b = lhs.1 <=> rhs.1
>> if b != .equal { return b }
>> return .equal
>> }
>> // Similarly for <A : Comparable, B : Comparable, C : Comparable>, etc.
>>
>> To simplify the reversal of a given ordering operation, two members of
>> Ordering are provided in an extension:
>>
>> extension Ordering {
>> public static func reversing<T : Comparable>(_ ordering: (T, T) -> Ordering)
>> -> (T, T) -> Ordering
>> {
>> return { l, r in ordering(r, l) }
>> }
>>
>> public var reversed: Ordering {
>> switch self {
>> case .ascending: return .descending
>> case .equal: return .equal
>> case .descending: return .ascending
>> }
>> }
>> }
>>
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation>
>> Foundation
>>
>> In addition, Foundation code will now bridge NSComparisonResult to
>> Ordering allowing for a fluid, natural, and safe API.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code>Impact
>> on existing code
>>
>> The biggest drawback of the proposed design is the large surface area of
>> Comparable's interface, as well as the possibility of overriding the
>> comparison operators by mistake. On the other hand, since the required
>> <=> operator is new and affects all users porting their previously
>> Comparable data types to Swift 3, we can use documentation to suggest
>> removing the redundant (and possibly faulty) implementations of other
>> comparison operators.
>>
>> Existing Equatable but not Comparable types that define an equivalence
>> relation with == will remain unchanged.
>>
>> Existing Comparable types that define a total ordering with < will need
>> to implement <=> and should remove their existing implementation of any
>> comparison operators, including ==. All other existing Comparable types
>> should implement <=> that provides a total ordering, or should drop
>> their Comparable conformance.
>>
>> Before:
>>
>> struct Date: Comparable {
>> let year: Int
>> let month: Int
>> let day: Int
>> }
>> func ==(lhs: Date, rhs: Date) -> Bool {
>> return lhs.year == rhs.year
>> && lhs.month == rhs.month
>> && lhs.day == rhs.day
>> }
>> func <(lhs: Date, rhs: Date) -> Bool {
>> if lhs.year != rhs.year {
>> return lhs.year < rhs.year
>> } else if lhs.month != rhs.month {
>> return lhs.month < rhs.month
>> } else {
>> return lhs.day < rhs.day
>> }
>> }
>>
>> After, using the tuple overload of <=>:
>>
>> struct Date: Comparable {
>> let year: Int
>> let month: Int
>> let day: Int
>>
>> static func <=> (lhs: Date, rhs: Date) -> Ordering {
>> return (lhs.year, lhs.month, lhs.day)
>> <=> (rhs.year, rhs.month, rhs.day)
>> }
>>
>> // // Explicit version:
>> // static func <=> (lhs: Date, rhs: Date) -> Ordering {
>> // let yearResult = lhs.year <=> rhs.year
>> // guard case .equal = yearResult else { return yearResult }
>> // let monthResult = lhs.month <=> rhs.month
>> // guard case .equal = monthResult else { return monthResult }
>> // return lhs.day <=> rhs.day
>> // }
>> }
>>
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered>Alternatives
>> considered
>>
>> A previous design of this proposal suggested a strict total order upon
>> Comparable. While that would make generic algorithms more correct, the
>> definition ended up fighting against the expected behaviour of floating
>> point numbers.
>>
>> An alternative design that better matches the existing arithmetic-related
>> protocols in Swift is one that uses a member function.
>>
>> public protocol Comparable: Equatable {
>> func compare(to: Self) -> Ordering
>> }
>>
>> However, while this API does read better than an operator, we believe
>> that this imposes a number of artificial restrictions (especially in light
>> of SE-0091
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md>
>> )
>>
>> 1. There is no way to use Comparable.compare as a higher-order
>> function in a non-generic context.
>> 2. If a member is desired, it can be provided in a protocol extension
>> and defined in terms of the ordering operator; to each according to their
>> need.
>> 3. The existing tuple overloads cannot be expressed with a member
>> function.
>>
>> One other that Rust has adopted is the inclusion of PartialEquatable and
>> PartialComparable as ancestors of their flavor of Equatable and
>> Comparable . Having protocols to organize and catalogue types that can
>> only guarantee partial equivalence and ordering relations is a good
>> approach for modularity but clutters the standard library with two new
>> protocols for which few useful algorithms could be written against.
>>
>> <https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions>Future
>> directions
>>
>> That the default sort() compares by < and not <=> should be considered a
>> bug to be fixed in a future version of Swift. Using <=> will make sort() well-behaved
>> in the presense of NaN. However, given that the current behaviour is to
>> produce an unspecified order, the fix is additive and can be slipped past
>> Swift 3.
>>
>> With <=> in place, several present and future standard library
>> algorithms involving a <T : Comparable> requirement will possibly
>> benefit from knowing the total ordering of two operands at once. This is a
>> list of possible such functions (taking Array as example), to be
>> proposed separately as an additive change:
>>
>> extension Array {
>> // Sorting
>>
>> mutating func sort(ordering: @noescape (Element, Element) throws -> Ordering) rethrows
>> func sorted(ordering: @noescape (Element, Element) throws -> Ordering) rethrows -> [Element]
>> mutating func stableSort(ordering: @noescape (Element, Element) throws -> Ordering) rethrows
>> func stableSorted(ordering: @noescape (Element, Element) throws -> Ordering) rethrows -> [Element]
>>
>> /// Reorders the elements of the collection such that all the elements
>> /// returning `.ascending` are moved to the start of the collection, and the
>> /// elements returning `.descending` are moved to the end of the collection.
>> /// - Returns: the range of elements for which `ordering(x) == .equal`.
>> mutating func partition(ordering: @noescape (Iterator.Element) throws -> Ordering) rethrows -> Range<Index>
>>
>> // Binary search
>>
>> func bisectedIndex(ordering: @noescape (Element) throws -> Ordering) rethrows -> Index?
>> func lowerBound(ordering: @noescape (Element) throws -> Ordering) rethrows -> Index
>> func upperBound(ordering: @noescape (Element) throws -> Ordering) rethrows -> Index
>> func equalRange(ordering: @noescape (Element) throws -> Ordering) rethrows -> Range<Index>
>> }
>>
>>
>>
>>
>> _______________________________________________
>> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160725/3f953874/attachment.html>
More information about the swift-evolution
mailing list