Subject: Re: bug#69709: `sort` interface improvement and universal ordering predicate

From: Mattias Engdegård <[email-masked]>
Date: Wed, 20 Mar 2024 20:01:39 +0100

Now the origin/scratch/sort-key branch contains a draft proposal. Summary:

* Our timsort has now the key function handling from the original code (ported to Emacs).
* New keyword-based calling convention for `sort`. The old one is still there and works as before.
* New `value-less-p` universal ordering predicate.
* No manual updates yet.
* NEWS entries are there.
* `sort-on` is now completely superfluous (slower, less convenient) and should be removed.
* Performance seems fine from initial tests. More comprehensive benchmarking will be done.

Some things that I haven't made up my mind about:

* Better name for `value-less-p`:
    value<
    {generic,universal,standard,lisp}{-less-p,<}

* Maybe the :destructive keyword be called :inplace or :in-place instead? Shorter, less violent.

* Should the :reverse keyword be called :reversed or even :descending ?

* Internally, `value-less-p` computes a 3-way result; it would be easy to expose that to Lisp as `value-compare`, could be useful.

* The design space for `value-less-p` is vast: the current code is an attempt at intuitive semantics without too much complexity. There are also good (and bad) arguments for:

- heterogeneous comparisons (compare objects of different types)
- total order on all values
- strict agreement with `equal`
- automatic call-out to user-defined comparison functions for classes that have them