SRFI 32

["Paul Steckler" <steck@xxxxxxxxxxx>]

Olin,

> Could y'all make a pass through
>     http://srfi.schemers.org/srfi-32/
>     (sorting library)
> and
>     http://srfi.schemers.org/srfi-32/
>     (integer bitops)
> and make sure
>   - No bad mistakes
>   - Y'all will be willing to adopt this?

I've just read through the SRFI-32 draft and scanned the archive of the
email discussion list.

Maybe I'm near-sighted, but where is the reference implementation?
David Feuer asked the same question on the discussion list, and I didn't
see a response.

I suspect that the LET-OPTIONALS macro is roughly equivalent to PLT's
opt-lambda -- I'd have to see the reference implementation to be sure.

High-level comment: this SRFI is well-organized and useful.  I think
it's up to Matthew whether to put this in MzScheme, but I'd be happy to
see it there.

Typos and quibbles:

  - "an SRFI" -> "a SRFI" (? depends on how you pronounce "SRFI" :-))

  - in the section on types of parameters and return values, it uses the
word "unspecified"; in the descriptions of procedures, this mutates to
"unspecific"

  - under `sort-lib', in the type for `vector-delete-neighbor-dups!',
the return value is named end'.  Hmmm, I'd avoid using a quote there,
and name it end2.  This name is used a couple of other places, I think.

  - in the description of START and END, `v' is lower-case in
(vector-length v), then upper-case in `where V ...'.  But this text may
be redundant, since the same setup is already described in the section
"All vector operations accept optional subrange parameters".

  - there is a general inconsistency in the capitalization of procedure
names, or maybe I don't understand why they're in upper-case in certain
places, and lower-case in others

  - in the snippet of code that follows "The definition is rather
different, given a <= comparator:", you should transpose `x' and `y' for
one of the arguments to `and'

  - in the type for `vector-merge!', the first optional argument is
given as `start', but later mentioned as `START0' (inconsistent
capitalization? as well as the `0')

  - `list-merge!' is described as "iterative, not recursive".  Hmmm,
that's a bit confusing to me -- I'd just write "iterative".
  	  	
  - I don't understand the comment on "Pure list merge sort" that begins
"and possibly better ..." and what the "above" refers to.

  - it's stated that the `LIST-SORTED?' function *will* return false
given a <= comparator and a list with adjacent equal elements.  I think
that depends on the semantics of `LIST-SORTED?' (the intended semantics
is described later in the SRFI).  Maybe "may" is a better word choice
here, before the reader has seen that semantics.

  - after a lengthy discussion of why < is better than <=, there's a
reference to Common Lisp's similar choice.  I'd put that before your own
explanation, and say something like "While I don't know CL's reasons for
that choice, here are my own."

 - `vector-delete-neighbor-dups{!}' is described twice, as part of
sortlib and delndup-lib.  Also, the description that it implements a
linear-time algorithm appears twice (well, the second time, that also
applies to the list deletion procedures).

A more substantive comment:

  - I don't understand why there are four vector sort libraries.
Presumably, there's not a lot of code there.  Couldn't they go into just
one library?

On the order of arguments issue: I'd be in favor of putting the
procedure argument in front of list/vector data, uniformly.  If this
SRFI is widely-adopted, most of the procedure names will be new in most
implementations.  So you may as well do the right thing now, rather than
have to live with a bad decision for years to come.  It also helps to
distinguish Scheme from C, whose quicksort() puts the comparator last.
:-)

I think that the binary search procedure probably belongs elsewhere.  I
don't know if there's a SRFI that deals with search trees, etc., but
that's where I'd put it.

I hope you find these comments useful.

- -- Paul