Operator constraints in Go

https://blog.merovius.de/posts/2022-05-23-operator-constraints/

by Merovius • 4 years ago

47 18 4 years ago

blog.merovius.de

I don't program in Go. But I could imagine that I might at some point want to sort a list of a custom struct by one of its members. And that's probably as advanced as it would get for my purposes.

Merovius5• 4 years ago

Note that the article targets people writing generic code, not consuming it. So it's not really about what you want to sort. It's about what (and how) you want to support with your sorting algorithm.

As for that use-case: Go generics currently don't have a way to constrain on struct fields. So that will always have to be done with some sort of custom comparison function written by the user of your code, which returns the appropriate field.

jeffbee2• 4 years ago

Hrmm. How do float32 and float64 satisfy constraints.Ordered? The Go spec (which is almost uselessly vague and will some day contain 1000 pages of caveats) just says that floats are "comparable and ordered, as defined by the IEEE-754 standard" but of course that standard doesn't really say that, it specifically says that NaN are unordered. I just checked quickly with Compiler Explorer and float32<float32 emits UCOMISS on x86, which makes sense, resulting in 42.0<NaN and NaN<42.0 both being false, as expected. So how does it handle the constraint for float?

jerf• 4 years ago

Basically, it doesn't work for sorting. https://pkg.go.dev/golang.org/x/exp/slices#Sort mentions this explicitly and has a suggested alternative solution. You can see this in action here: https://go.dev/play/p/6GuDa8ziU0L

Note in the second case, that's not "Go" sorting NaNs to the front, that's the requested result from the passed-in function. You could create any result you wanted with a suitable choice of such function.

This isn't particularly special to Go. Most languages have "quirks", to put it charitably, around floats. Even Haskell would have similar behavior. It's really the IEEE standard that is broken, arguably; defining an entity that is not equal to itself proceeds to effectively break a huge swathe of things that you may not have even realized was based on the presumption that the identity property holds, because... why would you think about what is based on that? It's so foundational. As anyone who has dealt with NaNs for any period of time can attest, it's really difficult to work with such entities.

(Similarly, while I understand what they were trying to get at, I think SQL NULL should be equal to itself. I could be down with NULL < 1 being false and NULL > 1 being false but I'm not a huge fan of how it's NULL either. We've had many languages written since then with more conventional ideas about "invalid" values and how they participate in operators and I think the modern way almost everything else works is better, even if it arguably less "correct".)

jeffbee2• 4 years ago

The entire C++ STL is a huge footgun for this very reason. None of the algorithms work on floats unless you guarantee the absence of NaN (which the STL assumes without being terribly vocal about it).

nerdponx• 4 years ago

This is problematic even in dependently-typed languages like Idris, because while you can require a proof that something is not (or does not contain) NaN, it's pretty easy to call a function that is allowed to return NaN, which means that you actually cannot satisfy that proof after calling one of those functions unless you actually check again.

dinosaurdynasty• 4 years ago

Rust handles this in a "correct", if annoying way: the stdlib sort requires its elements to have a "totally ordered" trait, and floating point doesn't have that trait. You have to either give a custom comparison function, or use a "non-NaN and totally orderable floating point" type some non-stdlib crates have.

Merovius5• 4 years ago

How do float32 and float64 satisfy constraints.Ordered?

Well, the simple answer is that constraints.Ordered is a type set which lists them: https://pkg.go.dev/golang.org/x/exp/constraints#Ordered

The other answer is of course, that float32 and float64 have a < operator, so every type listed in constraints.Ordered does, so you can use the < operator on a type parameter constrained by constraints.Orderded.

The real question you seem to be asking though, is "how does Go support < on float32 and float64 if the IEEE-754 standard says that NaN are not comparable". I can't comprehensively answer that, because I don't know that standard well enough. But for == the answer is that == is supported on floats and x == y is always false if either is NaN. Empirically, the same seems to be true for NaN <= NaN: https://go.dev/play/p/hB9CnrzpAVq

In any case, Wikipedia claims that IEEE-754 defines in fact an ordering, which is the one Go is going to use use: https://en.wikipedia.org/wiki/IEEE_754#Total-ordering_predic...

lalaithion• 4 years ago

For a function, it makes sense to just write two functions, the easiest to use, and the one with maximum flaxibility.

    func SortOrdered[T constraints.Ordered](s []T) {
      // …
    }

    func Sort[T any](s []T, less func(T, T) bool) {
      // …
    }

For a data structure, I recommend using

    type SearchTree[T any] struct {
      Less func(T, T) bool
      // …
    }

and then writing two constructors

    func NewSearchTree(less func(T, T) bool) *SearchTree[T] {
      // …
      return &SearchTree[T]{
        Less: less,
        // …
      }
    }

    func NewOrderedSearchTree[T constraints.Ordered]() *SearchTree[T] {
      // …
      return &SearchTree[T]{
        Less: func(x, y T) bool {return x < y},
        // …
      }
    }

Merovius5• 4 years ago

Personally, I very much dislike that this makes the zero value of `SearchTree[T]` not useful. I personally feel that anything which only handles data (as opposed to something like an os.File) shouldn't require explicit initialization.

I genuinely think I might personally converge on the `Comparator[T]` approach only (at least for types), for that reason.

karmakaze2• 4 years ago

Nice write-up and summary. The emoji chart would be easier to visually parse with more traditional symbols e.g. [I realize these Unicode symbols could also be considered emoji but are less emotional.]

majewsky2• 4 years ago

Or even with words. "yes" and "no" are much easier to distinguish at a glance than thumbs-up-emoji and thumbs-down-emoji.

Merovius5• 4 years ago

I considered both. The issue I'm having is that "yes" and "no" is semantically wrong - or rather, semantically uninteresting. The interesting question is if a particular mechanism is "good" or "bad" in a particular way. For "boilerplate types", a "yes" is bad. For "custom order", a "yes" is good.

Writing "yes" or "no" (or using checkmarks and crosses) means I either have to put it on the reader to do that extra step of inference. Or that I have to re-phrase every item to be aligned in this way, while staying snappy. Or I could write "good" and "bad", of course, which seemed… overly simplistic.

Anyways, I did think about all of this and it was a conscious decision. For better or for worse. And I'm okay with it, criticism notwithstanding :)

gavinray• 4 years ago

What is shown in the examples I know as the term "generic interface" or, in some fancy languages, "typeclasses"

TheDesolate0• 4 years ago

Imagine looking at a Garbage Collected language that isn't even a complete language (You just got generics, FFS) and thinking, "Yeah, this is a great idea!"

Operator constraints in Go

Related Stories