How should universal ordering functions behave for Float

[pchiusano]

Discussion with @dolio. Currently the new runtime represents unboxed doubles with ints and uses Int comparison when comparing unboxed doubles. Question is whether bitwise casting a Double to an Int and comparing the Int gives the same results as comparing the doubles directly. (Ignoring NaNs for a minute)

This issue is a question to look at IEEE float layout and see if it gives same results. Does this answer depend on the endian-ness of the architecture?

Next question: what about handling of NaN and Infinity?

Q: Do we want to jump through hoops to have universal ordering behave exactly according to IEEE floats? Or is it okay to have it be a different but still reasonable ordering (given that specialized Float.gt functions still exist)

[dolio]

For reference, I think it's not too hard to make it so that comparing boxed Double values actually uses the floating point comparison. The difficult part is if you expect arbitrary bytes packed into a partially applied function's closure to work like doubles.

I think also this might currently be kind of an academic concern, because I don't think there's any way to partially apply something to unboxed data. But that might not always be true.

[aryairani]

Ignoring NaN and ignoring +0 == -0, they are lexicographically ordered same as ints. Not sure about endianness.

https://people.eecs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF

[...] encodings are all “ Lexicographically Ordered,” which means that if two floating-point numbers in the same format are ordered ( say x < y ), then they are ordered the same way when their bits are reinterpreted as Sign-Magnitude integers. Consequently, processors need no floating-point hardware to search, sort and window floating-point arrays quickly. ( However, some processors reverse byte-order!) Lexicographic order may also ease the implementation of a surprisingly useful function NextAfter(x, y) which delivers the neighbor of x in its floating-point format on the side towards y.

Comparisons to NaN are always supposed to be false (except !=), so how are you supposed to sort a list of Float when <= and > don't form a partition? I think providing a total ordering through integer comparison is a good choice.

[mzaks]

Endianness does apply for floats same as for ints. If there is a sequence of more than one byte, you can write them either from left to right or right to left 🤷‍♂️. And as nobody uses quarter precision floats (8 bit), endianness is always an issue.

Comparing bytes directly works AFAIK for non special cases. Special cases being 0 / -0, NaN, +Inf, -Inf. With zero there are "only" two representation how one can represent it. With not a number and infinity, there is actually large amount of possible bit combinations which result in those "logical values". AFAIK most language let user check if the given number is a "not a number", "positive / negativ infinity". You can also hide it by doing the same under the hood, so if you have two different bit sequences, which both can be represented as infinity you can declare those equal, but to be frank I am not 100% sure what the typical behaviour is.

Regarding comparing doubles (proper values) with each other just a s a byte array. This is "ok" when you comparing literals say 0.1 == 0.1 this is bound to be equal because the transformation is the same. But if the values are results of arithmetic computations, it is very probable that the bit representation will be different, even if logical representation should be the same. This is where epsilon (https://en.wikipedia.org/wiki/Machine_epsilon) comes in to play. Having epsilon based comparison "engraved" into the language could be nice from developer experience point of view, but implies slower comparisons in general.

If you are interested in playing around with float representations, I find this project very helpful: https://evanw.github.io/float-toy/

And for a rabbit hole, deep down exploration of what is wrong with IEEE754, I can recommend following presentation: https://youtu.be/N05yYbUZMSQ

[pchiusano]

I don't think endian-ness is relevant. If you use an Int comparison, that will compare the bytes from most significant to least. Unless the byte order of ints and floats is swapped from each other it should work out, right?

I'm actually curious what other languages do for float sorting. Do they preserve the bizarre partial order behavior and then things silently break if you use a float as a key in a map?

@dolio For boxed doubles we could avoid inspecting the tag at all except for those cases where you're comparing two partially applied functions.

This breaks down for Nat ordering - if the Nat is bigger than 2^63 then Int comparison will give the wrong results. I guess we could just say that Nats are 63 bits.

If we inspect the tag that needs to be more efficient than looking at a Reference and like comparing Text values inside the Builtin.

[pchiusano]

FYI the Haskell Ord Double instance is a partial order and breaks the Ord laws to preserve IEEE float comparison behavior. Not sure I agree with this... see this discussion.

[mzaks]

@pchiusano Swift has the same approach: https://github.com/apple/swift/blob/main/stdlib/public/core/FloatingPoint.swift#L98

Also there is documentation for total order comparison: https://github.com/apple/swift/blob/main/stdlib/public/core/FloatingPoint.swift#L1121

[mzaks]

Also here is the implementation of func isTotallyOrdered(belowOrEqualTo other: Self) -> Bool https://github.com/apple/swift/blob/main/stdlib/public/core/FloatingPoint.swift#L1980

[mzaks]

Maybe this is also interesting. I tried to find how Rust handles order and float numbers and stumbled upon this stackoverflow question:

https://stackoverflow.com/questions/26489701/why-does-rust-not-implement-total-ordering-via-the-ord-trait-for-f64-and-f32

[dolio]

Perhaps a related question is: what is universal ordering for?

Is it for having an arbitrary ordering on (nearly) every type so that it can be used for things like map keys? A lot of things are automatically going to end up that way regardless.

If it's expected to match some more meaningful ordering for some types, why? Is it because we lack a better story for overloading? That seems like a bad reason.

Also, the way thing currently work is going to automatically defeat any abstract type, because what is being compared is the exact structure of the concrete implementation, without any regard for what that structure actually represents. So for instance, sets implemented as a balanced tree may compare differently based on exactly how the tree is balanced, instead of what set is represented.

@mzaks I actually have Gustafson's book. Never got around to reading the whole thing, though. :)

[pchiusano]

In general I think it's useful to have a default ordering available which is often what you want. Saves you writing a bunch of boilerplate in those cases. Same reason that deriving Ord is nice in Haskell.

The specific mechanism in Unison of universal functions that work on the structure of the values is... not that great, for some of the reasons you mention.

I'd like to figure out a better story for typeclasses and overloading, though probably for Unison v2.