inconsistent definition of "sort" (and what about stability?)

On Sat, Nov 19, 2011 at 09:46:47PM -0500, Stavros Macrakis wrote:
> Argh! ?Sorry for jumping so quickly to (incorrect) conclusions.
> 
> I don't know why, but I assumed that "<=" was an acceptable predicate for
> 'sort'.

The current documentation suggests in the first part that <= is to be used.
(So in some early parts of our library we used "<="; upon reflection
I decided that it must be "<", which we used that from then on, and I
created a todo for this inconsistency in the Maxima-documentation,
which wasn't acted upon until finally when using also Sbcl we got
errors.)

> 
> Let me propose wording that reflects your corrections:
> 
> ?-- Function: sort (<L>, <P>)
> ?-- Function: sort (<L>)
> 
> Sorts a list <L> using a predicate function <P> of two arguments which defines
> a strict total order. ?If <P>(a,b) is true, then a will appear before b in the
> result. ?If neither <P>(a,b) nor <P>(b,a) is true, then a and b are equivalent,
> and will appear in the same order as in the input (that is, 'sort' is a stable
> sort).
> 
> If both P(a,b) and P(b,a) can be true, then P is not a valid sort predicate,
> and the result is undefined, though 'sort' may not signal an error. ?If P(a,b)
> is not true or false for some a and b, sort signals an error.
>

As Steve already pointed out, that P(a,b) must be true or false is a prerequisite,
and without it the computation is undefined, but we can not make guarantees
about the occurrence of an error.

Typically for specifications of programs one uses only positive conditions,
what happens for sure if the prerequisites are met. It is rare, and typically best
to be avoided, to make guarantees in case the prerequisites are not fulfilled.

For example in our case, if we define
cmp(x,y) := if x=1 and y=3 then 7 else true;
then
sort([1,2,3],cmp);
at least under Ecl works, i.e., returns the correct result.
(While cmp(x,y):=7 will result in "Unable to evaluate predicate 7".)

So, at least if the documentation should be easy-going, I would
just specific what must hold, and not what will happen in the
negative case.

If Maxima would be used to steer my nuclear power station or your
airplane, then one needed also to state something about
the negative case: "undefined behaviour" (the computer might melt
down when a bad P is provided (sending out first tons of spam)), or,
on the other end, a false result might be returned but otherwise it is guaranteed that
the system is still perfectly working.
It is hardly possible to make the second guarantee (P might have
side effects).
And given the nature of Maxima, and that it happens not to steer my
nuclear power station, I propose just to say something about the
prerequisites.

That is actually a bit problematic. I would prefer to use "strict weak
ordering". That would be found when making an Internet search. For "strict total
order" we get http://en.wikipedia.org/wiki/Total_order, and there
it says (which I think correctly reflects usage in mathematics and computer
science), that a strict total order involves the use of "=".
However we do not need "=" for sorting --- the point of "strict weak ordering"
is to avoid to have "=" as a prerequisite (that is, actually *two* predicates
would be involved), but to derive equivalence between objects implicitly.

And actually it would be good to give early an example of "<" (perhaps simply
stating "< can be used, but not <=").

So my favourite paragraph for the conditions on P would be (something like that):

---
P should fulfil the conditions of a strict weak ordering (so "<" may
be used, but not "<=").
---

Then the above two paragraphs could be replaced by the following single paragraph: 

---

Sorts a list <L> using a predicate function <P> of two arguments which defines
a "strict weak ordering" (so "<" may be used, but not "<=").
If <P>(a,b) is true, then a will appear before b in the
result. ?If neither <P>(a,b) nor <P>(b,a) is true, then a and b are equivalent,
and will appear in the same order as in the input (that is, 'sort' is a stable
sort).

---

On the one hand, we now give some precise information (that on "strict weak
ordering", which can be found easily on the Internet, and is through
the history of computation strongly associated with sorting).
And on the other hand, that little piece of information the user
perhaps just wants, namely "Just tell me, < or <= ?!?", occurs
early enough. (I think documentation should give quick answers
to common use-cases. There should be no need to derive something.)

Finally, if I understand Steve correctly, then he suggests not to make
such assumptions on P, which might be unnecessarily strong, but just
to follow the Lisp-spirit --- use whatever P you wish, if it happens
to establish an order. A main problem is that this depends on the
sorting algorithm used. I would strongly prefer to give an explicit
definition (so create a little world of meaning, so to speak).
The user might still correctly infer that for example P(a,b) is only
involved on elements found in the list to be sorted ...


> The predicate function may be specified as the name?of a function (e.g.
> 'orderlessp), a quoted binary infix operator (e.g. "<"), or as a
> `lambda'?expression (e.g. lambda([a,b],a[1]<b[1]) ).
> 

But the fact, that orderlessp is the default in case P is not given, should be mentioned.

> The sorted list is returned as a new object; the argument <L> is?not modified.
> 

Oliver