[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*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 --

**Follow-Ups**:**[Density?] SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 4)***From:*David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>

**References**:**Re: SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 4)***From:*Dave.Touretzky@C.CS.CMU.EDU

- Prev by Date:
**Re: Issue: PROCLAIM-LEXICAL (Version 5)** - Next by Date:
**Issue status** - Previous by thread:
**Re: SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 4)** - Next by thread:
**[Density?] SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 4)** - Index(es):