I've just read through the SRFI-32 draft and scanned the archive of the
email discussion list.
Great review, Steck. Thank you very much!
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 think I responded. I haven't released the ref implementation. I still
need to clean up one of the routines, and I have been putting my SRFI
time into the discussion & spec.
- "an SRFI" -> "a SRFI" (? depends on how you pronounce "SRFI" :-))
- 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 section on types of parameters and return values, it uses the
word "unspecified"; in the descriptions of procedures, this mutates to
"unspecific"
- `list-merge!' is described as "iterative, not recursive". Hmmm,
that's a bit confusing to me -- I'd just write "iterative".
All fixed.
- 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.
I kinda like END'.
- 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
I need to make a pass to make capitalisation consistent.
- 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')
I replaced START0/END0 with START/END uniformly.
- I don't understand the comment on "Pure list merge sort" that begins
"and possibly better ..." and what the "above" refers to.
I changed "better" to "O(n)," producing
Stable and fast -- O(n lg n) worst-case, and possibly O(n), depending
upon the input list (see above).
"Above" means the three paragraphs *immediately above*.
- 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.
No, the semantics is fixed, so "may" isn't the right word. It *will*.
Maybe I should reorder the text.
- 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."
I don't really *have* any good reasons for using <, other than it is the
common practice. That section *doesn't* say one is better than the other,
just that they are quite different, and what the implications of that
difference are.
- `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).
Yeah, I know, and you are correct to push me to do something about this
redundancy. I will reflect on this.
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?
I don't see why you should have to link in six different sort libraries
just to get heapsort.
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.
:-)
This seems to be the consensus, to my pleasant surprise. I'm waiting to
hear from a few more implementors.
I hope you find these comments useful.
Very. Thanks. May I forward your msg to the SRFI mailing list / archive?
-Olin