Adjustable and displaced arrays

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

Perhaps I can clarify one or two points in this discussion.

    Date: Wed, 22 May 1985  23:56 EDT
    From: Rob MacLachlan <RAM@CMU-CS-C.ARPA>

    I am somewhat confused about the interaction between array adjustment
    and displacement.

    In CLTL p298:

	Note that if the array a is created displaced to array b and
	subsequently array b is given to adjust-array, array a will still
	be displaced to array b; the effects of this displacement and the
	rule of row-major storage order must be taken into account.

    What is this trying to say?  Is this a warning to the user or a threat
    to the implementor?  The obvious interpretation of this statement
    seems to require that all non-simple arrays contain a list of all the
    other array headers that share the same data so that they can be fixed
    up when the array is adjusted.  The answer that you stick in a
    forwarding pointer is not acceptable.

I can't tell what you mean by your last two sentences, but if you encache
information about array b inside of array a, you must arrange one way or
another to discover when that cache is invalid.  An alternative to encaching
is to examine array b on every access to array a.  We use a combination of
both techniques; normal array accesses to array a examine array b, but a
tight array processing loop can use a declaration to get the array decoding
moved outside of the loop.  This encached information is automatically
updated if any array is adjusted (our hardware can do with this without
taking any extra time; the validity check for the encached information
consists of comparing two numbers, one of which increments every time an
array is adjusted, and is overlapped with memory access time).  In a system
that doesn't allow multiple processes, you could probably get away without
any provision for cache updating if you require the user not to do any
array adjustment inside his inner loop.

    The statement in the manual also doesn't answer the question of what
    happens to array b if array a is adjusted.  Is it legal or meaningful
    to have arrays which are both displaced to another array and
    adjustable?  What are the semantics of adjusting such an array?

The answer is that it is extremely straightforward.  Adjusting array a
never affects array b in any way.  Adjusting a displaced array never moves
any data elements around in storage; it simply changes the dimensions,
displaced-to, and/or index-offset of the displaced array.  It sounds like
the manual needs to be improved.

    Date: Thu, 23 May 85 09:57:23 EDT
    From: greek@DEC-HUDSON

    We were so confused about the problem of adjusting displaced arrays,
    we simply don't allow it in VAX LISP.  I'd sure appreciate some
    thoughts on the matter myself.

See above; adjusting displaced arrays is much easier than adjusting
ordinary arrays.

    Date: Tue, 28 May 85 11:21:20 EDT
    From: greek@DEC-HUDSON

    Erf!  I certainly should have objected to the incredible hair needed
    to implement adjustable arrays, particularly those which are displaced,
    back when we specified them.  However, I'd like to object now.

    I'd like to see a list of the uses people make of displaced and
    adjustable arrays.  Maybe there are only two or three real features
    that people use, and we could restrict ourselves to those.  I looked
    around here at DEC, and found exactly two uses:

    1.  Make an array bigger.  Obviously this could be done with MAKE-ARRAY
	and REPLACE.

This is not obvious at all!  Suppose there are multiple references to the
original array; how do they get updated to refer to the new copy?  That
issue is the whole reason why adjustable arrays exist.

    2.  Linearize a multidimensional array so that row-major references
	can be done.  This is useful, but an AREF-ROW-MAJOR function could
	probably do it more efficiently.

    It seems to me that any set of rules that require AREF to iterate to
    find the data ought to be simplified.  So much for inline code.

Common Lisp was explicitly not designed for efficient implementation on
Fortran machines in the absence of declarations.  Does the ability to declare
an array to be SIMPLE take care of your problems with implementing inline
code for AREF?  If not, there is an issue we need to address.

    Date: Tue, 28 May 85 12:48 EDT
    From: David C. Plummer in disguise <DCP@SCRC-QUABBIN.ARPA>

    I don't think we don't use it for your case (1); instead we do make a
    new array, copy, and structure forwared the old to the new.  They can
    also be used for your case (2), but I think the our function
    SYS:%1D-AREF subsumes the need.

Slight clarifications: SYS:%1D-AREF and AREF-ROW-MAJOR are two names for
exactly the same thing.  "structure forward" is a Lisp machine concept
that does not exist in Common Lisp.