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

• To: labrea!Dave.Touretzky%C.CS.CMU.EDU@labrea.stanford.edu
• Subject: [Density?] SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 4)
• From: Jon L White <edsel!jonl@labrea.stanford.edu>
• Date: Sat, 28 Nov 87 05:27:53 PST
• Cc: labrea!cl-cleanup%sail@labrea.stanford.edu
• In-reply-to: Dave.Touretzky@C.CS.CMU.EDU's message of Mon 16 Nov 87 01:57:08-EST <12350990498.13.TOURETZKY@C.CS.CMU.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 --

```