You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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 3b7e02e)
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.
The text was updated successfully, but these errors were encountered:
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 3b7e02e)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.The text was updated successfully, but these errors were encountered: