Adjustable and displaced arrays (summary)

[Fischer.pa@Xerox.ARPA]

Here is "my understanding" of adjustable and  displaced arrays.

This is an "unproofed by the other participants" summary of a discussion
between: Moon@STONY-BROOK.SCRC.Symbolics.COM, fischer.pa,
Fahlman@CMU-CS-C, Greek@DEC-HUDSON, RAM@CMU-CS-C, GSB@MIT-MC

A simple implementation example of displaced arrays: a displaced array
keeps a pointer to the actual array that it is displaced to.  Accesses
to such a displaced array must look down the chain of displacements to
make a reference.  It is important that the behavior of this technique
be preserved.  It becomes critical when, for instance, an array
somewhere in the chain of displacements is handed to adjust-array and
given a new displacement.  Accesses must then follow the new chain.
Your mileage may vary, eg you can optimize this any way you please, most
commonly by encaching information in the array "header" about the
ultimate address and offset of the block of data being referenced.  A
scheme to update the encached information is then called for (possibly
for the whole chain of displaced arrays).

adjust-array can alter the dimensionality and contents (or displacement)
of an array.  It doesn't move elements around to preserve order.  It
only copies elements if the array they are part of enlarges or shrinks*.
Here is an outline of the cases adjust-array handles:

If a displacement is given as an argument
  then
	set dimensions
	set displacement
else if the old array was displaced
  then
	copy the elements (shrink, enlarge or same size**)
	set new dimensions
else if new dimensions have same linear size as old
  then
	simply set dimensions
else
	; new dimensions with different linear size
	copy elements to new size block.

Bear in mind that initial-element, initial-contents, and displaced-to,
are mutually exclusive.  Completely new contents may be specified by
initial-contents.  Gaps in a newly enlarged array may be initialized
with initial-element.

[*Note: CLtL specifically does not specify when an error should be
signalled if adjusting an array causes another array displaced to it to
have invalid linear size.  This could be done at adjust-array time or
aref time.  Seems to be your choice.]

[**Note: this interpretation of the case where a displaced array loses
its displacement is made arbitrarily. It is unclear from the text of
CLtL whether the elements should be copied into a new block to remove
the old displacement, or whether a blank storage block should be
created.  The former seems somewhat more reasonable.]

(ron)