# Comparable and FloatingPoint

There is a small but important tangle of issues around the interaction between `min` and `max` operations and `Comparable` and `FloatingPoint` protocols and the IEEE 754 standard that I would like to attempt to resolve.

This is a subtle subject. I will attempt to give a good overview of all the issues involved. For the purposes of this discussion, the behavior of comparisons (`==`, `!=`, etc) is out of scope. I am focused on min and max operations. Please read the entire post and attempt to stay focused.

IEEE 754 (2008)
The 2008 revision of 754 defined the following four operations (these are IEEE 754 operations, not Swift functions, but I am translating the interface from IEEE 754 pseudocode into Swift for familiarity):

• `func minNum<T>(_ x: T, _ y: T) -> T`
• `func maxNum<T>(_ x: T, _ y: T) -> T`
• `func minNumMag<T>(_ x: T, _ y: T) -> T`
• `func maxNumMag<T>(_ x: T, _ y: T) -> T`

These are defined to return the lesser / greater / lesser in magnitude / greater in magnitude of `x` and `y` if neither operand is NaN, the number operand if one argument is a quiet NaN, and a quiet nan if either operand is a signaling NaN or both operands are quiet NaNs.

These definitions are mostly sensible for pairwise operation, but they have a fatal flaw if you attempt to extend them to more than two arguments or use them in reductions: they are not associative in the presence of signaling NaNs. Example:

``````minNum(minNum(1, .signalingNaN), 2) = minNum(.nan, 2) = 2
minNum(1, minNum(.signalingNaN, 2)) = minNum(1, .nan) = 1
``````

FloatingPoint in Swift 3 ... 4.2
The `FloatingPoint` protocol binds IEEE 754; these operations are surfaced as the static functions `minimum`, `maximum`, `minimumMagnitude` and `maximumMagnitude`.

They are not surfaced as the `min` and `max` free functions defined on `Comparable` (which always returns the first argument if either is NaN), nor as the `fmin` and `fmax` free functions defined by the platform C module (which bind the C stdlib `fmin` and `fmax` functions).

IEEE 754 (201x)
Because of the flaw that I discuss above, the revision of IEEE 754 currently in preparation will remove the `minNum`, `maxNum`, `minNumMag`, and `maxNumMag` operations entirely. In their place, there are eight recommendedâ€”but not requiredâ€”operations added to clause 9:

• `func minimum(_ x: T, _ y: T) -> T`
• `func maximum(_ x: T, _ y: T) -> T`
• `func minimumMagnitude(_ x: T, _ y: T) -> T`
• `func maximumMagnitude(_ x: T, _ y: T) -> T`
• `func minimumNumber(_ x: T, _ y: T) -> T`
• `func maximumNumber(_ x: T, _ y: T) -> T`
• `func minimumMagnitudeNumber(_ x: T, _ y: T) -> T`
• `func maximumMagnitudeNumber(_ x: T, _ y: T) -> T`

`minimum` and `maximum` return NaN if either argument is NaN, and the lesser/greater of the two arguments otherwise. The `Magnitude` operations compare magnitudes. The `Number` operations discard NaNs, preferring to return number arguments.

These new operations have the virtue of being associative, which makes them suitable for use in reductions. They are unfortunately not required; as recommended operations, they may change somewhat in the next revision of IEEE 754 (202x), so we should exercise some caution in adopting them.

(I'm going to talk only about minimum from here on out; everything also applies to maximum). For those keeping score at home, we have considered five different "minimum" operations at this point. The one bound to `Comparable.min` is not ideal because it isn't commutative in the presence of NaN. The one bound to `FloatingPoint.minimum` has been explicitly abandoned from IEEE 754, and is probably the worst of the bunch.

Swift 5 ...
I suggest the following (again, I am only discussing minimum; all of this applies equally to maximum):

1. Add a customization point for binary `min` on `Comparable` that lets us override the behavior for `FloatingPoint`. Use this for the implementation of n-ary `min`, so that the behavior matches.
2. Deprecate `FloatingPoint.minimum`, marking it renamed to `FloatingPoint.minimumNumber`, which matches the IEEE 754 recommended operation (the semantics of the two are identical except for signaling NaNs, which are effectively a bug in the current Swift `minimum`, so this is a very reasonable replacement).
3. Deprecate the `fmin` free function. We don't need another name for this operation floating around to confuse things, and it's a holdover from the C stdlib.

The remaining questions after doing these three things are:

1. Should we provide a binding for the new IEEE 754 `minimum` operation?
2. What should the semantics of `Comparable.min` be on `FloatingPoint`?

The obvious thing to do is to have `Comparable.min` implement the new IEEE 754 `minimum` operation. This is pretty reasonable, because it satisfies most of the properties that we want for `Comparable.min`: it is associative, and it is commutative (up to representation when `x == y`). This would be a completely fine solution, I think.

There is one additional property, however, which is desirable for the `min` free function; that the sets {x, y} and {min(x,y), max(x,y)} are the same. This cannot be satisfied by either of the IEEE 754 recommended notions of `minimum`. I can think of at least one other option that we may want to consider: make NaNs a `preconditionFailure` when used in `Comparable.min`, and repurpose `FloatingPoint.minimum` to bind the IEEE 754 `minimum` operation.

This would leave us with three notions each of `minimum` and `maximum`; the two recommended IEEE operations, as static funcs on `FloatingPoint`, and a third definition which only allows values that are non-exceptional under `Comparable`. This may be a better solution, or it may be the pathway to a rabbit hole of ever-increasing complexity that we're better off ignoring.

5 Likes

[Note that I left the `Magnitude` operations out of my discussion about what to do about the situation; this is deliberate. They're much less-used, and should almost surely simply follow whatever we do for the normal minimum and maximum operations.]

My opinion is that if a `min` etc. customization point is added to `Comparable`, then the implementations for `FloatingPoint` types should `preconditionFailure`.

3 Likes

I think your proposed plan is the most reasonable, including `preconditionFailure` for comparing NaNs with a customized `Comparable.min`.

As for the new IEEE minimum, it may be best to keep the number of notions of â€śminimumâ€ť to a minimum and forego exposing that operation for the moment, especially in light of potential future changes in the standard.

1 Like

Thank you for this really good break down!
Can we just fix the bug in swift 5 and leave the name the same?

I do not like the idea of having a precondition for NaN. Doesnâ€™t that just defeat the whole purpose of NaN?

I prefer NaN and anything is NaN throughout and therefore `{1, NaN} != {min(1, NaN), max(1, NaN)}`. With the â€śNaN and anything is NaNâ€ť rule there is no need to introduce the new IEEE comparisons.