Add support for partial ordering to Comparators

[Akirathan]

After recent discussion with @JaroslavTulach and @radeusgd (the conclusion is here #5742 (comment)) we have decided that we will roll back the behavior of comparators to allow specification of partial ordering. The new API shall look like so:

type Ordered_Comparator
  is_ordered = True
  compare : Any -> Any -> (Ordering|Nothing)
  hash -> Any -> Integer

type Unordered_Comparator
  is_ordered = False
  equals : Any -> Any -> (Boolean|Nothing)
  hash : Any -> Integer

for compare x y, the return value of Nothing specifies that x and y are incomparable. (for example, this will be the case when x or y is NaN).

Tasks

Preview Give feedback

1. Reject NaN is a new builtin type #5744.
2. Make sure that there are no regressions in related benchmarks.
3. Consider using just compare method without dedicated equals method

[enso-bot]

Pavel Marek reports a new STANDUP for today (2023-02-27):

Progress: Reverting back the functionality of comparators such that partial ordering is supported. Reformating every related builtin node such that it can take Nothing and produce Nothing values. Also had a GPU debugging session with @Frizi trying to figure out what is going on with the performance on my local setup with 4k display. The conclusion is that it is most likely due to some weird bugs with my GPU driver. It should be finished by 2023-03-03.

[JaroslavTulach]

Why don't we have just a single:

type Comparator
  compare : Any -> Any -> (Ordering|Nothing)
  hash -> Any -> (Integer|Nothing)

Such an API is simpler and achieves the same. Everyone who would want to support just equals can implement compare: Any -> Any -> (Ordering.Equal | Nothing) at the same cost and speed.

[Akirathan]

Now that we support partial ordering, and we can have situations like:

type My_Comparator
  equals x y = x.data == y.data
  hash x = Nothing

i.e. hash just returns Nothing, or equals can return Nothing for almost all instances except for few ones, etc. I am thinking it is, indeed, not necessary anymore to differentiate between an ordered comparators and unordered ones.

These all changes of course mean that we will have to deal with more weird comparator behavior at runtime, but since we all agreed that our users are as clueless as possible, then I think these changes are just fine.

The author of the proposal to differentiate between ordered and unordered comparators is @radeusgd, so if he does not have any strong opinions against merging ordered and unordered comparators into single comparators, then let's do it.

[JaroslavTulach]

Have I made an oversight in the previous comment? I am surprised hash could return Nothing - why? I believe the requested behavior should be:

type Comparator
  compare : Any -> Any -> (Ordering|Nothing)
  hash -> Any -> Integer

Don't we want all Enso objects to participate in (hash) Map? If so, we want them to have hash computed. They cannot say no. Of course they can return hash _ = 0 or any other constant - which has similar meaning.... so my comment is more about expectations... but still: returning Nothing shall not be encouraged.

[Akirathan]

You are right. We can, and probably should, enforce users to specify hash for all the values, even the incomparable ones. That should not break the hash contract. So far, I have just updated the docs, and method signatures, so let me revert it such that hash method cannot return Nothing.

By the way, let's deal with the merging of unordered and ordered comparators into a single one in a separate issue.

[radeusgd]

The author of the proposal to differentiate between ordered and unordered comparators is @radeusgd, so if he does not have any strong opinions against merging ordered and unordered comparators into single comparators, then let's do it.

I think with the new approach merging these two seems fine.

My only concern is that is may be relatively common for users to want to define such unordered types and having to define a compare method which returns Equals or Nothing instead of being able to define an equals method which simply returns True or False feels like adding a bit of unnecessary confusion.

BUT I don't think this is an issue, because we should be able to, at the library level, provide a helper make_comparator_for_unordered_type (name ofc to be revised) which could take an object with equals : a -> a -> Boolean and hash methods and 'convert' it into this comparator based form.

So I think at implementation level it is all good, and at the user-facing API level we may want to revise it later on, probably ideally once we use custom comparators a bit more and see what patterns will work best.

[enso-bot]

Pavel Marek reports a new STANDUP for yesterday (2023-02-28):

Progress: Refactoring code base such that Comparator.compare can return Nothing. Simplification of Vector.sort. It should be finished by 2023-03-03.

[enso-bot]

Pavel Marek reports a new STANDUP for yesterday (2023-02-28):

Progress: Use org.enso.base.CompareException instead of ClassCastException. Digging into a test failure that seems like there is difference between result from cached and uncached version of EqualsNode. Add debugging code, but is not?? It should be finished by 2023-03-03.

[enso-bot]

Pavel Marek reports a new STANDUP for today (2023-03-02):

Progress: Trying to fix some issues in my config that arised after Hubert's PR - sbt buildEngineDistribution fails in IntelliJ's builtin sbt console. I have no idea why. Resorting to the standard terminal so far. Fixing some issues on the PR. Struggling with exceptions in std-table. Comparing benchmarks to develop locally. So far, EqualsBenchmarks.equalsPrimitives is 20% faster. It should be finished by 2023-03-03.

[enso-bot]

Pavel Marek reports a new 🔴 DELAY for yesterday (2023-03-06):

Summary: There is 3 days delay in implementation of the Add support for partial ordering to Comparators (#5771) task.
It will cause 0 days delay for the delivery of this weekly plan.

Delay Cause: Taking into account my 1 day off on Friday.

[enso-bot]

Pavel Marek reports a new STANDUP for yesterday (2023-03-06):

Progress: Integrating review comments. Discussion about sorting and how to treat incomparable values. Fixing some tests. It should be finished by 2023-03-06.