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

On Sat, Nov 12, 2011 at 08:02:43PM -0800, Steve Haflich wrote:
> Oliver Kullmann <O.Kullmann at swansea.ac.uk> wrote:
> 
>    Obviously, I am referring to the MAXIMA documentation:
> 
> (I'm in danger of acting like a troll, which is not my intention.
> Apology in advance.)
>

I made not only the observation, that the Maxima documentation
is unusable, but I also proposed how to fix it.
And this in a way, which establishes what should always be the
goal: not to refer to some implementation, but to a (relatively)
well-defined semantics, independent of any implementation.

The productive answer then would be to say what the intended semantics is,
and to investigate the actual semantics, which results then in an improvement
of the documentation at least, and perhaps even of the code.

> This appears to be the definition of maxima sort:
> 
>   (defmfun $sort (l &optional (f 'lessthan))
>     (let ((llist l) comparfun bfun ($prederror t))
>       (unless ($listp llist)
> 	(merror (intl:gettext "sort: first argument must be a list; found: ~M") llist))
>       (setq llist (copy-list (cdr llist))
> 	    comparfun 
> 	    (mfunction1 (setq bfun (getopr f))))
>       (when (member bfun '(lessthan great) :test #'eq)
> 	(setq llist (mapcar #'ratdisrep llist)))
>       (cons '(mlist) (sort llist comparfun))))
> 
> Despite the murk of the Maxima documentation (which probably predates
> the ANS) all the actual sorting is performed by the Common Lisp sort
> function.

Even if it just would call the Lisp sorting function, this would not guarantee
anything: the question is then about the environment (the term system) and about
the components involved. Both are not well-defined (they have only an operational
meaning in the Maxima-world, subject to permanent adaptation on practical grounds),
and thus the need to specify the *contract*.

>  (Significant exception is that Maxima sort is
> non-destructive, which CL sort is allowed to be destuctive.)  So if you
> want to know how sort behaves in these various edge cases with a
> conforming ANSI CL, the ANS is where you'd have to look.
> 
> BTW, the ANS informally defines sort tability.  The function cl:sort
> does not guarantee stability, which cl:stable-sort does.  On some
> implemnentations, perhaps most. these functions are the same.
> 
> (Yes, in a more-perfect world, Maxima documentation would be accurate,
> complete, and current.  If so, then this world must fail to be at least
> one of the above.  I hope this won't come as a shock to anyone.)
> 

Sounds like the reaction of a current politician to me: when pointing
out an error, reacting with cynism that the world is not perfect,
and only a fool could expect otherwise.

I always hoped (and still do so) that Maxima is part of mathematics,
and that whatever happens, when speaking to a mathematician the
least common denominator is always truth (and its simpler cousine,
correctness).

> So the current question could be resolved with one of these three choices:
> 
> 1) Rewrite $sort to conform to the Maxima documentation, in a way that
>    is portable to all ANSI-conformant implementations.
> 
> 2) Rewrite the documentation to agree (other than the copy-list) with
>    the ANSI definition.
>

This doesn't include the obvious thing to do, to *correct* the Maxima
documentation (this is also the easiest thing to do).
 
> 3) Ignore this minor discrepency for the time being, because more
>    important issues require atention in Maxima source and documentation.
> 
> I guess (3) could be essentially a troll, but these choices offerred
> sincerely.  Sorry about that.

I fear that (3) might be the preferred solution, given the unwillingness to
engage with the semantics (I started with a semantical question, and proposed
an answer, but yet the only reaction where the Lisp-mantra "read the code"
and referral to some documents (which can't contain the answer)).

Before writing my request, I wouldn't have imagined that "Ignore this" would
have been considered. For a mathematician, correctness is the ultimate barrier,
and pointing out an error, a minor in a lecture script, a major in a paper,
must always cause the immediate desire to fix it.

Learning from that experience, and thinking through my past experiences with
Maxima, I developed now a little theory: there is a kind of psychotic split
in Maxima (and thus in its community), into what is "mathematical" about
Maxima, and what is "not" (the latter being some kind of dark subconsciouness).
Things relating to the perceived mathematical side can be discussed in
therms of truth and correctness, and this is widely done on the mailing list.
Things relating to the non-mathematical side can and must not be considered
in terms of truths, perhaps better are not discussed (mentioned) at all.
One sees a degeneration into a hackish attitude ("read the code" or "read
that document", without discussion of what's in the document --- where
programming standards are notoriously vague), and a rather strong
emotional "disavowal".

In a sense "of course" one has to take also my position into accout,
as a "computer scientist": from that point of view "of course" the
underlying programming infrastructure must be thought of in terms of
truth and correctness, is a mathematical construct in the same sense
as numbers and polynomials are.
This shows also in our Maxima code (just counted, out of interest:
about 700 files with total 80000 lines), where in our context
the sort-function is much more important than, say, the solve-
or the defint-function.

I guess now that the above interpretation won't change much.
So well, then I assume that my interpretation (that of the strict
weak order) is basically correct (at least for our practical purposes,
where terms are always simple). Perhaps we write our own sorting-functions
(at Maxima-level).

Nevertheless, thanks for the time spent.

Oliver