API: add simpler CompareSameType interface

The current CompareSameType interface, which answers queries like "is x < y?" or "is x >= y?", arose from my misunderstanding of the requirements of typical sort routines. Go's sort.Sort accepts a less func(x, y) bool parameter, which misled me into thinking that it could sort values that are not totally nor even weakly ordered, such as IEEE 754 float NaN values. This is not the case: nearly all efficient sort algorithms assume the relation is at least weakly ordered. (For this reason, you can't use sort.Sort on floats; the sort.SortFloats wrapper defines a weak order over floats by mapping NaNs to the least element.)

Once this was recognized, we changed the spec so that Starlark's sole sort function, sorted, would work correctly on a list of floats: the Starlark spec diverges from IEEE 754 and states that floats are totally ordered, with all NaN values considered equal, and larger than infinity. (See https://github.com/google/starlark-go/commit/3b7e02ecde8b80808c06c8284ce9f85c101fcebd)

Consequently, it would be sufficient for the CompareSameType interface not to accept a relational operator (such as < or >=) and return a boolean, but to return a three-valued comparison (<0, 0, >0). This would simplify all implementations, which must currently copy the threeway function. We can't break the API, but we could add a new Compare interface and have the interpreter test for it first. Let's do that.

google / starlark-go

API: add simpler CompareSameType interface #356