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

On Sat, Nov 19, 2011 at 07:46:26PM -0500, Stavros Macrakis wrote:
> On Sat, Nov 19, 2011 at 18:32, Robert Dodier <robert.dodier at gmail.com> wrote:
> 
> Comments in line:
> ?
> 
>     ?-- Function: sort (<L>, <P>)
> 
>     ? ? Sorts a list <L> according to a predicate `P' of two arguments,
>     ? ? such that `<P>(<L>[k + 1], <L>[k])' is `false' for any two
>     ? ? successive elements.
> 
> 
> I'm afraid this definition is incorrect. ?After all,?L= [1,1] is sorted
> according to "<=", but P(L[2],L[1]) is true. ?And what is the purpose of saying
> "any two successive elements" when we already have L[k+1] and L[k]?? Also, "L"
> is being used in the same sentence to mean two very different things: the input
> list and the output list. ?All in all, very confusing. ?Why not something
> simpler like:
>

No, the definition is correct: "<=" can not be used by "sort", but yields
undefined behaviour.

How to construct a good example, to demonstrate this?
The best I'm aware of at the moment is to show that different Lisp's
yield different results:

cmp(x,y):=is(first(x) <= first(y));
sort([[1,1],[1,2]],cmp);

Ecl yields
[[1,1],[1,2]]
Sbcl yields
[[1,2],[1,1]]

However with the correct definition
cmp(x,y) := is(first(x) < first(y));
both yield
[[1,1],[1,2]]

> ? ? Sorts a list <L> using an ordering function P of two arguments, which
> defines a "less than or equals" relation. ?More precisely, if P(a,b) and P(b,a)
> are both true, then the order of a and b remains the same as in the input
> ("stable sort"). ?Otherwise, a comes before b if P(a,b).
> 

If both P(a,b) and P(b,a) are true, then we have undefined behaviour.
?
> (This also makes the discussion of stable sort below unnecessary.)
> 
> 
>     ?The predicate may be specified as the name
>     ? ? of a function or binary infix operator, or as a `lambda'
>     ? ? expression. ?If specified as the name of an operator, the name is
>     ? ? enclosed in "double quotes".
> 
> 
> Adding an example might help: e.g. "<".?
> 

Whatever you do, one can not have "<=" and "<" at the same time.
?
> 
>     ? ? It is assumed the predicate <P> is a strict total order on the
>     ? ? elements of <L>.
> 
> 
> No, it is assumed that P is total, but not strict -- i.e. it is like <=, not <.
> ?(Otherwise we wouldn't have to specify stability.)
>

Yes, it is strict. Sorting always considers strict orders. For strict orders
equivalence x~y is defined as not(x<y) and not(y<x). Stability concerns
equivalent elements.

> 
>     ?If not, `sort' might run to completion without
>     ? ? error, but the result is undefined. ?`sort' complains if the
>     ? ? predicate evaluates to something other than `true' or `false'.
> 
> ?
> Instead of "complains", how about "gives an error"? ?"Complains" could mean
> "prints a warning".
> ?
> 
>     ? ? `sort' is a stable sort: if two elements <x> and <y> are
>     ? ? equivalent in the sense that `<P>(<x>, <y>)' and `<P>(<y>, <x>)'
>     ? ? are both `false', then the relative order of <x> and <y> in <L> is
>     ? ? preserved by `sort'.
> 
> 
> No, this is incorrect. ?If P(x,y) and P(y,x) are both false, then P is not a
> total order (strict or otherwise), and all bets are off.
> 

This is called a "strict weak order", and is fully sufficient for all
sorting purposes.

If your statement above would be true, then sort([1,1]) would be undefined ---
given that orderlessp is used!

orderlessp(1,1);
  false?

> 
>     ? ? `sort (<L>)' is equivalent to `sort (<L>, orderlessp)'. ?That is,
>     ? ? the default sorting order is ascending, as determined by
>     ? ? `orderlessp'. ? ?All Maxima atoms and expressions are comparable
>     ? ? under `orderlessp'.
> 

Oliver