define Ord as a total ordering and remove the f32/f64 implementation (similarly, remove the Eq implementation)

[thestinger]

The operators will still work, because they are a language feature. This would remove the need for TotalEq and TotalOrd. The current situation is too complex and traits without requirements aren't good traits. These do need some kind of definition, whether it's a total ordering or a weak ordering.

Floating point types could still implement these via the IEEE754 total ordering predicate. For equality, it will be as fast as it's just a bitwise comparison. It looks like there's no way to avoid a performance hit for comparisons, but the traditional weak ordering can still be provided via alternate methods.

[nikomatsakis]

One implication of this is that you could not sort an array of floats

[nikomatsakis]

We could add PartialEq and PartialOrd and make Eq and Ord total

[pnkfelix]

Need to discuss further. accepted for 1.0. P-backcompat-lang.

[thestinger]

@nikomatsakis: You wouldn't be able to use a sort method based on Ord, but passing a closure to a more flexible sort method would work and I think we'll want that flexibility available anyway.

[thestinger]

There's now a sort_by method so floats won't be left without an array sorting method. Deciding how to order NaN becomes the problem of the code calling sort_by.

[huonw]

FWIW, [].sort() currently uses TotalOrd so sorting an array of floats already requires using a closure with .sort_by().

[nikomatsakis]

One thought: Why is it so hard to implement Ord for f32 and f64? That is, we can define a total ordering (e.g., borrowing the definition that Java uses). It does mean that the < operator will not necessarily be the same as the Ord trait. I used to think this was awful but I think I've personally come to terms with it.

[nikomatsakis]

I guess this does not work as well for Eq unless we define the operator == to be some other trait.

[thestinger]

@nikomatsakis: I think it would be quite strange for < to do a different operation in a generic function for floating point numbers. IEEE754 does define a total order for floating point numbers but I think using it would be a performance hit for the ordering functions (although not equality).

[thestinger]

I think doing this is incredibly important. A sane definition of equality and ordering is required for these traits to be useful for writing correct generic code. If having these for floating point numbers is viewed as important, then we should to implement the IEEE754 total ordering for the built-in comparison operations and these traits. The traditional partial ordering can be provided via a separate set of methods.

Without defined requirements, traits are the worst of both worlds. They're more verbose than generics without bounds and aren't enforcing a set of requirements on the type parameters.

[emberian]

I agree with this.

[brson]

Nominating.

[pongad]

I can try to work on this. My current plan (which might be completely stupid): created impl<A: TotalOrd> Ord for A or ord_from_total macro and rename TotalOrd to Ord later. Does everyone think this is reasonable? I totally understand if anyone thinks we should plan more before starting to implement.

[thestinger]

There needs to be a plan in place for floating point. It's not just a library issue.

[pongad]

Do you think it's possible for binary comparison on floating points to do total ordering by default? Does anyone know if there's a meeting planned to address this issue in general?

[nikomatsakis]

This issue would benefit from a RFC writeup. (In general, I want to
encourage us to move more in this direction, versus scattered
discussion.) Before writing code, I think, the next step is to write
a document that will (1) summarize the situation, (2) make a specific
and complete proposal, and (3) discuss the ramifications and possible
alternatives. This could then be sent to the rust-dev mailing list and
linked to from here.

[thestinger]

@pongad: IEEE754 defines a total ordering predicate, but hardware doesn't implement it.

[pongad]

RFC:
https://docs.google.com/document/d/18pYRBTN8iM5q2nfkNGiHn10_mSm4vXO-3D_aS-h-RvE/edit?usp=sharing

[thestinger]

I don't think it needs to take more than one step. We can just add the correct definition to Eq and Ord while removing TotalEq and TotalOrd. Floating point can also be switched to using the total ordering.

[pongad]

I personally like to iterate and not do everything at once. Though I do
agree that it does not have to take more than one step. I assume from
your comment that you don't have anything against the change list itself?

On Wed, Feb 19, 2014 at 11:58 PM, Daniel Micay [email protected]:

I don't think it needs to take more than one step. We can just add the
correct definition to Eq and Ord while removing TotalEq and TotalOrd.
Floating point can also be switched to using the total ordering.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/10320#issuecomment-35589423
.

[thestinger]

I don't think it should be left in intermediate states. It should really be done in one pull request to avoid a need to use stage annotations and a compiler snapshot too. The annoying part is obtaining a copy of the IEEE754 standard and correctly implementing the ordering.

[lilyball]

I am rather concerned about defining the normal comparison operators (<, etc) using the total order predicate for floating point numbers. Anybody who has any experience whatsoever with floating point will be surprised that Rust evaluates a < b differently than every other language (that I'm aware of). I'm also concerned that this would be opting into the slow implementation by default.

Unfortunately, I don't have a good suggestion here. It would be odd for a < b and a.cmp(b) to disagree, which is why we can't just implement TotalOrd for floating point numbers and call it a day. But I'm not sure that's any worse than what's being proposed here.

[thestinger]

@kballard: Having TotalEq and TotalOrd traits is overcomplicated and this issue is about eliminating them. The Eq and Ord traits are rarely useful. It's not even possible to define a correct generic min, max and clamp via those traits since floating point types need more work to handle NaN. Sorting and tree maps/sets already use TotalOrd so there aren't really any correct users of Ord.

Implementing TotalOrd for floating point values will not eliminate the need to implement both Ord and TotalOrd for endless user-defined types. Most forgot to implement TotalOrd if they're not being used in a tree.

With the IEEE754 total ordering, == and != won't be any slower, and < and > may not be any slower (depends on how NaN ordering is supposed to work). The only operators that will certainly be slower are <= and >=. These operators belong to the Eq and Ord traits so floating point has to follow whatever they define as the requirements.

[lilyball]

@thestinger Do you have any evidence for your claims about performance? From what wikipedia says about the IEEE floating point total order predicate, ==, !=, and < will behave differently. For example, -0 == 0 in hardware but not with the total order predicate. And the total order predicate only matches the hardware < when the hardware < returns true; the total order predicate is free to return true if < returns false. These suggest to me that the hardware implementation cannot be used for these operators, which indicates that it will indeed be slower.

Why are <= and >= in Ord? Could they be moved to TotalOrd? Offhand, it seems likely to me that it's in Ord because people would expect <= to work if both < and == work, but maybe if we moved it to TotalOrd then people would be more likely to remember to derive it.

Perhaps #[deriving(Ord)] could be modified to derive TotalOrd as well, unless the type is flagged with #[no_total_ord]? We could also have a lint that warns on any types that explicitly implement Ord but not TotalOrd (again, unless flagged with #[no_total_ord]). That would go a long way to ensuring people implement TotalOrd.

And then, perhaps to make it more obvious what's going on, we could rename TotalOrd to Ord, rename Ord to PartialOrd, and then have #[deriving(Ord)] also count as #[deriving(PartialOrd)]. This approach should mean we can avoid the #[no_deriving_ord] and lint, because anyone who derives or implements PartialOrd directly have a hint from the name that they're not getting full ordering. The only wrinkle here is anyone who implements Ord directly would also have to implement PartialOrd, but that doesn't seem particularly onerous to me.

[thestinger]

This issue is about removing TotalEq and TotalOrd. I think there is a strong consensus that the existing situation is too complex, and that Eq and Ord have proven to be useless for generic code. Further complicating it by making TotalOrd a language feature via another lang item and splitting up the comparison methods is not going to help. It's going to result in generic code requiring Eq + Ord + TotalOrd where it would otherwise require only Ord. Anyway, the current Eq definition for floating point is not a correct implementation of equality either so it's not restricted to Ord and TotalOrd cannot be tied to Eq (it must be tied to TotalEq). Traits exist to write generic code and there's no use in adding traits if they're not actually usable.

A PartialOrd/PartialEq trait should not be added without a use case in generic code. It wouldn't solve the floating point issue because a sane PartialOrd would be available if Ord is was available, and it would need to perform the same operation.

I moved the floating point part of the problem to #12434.

Do you have any evidence for your claims about performance?

It seems equality would be a bitwise comparison.

[thestinger]

Performance-wise, Rust already needs a check for integer division by zero, signed integer division of INT_MIN by -1, overlong shifts, casts to and from floating point types and bounds checks. I don't really think this is really any different - Rust won't be as efficient as C with the default operators, but the weak ordering can still be provided via the Float trait as flt, fgt, fle, fge, feq, fne and fcmp along with the min, max and clamp implementations specific to floating point types.

[nikomatsakis]

On Thu, Feb 20, 2014 at 06:36:00PM -0800, Kevin Ballard wrote:

I am rather concerned about defining the normal comparison operators (<, etc) using the total order predicate for floating point numbers. Anybody who has any experience whatsoever with floating point will be surprised that Rust evaluates a < b differently than every other language (that I'm aware of). I'm also concerned that this would be opting into the slow implementation by default.

+1

Unfortunately, I don't have a good suggestion here. It would be odd for a < b and a.cmp(b) to disagree, which is why we can't just implement TotalOrd for floating point numbers and call it a day. But I'm not sure that's any worse than what's being proposed here.

I am currently of the opinion that they should just disagree. I
thought it was weird at first, but i've gotten over it. There is
precedent for this (e.g., Java).

[thestinger]

I am no longer go to push for this. There is too much opposition to it and the existing design can stay as it is today.

[glaebhoerl]

@nikomatsakis / @kballard There's also a variant where comparison operators on f32 and f64 behave as usual, and also has most of the benefits of this proposal (Eq and Ord have meaningful laws, generic code can use operator overloads and assume the laws, etc.), with the drawback that f32 and f64 need to be wrapped in newtypes to be used with code generic over Eq and Ord. See my comment in an other thread for details.

[thestinger]

@glaebhoerl: Yes, I'm fine with doing that instead. I added the TotalEq and TotalOrd traits in the first place and intended to port the generic code to it, while this idea was more recent. I thought there was a strong consensus that the distinction was too much to encode into traits but I was clearly mistaken.

[thestinger]

I'll send another pull request removing the equals method from TotalEq and adding trait inheritance.

[nikomatsakis]

@pongad thank you btw for writing up an RFC.

I think perhaps some details were missing, but if I understood correctly, the end goal of what is described is to:

1. Remove existing Eq and Ord traits
2. Rename existing TotalOrd to Ord
3. Remap operators to methods of TotalOrd
4. Have no support for a notion of partial ordering

I think there are two seemingly irreconcilable constraints:

1. The operators (< etc) should ideally work as they do in nearly every other language (with possible exception of Haskell, which I believe uses a total equality for floats). This implies that floats are not totally ordered.
2. For most generic code, total ordering is mandatory.

The palette of options then becomes:

1. Use total ordering everywhere, implementing some version for floats:
   • Pro: Ord and operators do the same thing.
   • Con: Non-standard behavior of operators, possible porting hazard and performance penalty. In particular, floats do not use the builtin hardware operations, which may impact the use of things like SIMD operations and so forth.
2. Use partial ordering for operators, total ordering for generics:
   • Pro: Basic floating point operators use the built-in hardware and are consistent with other languages. Extension to SIMD and so forth are clear.
   • Con: Generic code generally doesn't get to use operators, unless it is willing to accept partial ordering. This distinction is subtle and people may choose the wrong thing (e.g., a sort may only require the bound for the < operator, even though it expects a total ordering).
   • Con: Ord and operators diverge in behavior.

Precedents: I believe Haskell took approach 1 and Java chose approach 2. Note that in both cases, I am assuming that we implement some total ordering for floats, whatever it is, as that seems strictly better, though opinions may vary here.

As I've stated, I am inclined towards option 2, though I see the appeal of option 1. This seems, however, to be related to #11831 -- i.e., to what extent will the Rust types reflect the native hardware behavior, and to what extent will they attempt to emulate something closer to "true" mathematics.

[nikomatsakis]

@brson I think this is something we should discuss at upcoming team meeting along with #11831 (which you said you'd prepare)

[glaebhoerl]

@nikomatsakis You seem to be at least partly re-hashing the discussion we had in #12442. My understanding of the relevant tradeoffs was here. Further elaboration on my part between two of the options was here. In particular, the proposal I describe at greater length in the latter comment (you can read it as an RFC if you like) is different from both of the options you just described.

[nikomatsakis]

@glaebhoerl indeed. I'm rehashing discussions that have been had numerous times both in other bugs and here and you're right I omitted many choices. Clearly we need to cull some of these bugs!

[thestinger]

#12517 is the issue for @glaebhoerl's suggestion, although with altered naming.

[pongad]

I agree with the discussion above. Though, I'm a little confused: will the comparison operators on user defined types work off of Ord or PartialOrd?

[thestinger]

The comparison operators will be tied to PartialOrd and PartialEq. If a type implements Ord and Eq, then the comparison operators implement a total ordering. The Eq trait won't provide any methods itself, trait inheritance will provide them.

[pongad]

I'm not quite sure what you mean by the last sentence. Is there some kind of design doc that I can look up? (Sorry if it's in the discussion above and I missed it.)

[thestinger]

I opened #12520 with a list of things to change but I haven't written new documentation for std::cmp yet.

[pongad]

@thestinger Thanks! Will take a look.

[pnkfelix]

@pongad you said: "I'm not quite sure what you mean by the last sentence."

To make it clear, the sentence "the Eq trait won't provide any methods itself, trait inheritance will provide them" means something like this:

trait DeclareOps<T> {
    fn op1(&self, other: &Self) -> T;
    fn op2(&self, other: &Self) -> T;
}

trait AddLaws<T> : DeclareOps<T> {
    // no new methods; just new laws about how existing methods op1 and op2 must behave.
}

[pongad]

@pnkfelix I get it now. Thanks a lot!