Email list hosting service & mailing list manager

there is no correct way to use list-sort! or list-stable-sort! William D Clinger (09 Mar 2016 12:31 UTC)
more corrections for SRFI 132 William D Clinger (10 Mar 2016 17:06 UTC)
Re: more corrections for SRFI 132 William D Clinger (10 Mar 2016 19:37 UTC)
Re: more corrections for SRFI 132 William D Clinger (10 Mar 2016 20:32 UTC)
benchmarking the SRFI 132 reference implementation William D Clinger (10 Mar 2016 23:20 UTC)
Re: more corrections for SRFI 132 William D Clinger (12 Mar 2016 03:07 UTC)
Re: more corrections for SRFI 132 Alex Shinn (12 Mar 2016 23:26 UTC)
Re: more corrections for SRFI 132 John Cowan (13 Mar 2016 22:02 UTC)

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