[Proposal] Formalized Ordering, take 2


(Pyry Jahkola) #1

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(_:_:slight_smile: 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(_:_:slight_smile: and _max(_:_:slight_smile: functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, _min(_:_:slight_smile: should favour the left-hand side and _max(_:_:slight_smile: 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>)

There is no way to use Comparable.compare as a higher-order function in a non-generic context.
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.
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>
}


Comparable and FloatingPoint types
(Stephen Canon) #2

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@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(_:_:slight_smile: 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(_:_:slight_smile: and _max(_:_:slight_smile: functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, _min(_:_:slight_smile: should favour the left-hand side and _max(_:_:slight_smile: 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>)

There is no way to use Comparable.compare as a higher-order function in a non-generic context.
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.
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>
}


#3

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@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@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(_:_:slight_smile: 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(_:_:slight_smile: and _max(_:_:slight_smile: functions should return the lesser or
greater of the two operands, respectively, while in case of equal
arguments, _min(_:_:slight_smile: should favour the left-hand side and _max(_:_:slight_smile: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Stephen Canon) #4

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.

– Steve

···

On Jul 25, 2016, at 2:23 PM, Nevin Brackett-Rozinsky <nevin.brackettrozinsky@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@swift.org <mailto:swift-evolution@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@iki.fi <mailto:pyry.jahkola@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(_:_:slight_smile: 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(_:_:slight_smile: and _max(_:_:slight_smile: functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, _min(_:_:slight_smile: should favour the left-hand side and _max(_:_:slight_smile: 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>)

There is no way to use Comparable.compare as a higher-order function in a non-generic context.
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.
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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Björn Forster) #5

Hi Pyry,
thanks for all the work you have put into this!
Could you please explain for someone as simple minded as me why there is
(or has to be) a difference in the implementation of <, <= and >, >=?
Sorry, but I don't get into my head why there is/has to be a preference for
one side. Could you or someone else point out (in the proposal) why there
is a need/what is the reason for this?
I assume that this might not be obvious to some other people on the first
look, too.

Björn

···

On Mon, Jul 25, 2016 at 1:41 PM, Pyry Jahkola via swift-evolution < swift-evolution@swift.org> 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(_:_:slight_smile: 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(_:_:slight_smile: and _max(_:_:slight_smile: functions should return the lesser or
greater of the two operands, respectively, while in case of equal
arguments, _min(_:_:slight_smile: should favour the left-hand side and _max(_:_:slight_smile: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Pyry Jahkola) #6

To sort to ascending order, you'd still just call `.sort()` with no arguments.

To limit the scope of this proposal somewhat, I moved the introduction of new sorting functions into the Future directions section. All of those changes are additive in a way or another:

1. The default .sort() function would use `<=>` instead of `<`.

(a) On the one hand, we'd get improved performance in cases like Array<String>.sort() where doing another `<` comparison would be more costly.
(b) On the other hand, we'd get well-defined behaviour when sorting Double arrays containing NaNs, because all non-NaN values would be sorted into one contiguous subrange of the result.

That's an additive change because (a) types implementing total order will still sort according to the same spec as `.sort(by: <)`.

2. If I had it my way, the default .sort() would also become stable, and the programmer could opt in to using a faster unstable sort variant. There are cases where an unstable sort performs better, but a stable sort is a better default, not least because it's usually what people want when sorting a table by a given column.

3. Several functions (e.g. `.sort(by:)`) would be paired with a `frobnicate(ordering:)` variant where the block returns `Ordering` instead of `Bool`. For sorting to descending order, you'd call something like `someCollection.sort(ordering: Ordering.reversing(<=>))`. Or whatever naming we'll end up with.

— Pyry

···

On 25 Jul 2016, at 21:23, Nevin Brackett-Rozinsky <nevin.brackettrozinsky@gmail.com> wrote:

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.)


(Xiaodi Wu) #7

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 Mon, Jul 25, 2016 at 1:52 PM, Stephen Canon via swift-evolution < swift-evolution@swift.org> wrote:

On Jul 25, 2016, at 2:23 PM, Nevin Brackett-Rozinsky < > nevin.brackettrozinsky@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@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@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(_:_:slight_smile: 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(_:_:slight_smile: and _max(_:_:slight_smile: functions should return the lesser or
greater of the two operands, respectively, while in case of equal
arguments, _min(_:_:slight_smile: should favour the left-hand side and _max(_:_:slight_smile: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(David Sweeris) #8

Two quick questions…
1) What about adding an `isInvalid` case? That way types (such as Double/Float) which have “unordered” values can check for an invalid comparison.
2) What about making `Ordering` a tuple instead of an enum? “typealias Ordering = (isLessThan: Bool, isEqual: Bool, isGreaterThan: Bool, isInvalid: Bool)”? It’d take up more space on the stack, but I think this:
func < (lhs: Int, rhs: Int) -> Bool {
    return (lhs <=> rhs).isLessThan
}
or even this:
func < (lhs: Int, rhs: Int) -> Bool {
    let ord = (lhs <=> rhs).isLessThan
    return ord.isLessThan && !ord.isInvalid
}

would execute faster than this:
func < (lhs: Int, rhs: Int) -> Bool {
    switch (lhs <=> rhs) {
    case lessThan: return true
    default: return false
}

because there wouldn’t be any branching beyond what’s necessary to do the actual comparison.

- Dave Sweeris

···

On Jul 25, 2016, at 2:28 PM, Pyry Jahkola via swift-evolution <swift-evolution@swift.org> wrote:

On 25 Jul 2016, at 21:23, Nevin Brackett-Rozinsky <nevin.brackettrozinsky@gmail.com <mailto:nevin.brackettrozinsky@gmail.com>> wrote:

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.)

To sort to ascending order, you'd still just call `.sort()` with no arguments.

To limit the scope of this proposal somewhat, I moved the introduction of new sorting functions into the Future directions section. All of those changes are additive in a way or another:

1. The default .sort() function would use `<=>` instead of `<`.

(a) On the one hand, we'd get improved performance in cases like Array<String>.sort() where doing another `<` comparison would be more costly.
(b) On the other hand, we'd get well-defined behaviour when sorting Double arrays containing NaNs, because all non-NaN values would be sorted into one contiguous subrange of the result.


(Pyry Jahkola) #9

The reason is two-fold:

Firstly, and most importantly, because we want the law of antisymmetry (that `a < b` iff `b > a`, and likewise for ≤ and ≥) to hold even in the presence of strange types. Turning only one operator of every such pair into customisation points makes it essentially impossible to break that law.

Secondly, because we want to minimise the surface area of Comparable to keep the API as simple as possible. The drawback of my design is that while it manages to alleviate many subtleties of IEEE-754, it also contains many member functions (essentially all but `<=>`) which should not be customised for most types in practice.

— Pyry

···

On 25 Jul 2016, at 18:51, Björn Forster <bjoern.forster@googlemail.com> wrote:

Could you please explain for someone as simple minded as me why there is (or has to be) a difference in the implementation of <, <= and >, >=?
Sorry, but I don't get into my head why there is/has to be a preference for one side. Could you or someone else point out (in the proposal) why there is a need/what is the reason for this?
I assume that this might not be obvious to some other people on the first look, too.