Re: Adjustable and displaced arrays

[Glenn S. Burke <GSB@MIT-MC>]

It sounds like NIL implements complex arrays in a somewhat similar
manner to Spice Lisp.  However, in the general case, the complex array
header might have to point to another complex array header.  As a
result an AREF might have to iterate to find the eventual data vector.
Only in the case where none of the involved arrays (other than the
outermost) are adjustable can the data vector be "cached" as your
implementation does.

For instance.  
	(setq c (make-array '(5 5) :adjustable t))
C is a complex array header, whose displaced-to field (like your data
vector) is a simple vector 25 long, and whose displaced-index-offset
field holds 0.
	(setq b (make-array 20 :displaced-to c :displaced-index-offset 5))
B is a complex array header, whose displaced-to field is C, because C is
adjustable, and its data vector might get thrown out and replaced by a
new one.
	(setq a (make-array '(3 3) :displaced-to b :displaced-index-offset 4))
A is a complex array header, whose displaced-to field is C.  It is NOT
B, because B is not adjustable, so can be optimized out.  Its
displaced-index-offset field is 4, which was obtained by adding its
own with B's.

(aref A i j) operates by computing a row-major-order index into A,
using the dimensionality of A.  Then (because this is a complex array)
the displaced-index-offset (9) is added to this, and that is used as a
row-major-order index into its displaced-to array, C.  C is itself a
complex array, so the process iterates once more.  C's
displaced-index-offset is 0 and its displaced-to happens to be just a
simple vector.
--------------
Moon and i discussed this specification some well over a year ago,
because i was somewhat disturbed at the efficiency penalty in some of
the displacement.  We pretty much decided that in spite of the hair
needed, this model of array displacement was reasonable, and at least
simple arrays can be crunched pretty efficiently.  (The point being
that i was somewhat put off by the implementation necessary.)  In NIL,
the sequence functions operate internally by reducing a sequence to a
simple sequence and an offset, and then crunch on the simple sequence.
So, for instance, doing REPLACE on two strings, no matter how
adjustable or displaced, will eventually use the vax MOVC3
instruction, as implemented by a primitive which moves "bytes" from
one simple binary data object to another (the same thing works on
bignums).

The one thing i do NOT like about the specification is how elements
are preserved by adjust-array.  The replacement of those things with
matching indices is pretty random, and pretty inefficient to boot.  It
should just preserve the row-major-order data insofar as that is
possible (truncating, or extending with some initial-element or
"undefined" value, depending on whether the total-size is being
decreased or increased).