Keyword style sequence functions

[David A. Moon <MOON5 at MIT-AI>]

Comments on Fahlman's Proposal for Keyword Style Sequence Functions for
Common Lisp of 16 January 1982

I think this is a good proposal and a step in the right direction.  There
are some problems with it, and also a couple issues that come to mind while
reading it.  I will first make some minor comments to get flamed up, and
then say what I really want to say.


- Negative comments first:

ELT and SETELT should be provided in type-specific versions.

My intuition suggests that MAP would be more readable with the result data
type before the function instead of after.  I don't really feel strongly
about this, but it's a suggestion.

I don't like the idea of flushing CONCAT (catenate) and making TO-LIST
allow multiple arguments, for some reason.

There is a problem with the :compare and :compare-not keywords.  For some
functions (the ones that take two sequences as arguments), the predicate is
really and truly an equality test.  It might be clearer to call it :equal.
For these functions I think it makes little sense to have a :compare-not.
Note that these are the same functions for which :if/:if-not are meaningless.
For other functions, such as POSITION, the predicate may not be a symmetric
equality predicate; you might be trying to find the first number in a list
greater than 50, or the number of astronauts whose grandmothers are not
ethnic Russians.  Here it makes sense to have a :compare-not.  It may actually
make sense to have a :compare keyword for these functions and a :equal
keyword for the others.  I'm not ecstatic about the name compare for this,
but I haven't thought of anything better.  This is only a minor esthetic
issue; I wouldn't really mind leaving things the way they are in Fahlman's
proposal.

Re :start and :end.  A nil value for either of these keywords should be
the same as not supplying it (i.e. the appropriate boundary of the sequence.)
This makes a lot of things simpler.  In :from-end mode, is the :start where
you start processing the sequence or the left-hand end of the subsequence?
In the Lisp machine, it is the latter, but either way would be acceptable.

The optional "count" argument to REMOVE and friends should be a keyword
argument.  This is more uniform, doesn't hurt anything, and is trivially
mechanically translatable from the old way.

The set functions, from ADJOIN through NSET-XOR, should not take keywords.
:compare-not is meaningless for these (unlike say position, where you would
use it to find the first element of a sequence that differed from a given
value).  That leaves only one keyword for these functions.  Also it is
-really- a bad idea to put keywords after an &rest argument (as in UNION).
I would suggest that the equal-predicate be a required first argument for
all the set functions; alternatively it could be an optional third argument
except for UNION and INTERSECTION, or those functions could be changed
to operate on only two sets like the others.  I think EQUAL is likely
to be the right predicate for set membership only in rare circumstances,
so that it would not hurt to make the predicate a required argument and
have no default predicate.

The :eq, :eql, :nequal, etc. keywords are really a bad idea.  The reasons
are:  1) They are non-uniform, with some keywords taking arguments and
some not.  See the tirade about this below.  2) They introduce an artificial
barrier between system-defined and user-defined predicates.  This is always
a bad idea, and here serves no useful purpose.  3) They introduce an
unesthetic interchangeability between foo and :foo, which can lead to
a significant amount of confusion.  If the keyword form of specifying the
predicate is too verbose, I would be much happier with making the predicate
be an optional argument, to be followed by keywords.  Personally I don't
think it is verbose enough to justify that.

There are still a lot of string functions in the Lisp machine not generalized
into sequence functions.  I guess it is best to leave that issue for future
generations and get on with the initial specification of Common Lisp.


- Negative comments not really related to the issue at hand:

"(the :string foo)".  Data type names cannot have colons, i.e. cannot be
keywords.  The reason is that the data type system is user-extensible, at
least via defstruct and certainly via other mechanisms such as flavors in
individual implementations and in future Common extensions.  This means
that it is important to be able to use the package system to avoid name
clashes between data types defined by different programs.  The standard
primitive data type names should be globals (or more exactly, should be
in the same package as the standard primitive functions that operate
on those data types.)

Lisp machine experience suggests that it is really not a good idea to have
some keywords take arguments and other keywords not take arguments.  It's a
bit difficult to explain why.  When you are just using these functions with
their keywords in a syntactic way, i.e. essentially as special forms, it
makes no difference except insofar as it makes the documentation more
confusing.  But when you start having programs processing the keywords,
i.e. using the sequence functions as functions rather than special forms,
all hell breaks loose if the syntax isn't uniform.  I think the slight
ugliness of an extra "t" sometimes is well worth it for the sake of
uniformity and simplicity.  On the Lisp machine, we've gone through an
evolution in the last couple of years in which keywords that don't take
arguments have been weeded out.

I don't think much of the scheme for having keywords be constants.  There
is nothing really bad about this except for the danger of confusing
novices, so I guess I could be talked into it, but I don't think getting
rid of the quote mark is a significant improvement (but perhaps it is in
some funny place on your keyboard, where you can't find it, rather than
lower case and to the right of the semicolon as is standard for
typewriters?)


- Minor positive comments

Making REPLACE take keywords is a good idea.

:start1/:end1/:start2/:end2 is a good idea.

The order of arguments to the compare/compare-not function needs to be
strictly defined (since it is not always a commutative function).  Presumably
the right thing is to make its arguments come in the same order as the
arguments to the sequence function from which they derive.  Thus for SEARCH
the arguments would be an element of sequence1 followed by an element of
sequence2, while for POSITION the arguments would be the item followed
by an element of the sequence.

In addition to MEMQ, etc., would it be appropriate to have MEMQL, etc.,
which would use EQL as the comparison predicate?

MEMBER is a better name than POSITION for the predicate that tests for
membership of an element in a sequence, when you don't care about its
position and really want simply a predicate.  I am tempted to propose that
MEMBER be extended to sequences.  Of course, this would be a non-uniform
extension, since the true value would be T rather than a tail of a list (in
other words, MEMBER would be a predicate on sequences but a semi-predicate
on lists.)  This might be a nasty for novices, but it really seems worth
risking that.  Fortunately car, cdr, rplaca, and rplacd of T are errors in
any reasonable implementation, so that accidentally thinking that the truth
value is a list is likely to be caught immediately.


- To get down to the point:

The problems remaining after this proposal are basically two.  One is that there
is still a ridiculous family of "assoc" functions, and the other is that the
three proposed solutions to the -if/-if-not problem (flushing it, having an
optional argument before a required argument, or passing nil as a placeholder)
are all completely unacceptable.

My solution to the first problem is somewhat radical: remove ASSOC and all
its relatives from the language entirely.  Instead, add a new keyword,
:KEY, to the sequence functions.  The argument to :KEY is the function
which is given an element of the sequence and returns its "key", the object
to be fed to the comparison predicate.  :KEY would be accepted by REMOVE,
POSITION, COUNT, MEMBER, and DELETE.  This is the same as the new optional
argument to SORT (and presumably MERGE), which replaced SORTCAR and
SORTSLOT; but I guess we don't want to make those take keywords.  It is
also necessary to add a new sequence function, FIND, which takes arguments
like POSITION but returns the element it finds.  With a :compare of EQ and
no :key, FIND is (almost) trivial, but with other comparisons and/or other
keys, it becomes extremely useful.

The default value for :KEY would be #'ID or IBID or CR, whatever we call
the function that simply returns its argument [I don't like any of those
names much.]  Using #'CAR as the argument gives you ASSOC (from FIND),
MEMASSOC (from MEMBER), POSASSOC (from POSITION), and DELASSOC (from
DELETE).  Using #'CDR as the argument gives you the RASS- forms.  Of
course, usually you don't want to use either CAR or CDR as the key, but
some defstruct structure-element-accessor.

In the same way that it may be reasonable to keep MEMQ for historical
reasons and because it is used so often, it is probably good to keep
ASSQ and ASSOC.  But the other a-list searching functions are unnecessary.

My solution to the second problem is to put in separate functions for
the -if and -if-not case.  In fact this is a total of only 10 functions:

	remove-if	remove-if-not	position-if	position-if-not
	count-if	count-if-not	delete-if	delete-if-not
	find-if		find-if-not

MEMBER-IF and MEMBER-IF-NOT are identical to SOME and NOTEVERY if the above
suggestion about extending MEMBER to sequences is adopted, and if my memory
of SOME and NOTEVERY is correct (I don't have a Common Lisp manual here.)
If they are put in anyway, that still makes only 12 functions, which are
really only 6 entries in the manual since -if/-if-not pairs would be
documented together.