Arrays and Vectors

• To: common-lisp at SU-AI
• Subject: Arrays and Vectors
• From: Scott E. Fahlman <Fahlman at Cmu-20c>
• Date: Tue, 10 Aug 1982 05:19:00 -0000
• Cc: slisp: at CMU-20C

```OK, I am ready to cave in and allow fill pointers in ALL vectors
and all 1-D arrays.  (I think it is a serious mistake to allow fill
pointers in multi-D arrays.)  It is just too complex to allow fill
pointers in strings and not in other vectors, or to go to 1-D arrays
whenever you want the elasticity that a fill pointer can provide.

There is no added time cost for accessing a vector with a fill pointer,
as long as you were doing runtime bounds-checking anyway, and the space
cost is just one extra word per vector, so it's not a big deal.  Guy
currently holds the same point of view on this, and the new manual is
written this way, modulo some glitches.

I feel strongly that to make this coherent, we want the fill pointer to
be treated as the end of the vector or array for essentially all
purposes.  In particular, LENGTH means the length from 0 to the fill
pointer.  The ALLOCATED-LENGTH can be looked at, but it is normally only
meaningful when you want to grow the vector (i.e. move the fill
pointer).  The rest of the time, the space beyond the fill pointer is
inaccessible to built-in functions.  The Lisp Machine is very
inconsistent about all this, with LENGTH (meaning allocated length) used
in some places and ACTIVE-LENGTH in others -- this is presumably because
the fill pointers were grafted on as an afterthought.  Of course, for
most vectors most of the time, LENGTH and ALLOCATED-LENGTH will be the
same.

If vectors can have fill-pointers, we have many fewer uses for 1-D
arrays.  We would use these only in the odd cases where we want to make
some use of the indirection that the more complex array structure
provides, either for displacement or to allow arbitrary growth of the
array while preserving EQ-ness.  I think that having MAKE-VECTOR be a
separate function from MAKE-ARRAY is a very good thing; the previous
plan where you always called MAKE-ARRAY and sometimes got a vector was
very confusing.  In the new version of the manual VECTOR is still a
sub-type of ARRAY, and all of the ARRAY operation work on vectors
except, in some cases, those concerned with changing the array's size.

If you want vector accesses to be optimally efficient on something like
a VAX, you have to tell the compiler that you have a vector (or maybe
even a certain type of vector) and not a more general array.  This can be
done in any of several ways using the declaration system:

(VELT foo n)			; All equivalent in meaning and efficiency.
(ELT (THE VECTOR foo) n)
(AREF (THE VECTOR foo) n)

(VREF foo n)			; All equivalent in meaning and efficiency.
(ELT (THE (VECTOR T) foo) n)
(AREF (THE (VECTOR T) foo) n)

Instead of a THE construct, of course, you can declare the type of
variable FOO when it is bound.  If we go over to SETF as the master
changing form, we don't have to worry about ASET, VSET, VSETELT, etc.

The Lisp Machine people can just forget about these declarations, at
some small cost in efficiency if they ever move their code to a Perq or
a larger cost if they move to a Vax.

-- Scott

```