Issue: SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 6)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

I feel we didn't give the MODIFIED variation of this proposal a fair
shake. We took GENERALIZED to X3J13 even knowing that it was the
most controversial of the two options we had. X3J13 voted it down,
not surprisingly to me. MODIFIED is considerably more conservative
and deserves consideration as a fall-back position.
 -kmp
-----
Issue:        SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS
References:   Sequences (pp245-261), COERCE (p51)
Category:     ENHANCEMENT
Edit history: 05-Feb-87, Version 1 by Touretzky (option GENERALIZED)
	      28-Apr-87, Version 2 by Pitman (add option MODIFIED)
              26-Oct-87, Version 3 by Masinter (remove MODIFIED)
              11-Nov-87, Version 4 by Masinter (respond to comments)
              05-Feb-88, Version 5 by Masinter
	      06-Oct-88, Version 6 by Pitman 
	       (revert to version 2, flush GENERALIZED option
	        -- which was rejected by X3J13 -- and resurrect MODIFIED)
Status:	      For Internal Discussion

Description:

  Common Lisp provides many useful operations on lists and vectors which
  don't apply to arrays.

  For example, one can FILL a vector with 0's, but not an array. One can
  REPLACE the contents of one vector with another, but one can't do this
  for arrays.  One can verify that EVERY element of a vector has some 
  property, but one can't do this for arrays. And so on.

  The programmer who wishes to use arrays instead of vectors must give up
  most of the useful tools CLtL provides for manipulating sequences, even
  though there is no intuitive reason why operations like FILL, REPLACE,
  and EVERY shouldn't work on arrays.

Proposal (SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS:MODIFIED):

  Common Lisp already provides a facility called "displaced arrays"
  which can be used to overlay one array on top of a portion of another,
  even if the two are of different ranks, so that the two share storage.
  Emphasize this as a way of explaining the behavior of sequence 
  functions on certain arrays.

  Modify the definition of COERCE to allow the coercion of an array to
  a vector and vice versa. In keeping with p51 of CLtL, it should be an
  error if the result type has a different number of elements than the
  object being coerced.

  Extend the definitions of sequence functions that either return their
  argument sequences, return sequences which are the same shape as their
  argument, or return non-sequences so that they also allow arrays iff
  their action is conceptually independent of the shape of the array.
  The affected functions are COUNT, SOME, EVERY, NOTANY, NOTEVERY,
  FILL, REPLACE, SUBSTITUTE, NSUBSTITUTE, and MAP.

  Expressly forbid arrays as arguments to other sequence functions.
  These other functions are LENGTH, ELT, FIND, POSITION, REDUCE, SEARCH,
  MISMATCH, REVERSE, NREVERSE, SORT, MAP, SUBSEQ, COPY-SEQ, CONCATENATE,
  MERGE, REMOVE, REMOVE-DUPLICATES, DELETE, DELETE-DUPLICATES.

Rationale:

  This proposal would expand rather than interfere with existing practice.

  Since displaced arrays are already part of Common Lisp, the cost of the
  proposed changes would be very low.

  If the change is not adopted, Common Lisp programmers who wish to use
  arrays will have two choices.  Either they must write nested DO loops
  every time they want to perform an array operation equivalent to FILL,
  REPLACE, etc., or else they can build displaced vectors by hand and
  pass them to the sequence functions when necessary.

  This proposal extends certain sequence functions in some interesting
  ways without committing us to a theory of how arrays and sequences
  relate that everyone may not be happy with right now.

Adoption Cost:

  This would involve a lot of changes to functions, but all of them
  presumably minor. The presence of displaced arrays in the language
  already guarantees that the internal storage format needed to back
  up these proposed changes is already in place.

Benefits:

  Users of arrays do not have to use home-grown utilities to duplicate
  functionality already primitively provided to users of arrays. The
  sequence functions become useful in a variety of new situations.

Conversion Cost:

  This change is `upward compatible.' User code should run unmodified.

Aesthetics:

  This extends certain existing sequence functions to allow arrays
  as arguments in a fairly non-controversial way, leaving aside the
  larger issue of whether and how to generalize the other sequence
  functions.

Current Practice:

  Probably no one implements this now.

Discussion:

  A more general version of this was introduced by Touretzky but
  it was rejected by X3J13.

  The members of the Cleanup committee expressed interest in the ideas 
  behind this proposal but weren't sure they could accept it in the
  proposed form. A rewrite to separate some of the issues more clearly
  was solicited. Rees suggested this subset of Tourtezky's proposal
  might be interesting.

  Note that the function REDUCE is in a gray area. Many of its uses
  are not position-dependent, but some are. The same argument might
  be made about FIND. If people felt strongly, these too could be
  extended either by fudging the conservative rule or by explicit
  special case(s), but they have been omitted to be conservative.