RFC: Totally ordered wrappers for `f32` and `f64` (and possibly others)

[lifthrasiir]

It is well known that f32 and f64 are not totally orderable by default, and thus does not implement TotalOrd and TotalEq. However it is less known that we rarely need the total ordering in reality, and the standard library has only two cases requiring the total ordering (sorting and TreeMap). #12434 and #12435 are based on this observation, but we can think in the other direction: we can provide totally ordered wrappers for partially ordered types.

The suggested wrappers, TotallyOrderedF32 and TotallyOrderedF64 will be tuple (newtype) structs for f32 and f64. (Yes, I know this name doesn't look good, it's intentional.) They have the following constraints: (TOF for any of two types)

x < y  and x == x and y == y implies TOF(x).cmp(&TOF(y)) == Less
x > y  and x == x and y == y implies TOF(x).cmp(&TOF(y)) == Greater
x == y and x == x and y == y implies TOF(x).cmp(&TOF(y)) == Equal
           x != y or  y != y implies TOF(x).cmp(&TOF(y)) is arbitrary (but a function of x/y)

The actual implementation would be similar to IEEE 754-2008 totalOrder except that TOF(-0).cmp(&TOF(+0)) == Equal, otherwise we would break the constraints as -0 == +0. Combined with Deref (#7141, which would have to be implemented eventually) I no longer see the separation of Ord/Eq and TotalOrd/Eq is necessary. Usability-wise, the compiler can suggest TotallyOrderedF{32,64} on the failure to expand #[deriving(TotalOrd)] (and others) for f32 and f64.

This RFC only concerns about f32 and f64 since they are commonly encountered non-totally-ordered types, but if we want to pursue this further, we can alternatively provide a TotalOrder generic wrapper that massages Ord implementors to aforementioned constraints.

[thestinger]

However it is less known that we rarely need the total ordering in reality, and the standard library has only two cases requiring the total ordering (sorting and TreeMap).

Is there any generic code built on Eq and Ord that's correct in the presence of floating point types? If the answer is no, then the traits are not useful. I think the answer is no, because even min, max and clamp require specialized versions for floating point. The HashMap implementation is also incorrect as it really requires TotalEq (#5283).

The #12435 pull request is intended to remove a set of useless traits from the standard library, and make the usable ones into the default. The standard library is simply too complex, and needs to limit the usage of traits to cases where they're helpful for writing generic code. It's silly to have a set of traits for overloading operators not usable by generic code and then another set of traits with real guarantees but no operating overloading. Floating point types do have a total ordering available, so providing a terrible API for the sake of floating point seems silly.

I think it's important to keep in mind that if traits only have type signatures but no laws, then the advantage of explicitly declaring type bounds instead of inferring the requirements from the implementation is pretty much gone. The traits aren't really documenting anything about the API if they don't provide either a strict weak order or total order.

[pnkfelix]

"It's silly to have a set of traits for overloading operators not usable by generic code and then another set of traits with real guarantees but no operating overloading"

If each trait that provided the guarantees extended the trait that defined the overloaded operator, then I'm not sure that's totally silly. (I mean, it would be a little silly, in that the use of a trait to define the operator is solely an artifact of how Rust does operator-overloading. But not completely silly.)

E.g. I'm thinking something like this:

#[lang="ord"]
/// This trait is solely to provide access to {<, >, <=, >=} sugared operators,
///  but there are no guarantees about their semantics.  It has an intentionally ugly
/// name to discourage use as an accidental trait-bound on type parameters.
pub trait OrdOps {
    fn lt(&self, other: &Self) -> bool;
    #[inline]
    fn le(&self, other: &Self) -> bool { !other.lt(self) }
    #[inline]
    fn gt(&self, other: &Self) -> bool {  other.lt(self) }
    #[inline]
    fn ge(&self, other: &Self) -> bool { !self.lt(other) }

    // FIXME (#12068): Add min/max/clamp default methods
}

/// This trait provides concrete guarantees about ordering.
/// Note that f32/f64 does not impl this trait, but most other numerics do.
trait Ord : OrdOps {  }

Note that then #[deriving(Ord)] would need to be changed to inject definitions for both OrdOps and Ord.

Having said that, I do not do enough floating-point work myself to push hard to support {<, >, <=, >=} as built-in operators for f32/f64. This was just something I thought of this morning that I thought might resolve this issue. (Its possible that someone had already suggested this elsewhere.)

[thestinger]

@pnkfelix: IEEE754 defines a total ordering and we are going to implement it, so leaving out an implementation of the total ordering trait for floating point isn't a good option. This means the traits can't have any inheritance relationship if the operators are overloaded with the weak ordering for floating point types. So, there's a trait for generic code and a trait for operator overloading with the overloaded operators not usable in generic code.

[pnkfelix]

@thestinger my assumption is/was that people working with floating point might prefer to use the operator notation for the non-total-ordering. But I admit this would make it hard/impossible to mix generic-code that uses the Ord bound with structures that are employing floats (since the whole point of my suggestion was to make f32/f64 implement OrdOps and not Ord).

[pnkfelix]

@thestinger Oh wait, maybe I misunderstood part of your response.

You said: "So, there's a trait for generic code and a trait for operator overloading with the overloaded operators not usable in generic code."

Does this mean you can have more than one trait providing access to the same overloaded operators? (And presumably choose between them via appropriate use of use). If so, (1.) I did not know that, and (2.) Rust gets cooler every day.

(Update: rust may get cooler every day, but the above hypothesis is flawed, because you cannot currently have more than one trait with the #[lang="ord"] attribute. Not sure at the moment if that idea is forever impossible or if we might be able to hack it in post 1.0. It does not matter terribly for now.)

[thestinger]

I mean that as long as the floating point numbers use the non-total-ordering for the comparison operators, Rust won't have usable comparison operator overloading in generic code. Even the min and max functions are not correct for floating point types, and need to be switched to TotalOrd. The HashMap container needs to be switched to TotalEq and ordered maps/sets and sorting already use TotalOrd. I think it's a real disaster at the moment.

[pnkfelix]

@thestinger So just to be clear, when you said "So, there's a trait for generic code and a trait for operator overloading with the overloaded operators not usable in generic code.", this second trait, not usable in generic code (which presumably would be solely for f32/f64): you did not mean that it would provide access to infix {<, >, <=, >=} for f32/f64, right? Just that it would provide access to methods with names like float_lt, float_gt, etc (or something along those lines) that use the hardware's floating point comparison operations?

(I took your use of the word "overloaded operators" to mean "infix sugar", but it seems you could not have meant that.)

[thestinger]

No, I think you're misunderstanding what I'm saying. I am only saying that today, TotalOrd is for generic code and Ord is used only for the operator overloads. The situation today is that Eq and Ord are nearly useless traits, simply bloating the API documentation and causing confusion. These traits are unspecified, without any guarantees, so generic code can't make use of them. Floating point types would cause nearly any generic code to be incorrect since as generic code it's not going to include the necessary handling of NaN like fmin, fmax, a float-specific clamp, etc.

The TotalEq and TotalOrd traits are the ones usable by generic code, but do not provide operator overloads. Operators have to be tied to be a specific trait (in this case, Eq and Ord) or there will be coherency issues. It's not possible for these to inherit from Eq and Ord for the operator overloads because floating point types will not be implementing the same operations for both. Therefore, generic code has not access to operator overloads at the moment. There aren't convenience methods either (names taken by Ord), so it has to call cmp and compare against the Ordering variants.

[pnkfelix]

@thestinger Okay. You may not believe this, but I have understood the issues you have describing about Ord and Eq not providing any built-in guarantees that all-implementors adhere to, and I agree with the philosophy you have been espousing (namely that Ord/Eq are useless as trait bounds unless they do have some semantic laws associated with them).

I was just musing about a way to try to keep the operator-sugar available for floating-point hackers. I acknowledge that the separation I was proposing has similar problems to that of the existing Ord/TotalOrd separation; I was mostly just hoping that it would be less confusing (since the distinct roles of "provide operator sugar" and "provide semantic guarantees" would be better distinguished).

But I am fine with forcing people who want the hardware f32/f64 operations to have to use different methods without infix sugar.

[thestinger]

The previously existing proposal is #12435. The Eq and Ord traits provide the strong guarantees and operator overloads. There will be no need for partial or total ordering traits as it's simply not possible to provide this with a sane trait hierarchy. Floating point types will implement Eq and Ord with the IEEE754 totalOrder predicate, so deriving and generic code will work correctly.

The faster hardware floating point ordering can be provided by the Float trait as fcmp, fmin, fmax, fclamp, feq, fne, flt, [...]. It doesn't need to introduce complexity into the trait hierarchy.

• generic code should able to use operator overloads
• generic hash tables, ordered maps/sets, min, max, clamp and sorting require more than the hardware floating point comparisons can provide - some of these can be done with it, but doing it correctly requires deviating from a fast implementation (checks for NaN, inability to use three-way comparison functions like memcmp)
• floating point types have both the weak partial ordering and a totalOrder predicate defined in IEEE754

From a purely performance point of view, LLVM needs you to mark floating point operations with the permitted error and relax the restrictions on floating point transformations to allow generating fast code anyway.

[thestinger]

(nevermind the above, it was written before you posted the latest comment)

[glaebhoerl]

I believe the situation can be summarized as, out of the following:

1. Allow use of comparison operator overloads in generic code (rather than methods),
2. Have the comparison operators on f32 and f64 do what people are accustomed to, and what hardware implements (rather than the total ordering defined separately by IEEE754),
3. Allow use of generic code with f32 and f64

Choose any two. @thestinger chooses 1. + 3., @pnkfelix is proposing 1. + 2.

1. • 2. is possible if we have separate a trait OrdOps for the operator overloads, and a trait Ord: OrdOps which decrees a total order and that if a type impls Ord, its OrdOps impl must also be consistent with that order. f32 and f64 implement OrdOps according to the usual hardware-provided semantics, which do not provide a total order, and do not implement Ord. We then separately have newtypes such as struct TotalF32(f32) and struct TotalF64(f64), which implement both OrdOps and Ord according to the IEEE754 total ordering.

[pnkfelix]

@glaebhoerl to be honest, when I proposed 1. + 2., I had not thought through the consequences w.r.t. e.g. structs that have f32/f64 fields (which would then not be able to do deriving(Ord) under my proposal). ((I do acknowledge that your newtype wrappers would be a way to accommodate those cases.))

I think I'd prefer 1. + 3. over 1. + 2., given our current set of constraints. The only person, I think, who suffers under 1.+3. is the poor floating-point hacker, and while I would love to say "oh haven't they suffered enough?", I think if we choose nice-looking + short names for the methods then we will be okay.

[glaebhoerl]

How much potential is there for people who are not "floating-point hackers" per se, but happen to have stumbled into using f32/f64 for some particular task, to be bitten by this?

Essentially, I think that means, if you're not aware of the intricacies of floating-point math and just (naively) expect the comparison operators to do something reasonable, does the IEEE754 total ordering qualify?