[Density?] SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 4)

[Jon L White <edsel!jonl@labrea.stanford.edu>]

There's one sense in which I share Fahlman's reluctance to accept this idea.
It seems to presume that underlying any array whatsoever is a simple
vector of elements that represent the array in dense, row-major order.

In fact, Lucid Common Lisp does just about that (as all the others do too, 
I suspect!).  There is even an "internal" function named 
    'underlying-simple-vector'
to fetch that simple vector.

But the problem is that the simple-vector needn't be "dense" in elements 
of the array!  The existence of the function array-row-major-index doesn't 
require, for example, that there be no gaps between the rows.  [The 
definition on CLtL, p293 is only one possibility --  the one for dense 
underlying simple-vectors.]   Rather, it only requires a 1-1 mapping
between the integers {0,1,...(1- <array-total-size>)} and the full set of
multi-dimensional indices.

Your characterization of the relation between arrays and sequences exhibits
the bias towards dense, underlying simple vectors:
    Let me restate the basic intuition one more time.  A sequence is like  
    a string of beads.  If you stretch it out straight you have a list or 
    vector.  If you fold it up in various ways using COERCE or MAP, you 
    have an n-dimensional array which you can access with AREF, which is 
    not a sequence function.  The beads still sit on the string in the same 
    order, and the sequence functions still give the same result no matter 
    how you fold the string of beads.  This property is guaranteed by the 
    existing commitment in CLtL to storing array elements in row-major order.
"Ordering" may be guaranteed by row-major order; but "density" isn't.

Not even the existence of :displaced-index-offset guarantees "density"
(especially if it's value is typically row-aligned anyway), although
I admit that you won't get portable results if you can't assume density.

Until it is decided that a particular implementation of multi-dimensional
arrays is *standard* (as opposed to the functional interface to multi-
dimensional arrays), then Common Lisp implementations should be free
to store the rows of a matrix in any random way that is convenient to
the storage layout of that implementation (e.g., "sparse" storage?).

I must confess that on "stock" hardware, it would be rather inefficient not
to use the dense, row-major odering.  But closing off other implementation 
options seems premature, to me; at least until there is evidence of a *great* 
win to be had by doing so.


-- JonL --