there is no correct way to use list-sort! or list-stable-sort!
William D Clinger 09 Mar 2016 12:31 UTC
SRFI 132 should not be allowed to go into final status until the problem
noted below is fixed.
All programs that call the list-sort! or list-stable-sort! procedures
are incorrect because there is no correct way to call either of those
procedures.
If you call one of those procedures for effect, ignoring its result,
then your call may act as a no-op because those procedures "are allowed,
but not required, to alter the cons cells of their arguments to produce
their results."
If you call one of those procedures for its result, then your call is
incorrect because "They return an unspecified value."
Olin's SRFI 32 did not have that problem, because Olin required the
"linear update" procedures to return the sorted result regardless of
whether they had performed any side effects.
So long as I'm commenting on SRFI 132, let me state my opinion that its
emphasis upon destructive operations is antiquated. With generational
garbage collectors, it's entirely possible that each of the destructive
operations allocates a transaction record needed to preserve invariants
that allow garbage to be collected without scanning the entire heap.
(Some generational collectors pre-allocate the storage needed for that
meta-data, while some allocate it on the fly.) The SRFI's claim that
destructive versions will run in constant space is therefore an empty
promise. In my opinion, implementations that use sophisticated garbage
collectors should be allowed to implement the procedures described by a
SRFI in whatever ways would be most efficient within those systems.
Will