10. Arrays

10.1 What Arrays Are
An array is a Lisp object that consists of a of cells, each of which may contain a Lisp object. The individual cells are selected by numerical subscripts .

There are many types of arrays. Some types of arrays can hold Lisp objects of any type; the other types of arrays can only hold fixnums. The array types are known by a set of symbols symbols whose names begin with "art- " (for ARray Type).

array-types Variable
The value of array-types is a list of all of the array type symbols such as art-q , art-4b , art-string and so on.
array-types array-type-code
An array of the array type symbols, indexed by their internal numeric codes.
array-elements-per-q Variable
array-elements-per-q is an association list (see this link) which associates each array type symbol with the number of array elements stored in one word, for an array of that type. If the value is negative, it is instead the number of words per array element, for arrays whose elements are more than one word long.
array-elements-per-q array-type-code
This is an array, indexed by the internal codes of the array types, containing the number of array elements stored in one word, for an array of that type. If the value is negative, it is instead the number of words per array element, for arrays whose elements are more than one word long.
array-bits-per-element Variable
The value of array-bits-per-element is an association list (see this link) which associates each array type symbol with the number of bits of unsigned number it can hold, or nil if it can hold Lisp objects. This can be used to tell whether an array can hold Lisp objects or not.
array-bits-per-element array-type-code
This is an array, indexed by the internal codes of the array types, containing the number of bits per cell for unsigned numeric arrays, and nil for full-Lisp-object-containing array.
array-element-size array
Given an array, returns the number of bits that fit in an element of that array. For non-numeric arrays, the result is 24., assuming you will be storing unsigned fixnums in the array.
The most commonly used type is called art-q . An art-q array simply holds Lisp objects of any type. Similar to the art-q type is the art-q-list . Like the art-q , its elements may be any Lisp object. The difference is that the art-q-list array "doubles" as a list; the function g-l-p will take an art-q-list array and return a list object whose elements are those of the array, and whose actual substance is that of the array. If you rplaca elements of the list, the corresponding element of the array will change, and if you store into the array, the corresponding element of the list will change the same way. There is a set of types called art-1b, art-2b, art-4b, art-8b and art-16b ; these names are short for "1 bit", "2 bits", and so on. Each element of an art-1b array is a fixnum, and only one bit (the least significant) is remembered in the array; all of the others are discarded. Similarly, in an art-2b array, only the two least significant bits are remembered. So if you store a 5 into an art-2b array, for example, and look at it later, you will find a 1 rather than a 5. These arrays are used when it is known beforehand that the fixnums which will be stored are non-negative and limited in size to a certain number of bits. Their advantage over the art-q array is that they occupy less storage, because more than one element of the array is kept in a single machine word. (For example, 32 elements (decimal) of an art-1b array or 2 elements of an art-16b array will fit into one word). Character strings are implemented by the art-string array type. This type acts similarly to the art-8b ; its elements must be fixnums, of which only the least significant eight bits are stored. However, many important system functions, including read , print , and eval , treat art-string arrays very differently from the other kinds of arrays. These arrays are usually called string s, and an entire chapter of this manual deals with functions which manipulate them. There are three types of arrays which exist only for the purposes of stacks ; these types are called art-stack-head, art-special-pdl and art-reg-pdl . Their elements may be any Lisp object; their use is explained in the section on stacks (see this link).

The art-float array type is a special purpose type whose elements are flonums. When storing into such an array the value will be converted to a flonum. The advantage of storing flonums in an art-float array rather than an art-q array is that the numbers in an art-float array are not true Lisp objects. Instead the array remembers the numerical value, and when it is aref 'ed creates a Lisp object (a flonum) to hold the value. Because the system does special storage management for bignums and flonums that are intermediate results the use of art-float arrays can save a lot of work for the garbage-collector and hence greatly increase performance. An intermediate result is a Lisp object passed as an argument, stored in a local variable, or returned as the value of a function, but not stored into a global variable, an array, or list structure. art-float arrays also provide a locality of reference advantage over art-q arrays containing flonums.

10.2 How Arrays Work
The dimensionality of an array (or, the number of dimensions which the array has) is the number of subscripts used to refer to one of the elements of the array. The dimensionality may be any integer from one to seven, inclusively. The lowest value for any subscript is zero; the highest value is a property of the array. Each dimension has a size, which is the lowest number which is too great to be used as a subscript. For example, in a one dimensional array of five elements, the size of the one and only dimension is five, and the acceptable values of the subscript are zero, one, two, three, and four. The most basic primitive functions for handling arrays are: make-array , which is used for the creation of arrays, aref , which is used for examining the contents of arrays, and aset , which is used for storing into arrays. An array is a regular Lisp object, and it is common for an array to be the binding of a symbol, or the car or cdr of a cons, or, in fact, an element of an array. Another way of handling arrays, inherited from Maclisp, is to treat them as functions. In this case each array has a name, which is a symbol whose function definition is the array. The Lisp machine supports this style by allowing an array to be applied to arguments, as if it were a function. The arguments are treated as subscripts and the array is referenced appropriately. The store special form (see LINK:(store-fun)) is also supported. This form of array referencing is considered to be obsolete, and should not be used in new programs. Here are some issues of Maclisp compatibility: Fixnum arrays do not exist (however, see the Lisp machine's small-positive-number arrays). Flonum arrays exist but you do not use them in the same way; no declarations are required or allowed. "Un-garbage-collected" arrays do not exist. 'c yet??? --weak links Readtables and obarrays are represented as arrays, but unlike Maclisp special array types are not used. See the descriptions of read (LINK:(read-fun)) and intern (LINK:(intern-fun)) for information about readtables and obarrays (packages). There are no "dead" arrays, nor are Multics "external" arrays provided. The arraycall function is not used (see aref , LINK:(aref-fun).) Subscripts are always checked for validity, regardless of the value of *rset and whether the code is compiled or not. However, in a multi-dimensional array, an error is only caused if the subscripts would have resulted in a reference to storage outside of the array; so if you have a 2 by 7 array and refer to an element with subscripts 3 and 1, no error will be caused despite the fact that the reference is invalid; but if you refer to element 1 by 100, an error will be caused. In other words, any subscript error which is not detected will only refer to somewhere else in your array, and not to any other part of storage. Currently multi-dimensional arrays are stored in column-major order rather than row-major order as in Maclisp. This has an effect on paging performance when using large arrays. Row-major order means that successive memory locations differ in the last subscript, while column-major order means that successive memory locations differ in the first subscript. loadarrays and dumparrays are not provided. However, arrays can be put into "QFASL" files; see the section on fasloading (LINK:(fasload-fun)).
10.3 Extra Features of Arrays

Any array may have an array leader . An array leader is like a one-dimensional art-q array which is attached to the main array. So an array which has a leader acts like two arrays joined together. It can be stored in and examined by a special set of functions which are analogous to those used for the main array: array-leader and store-array-leader . The leader is always one-dimensional, and always can hold any kind of Lisp object, regardless of the type or dimensionality of the array. By convention, the zeroth element of the array leader of an array is used to hold the number of elements in the array that are "active" in some sense. When the zeroth element is used this way, it is called a fill pointer .

Specifically, if a string (an array of type art-string ) has seven elements, but it has a fill pointer of five, then only elements zero through four of the string are considered to be "active"; the string's printed representation will be five characters long, string-searching functions will stop after the fifth element, etc. The second element is also used in conjunction with the "named structure" feature; see this link.

The following explanation of displaced arrays is probably not of interest to a beginner; the section may be passed over without losing the continuity of the manual. Normally, an array consists of a small amount of header information, followed by the contents of the array. However, sometimes it is desirable to have the header information removed from the actual contents. One such occasion is when the contents of the array must be located in a special part of the Lisp Machine's address space, such as the area used for the control of input/output devices. Displaced arrays are also used to reference certain special system tables, which are at fixed addresses so the microcode can access them easily. If you give make-array a fixnum as its fourth argument, it will create a displaced array refering to that location of virtual memory. References to elements of the displaced array will access that part of storage, and return the contents; the regular aref and aset functions are used. If the array is one whose elements are Lisp objects, caution should be used: if the region of address space does not contain typed Lisp objects, the integrity of the storage system could be damaged by the garbage collector. If the array is one whose elements are bytes (such as an art-4b type), then there is no problem. It is important to know, in this case, that the elements of such arrays are allocated from the right to the left within the 32-bit words. See the description of internal array formats on LINK:(array-format).

It is also possible to have an array whose contents, instead of being located at a fixed place in virtual memory, are defined to be those of another array. Such an array is called an indirect array , and is created by giving make-array an array as its fourth argument. The effects of this are simple if both arrays have the same type; the two arrays share all elements. An object stored in a certain element of one can be retrieved from the corresponding element of the other. This, by itself, is not very useful. However, if the arrays have different dimensionality, the manner of accessing the elements differs. Thus, by creating a one-dimensional array of nine elements which was indirected to a second, two-dimensional array of three elements by three, then the elements could be accessed in either a one-dimensional or a two-dimensional manner. Even more complex effects can be produced if the new array is of a different type than the old array; see the description of internal array formats on LINK:(array-format).

It is also possible to create a one-dimensional indirect array in such a way that when an attempt is made to reference it or store into it, a constant number is added to the subscript given. This number is called the index-offset , and is specified at the time the indirect array is created, by giving a fixnum to make-array as its sixth argument. The nsubstring function (see LINK:(nsubstring-fun)) creates such arrays. 'findex "nsubstring"

10.4 Basic Array Functions
make-array area type dims &optional displaced-p leader index-offset named-structure
This creates and returns an array, according to various specifications. The area parameter specifies the area in which to allocate the array's storage; if you are not concerned with areas, simply use nil which as always means the default area. type should be a symbolic name of an array type; the most common of these is art-q . The elements of the array are initialized according to the type: if the array is of a type whose elements may only be fixnums or flonums, then every element of the array will initially be 0 ; otherwise, every element will initially be nil . See the description of array types on this link.

dims should be a list of fixnums which are the dimensions of the array; the length of the list will be the dimensionality of the array. For convenience, if the dimensionality should be one, the single dimension may be provided as a fixnum rather than a list of one fixnum. 

Examples:
(setq a (make-array nil 'art-q 5))       ; Create a one-d array 
					 ;of 5 elements. 

(setq b (make-array nil 'art-4b '(3 4))) ; Create a four-bit two-d 
					 ;array, 3 by 4.
If displaced-p is not nil , then the array will be a displaced array. displaced-p may either be a fixnum, to create a regular displaced array which refers to a certain section of virtual address space, or an array, to create an indirect array (see this link).

If leader is not nil , then the array will be given a leader. If leader is a fixnum, the array's leader will be leader elements long, and its elements will be initialized to nil . Leader may also be a list, in which case the length of the leader is equal to that of the list, and the elements are initialized to the elements of the list, in reverse order (i.e., the car of the list is stored in the highest-subscripted location in the leader). If index-offset is present, displaced-p should be an array, and index-offset should be a fixnum; it is made to be the index-offset of the created indirect array. (See this link.)

If named-structure is not nil , it is a symbol to be stored in the named-structure cell element of the array. The array created will be a named structure (see this link.) 

Examples:
(make-array nil 'art-q 5 nil 3)   ;;leader 3 elements long. 
(setq a (make-array nil 'art-1b 100 nil '(t nil)))
(array-leader a 0) => nil
(array-leader a 1) => t

make-array returns the newly-created array, and also returns, as a second value, the number of words allocated from area in the process of creating the array.

array-displaced-p array
array may be any kind of array. This predicate returns t if array is any kind of displaced array (including indirect arrays). Otherwise it returns nil .
array-indirect-p array
array may be any kind of array. This predicate returns t if array is an indirect array. Otherwise it returns nil .
array-indexed-p array
array may be any kind of array. This predicate returns t if array is an indirect array with an index-offset. Otherwise it returns nil .
adjust-array-size array new-size
array should be a one-dimensional array. Its size is changed to be new-size . If this results in making array smaller, then the extra elements are lost; if array is made bigger, the new elements are initialized in the same fashion as make-array (see LINK:(make-array-fun)): either to nil or 0 . [Currently there is a bug which causes initialization to zero not to work.] 
Example:
(setq a (make-array nil 'art-q 5))
(aset 'foo a 4)
(aref a 4) => foo
(adjust-array-size a 2)
(aref a 4) => ERROR
If the size of the array is being increased, adjust-array-size must allocate a new array somewhere; it then alters array so that references to it will be made to the new array instead, by means of an "invisible pointer". adjust-array-size will return this new array if it creates one, and otherwise it will return array . Be careful about using the returned result of adjust-array-size , because you may end up holding two arrays which are not the same (i.e., not eq ) which share the same contents.
return-array array
Return array to free storage. If it is displaced, this returns the pointer, not the data pointed to. Currently does nothing if the array is not at the end of its area. This will eventually be renamed to reclaim , when it works for other objects than arrays.
aref array &rest subscripts
Returns the element of array selected by the subscripts . The subscripts must be fixnums and their number must match the dimensionality of array .
ar-1 array i
array should be a one-dimensional array, and i should be a fixnum. This returns the i 'th element of array .
ar-2 array i j
array should be a two-dimensional array, and i and j should be fixnums. This returns the i by j 'th element of array .
ar-3 array i j k
array should be a three-dimensional array, and i , j , and k should be fixnums. This returns the i by j by k 'th element of array .
aset x array &rest subscripts
Stores x into the element of array selected by the subscripts . The subscripts must be fixnums and their number must match the dimensionality of array . The returned value is x .
as-1 x array i
array should be a one-dimensional array, and i should be a fixnum. x may be any object. x is stored in the i 'th element of array . as-1 returns x .
as-2 x array i j
array should be a two-dimensional array, and i and j should be fixnums. x may be any object. x is stored in the i by j 'th element of array . as-2 returns x .
as-3 x array i j k
array should be a three-dimensional array, and i , j , and k should be fixnums. x may be any object. x is stored in the i by j by k 'th element of array . as-3 returns x .
aloc array &rest subscripts
Returns a locative pointer to the element-cell of array selected by the subscripts . The subscripts must be fixnums and their number must match the dimensionality of array .
ap-1 array i
array should be a one-dimensional array whose elements contain Lisp objects, and i should be a fixnum. This returns a locative pointer to the i 'th element of array . See the explanation of locatives, this link.
ap-2 array i j
array should be a two-dimensional array whose elements contain Lisp objects, and i and j should be fixnums. This returns a locative pointer to the i by j 'th element of array . See the explanation of locatives, this link.
ap-3 array i j k
array should be a three-dimensional array whose elements contain Lisp objects, and i , j , and k should be fixnums. This returns a locative pointer to the i by j by k 'th element of array . See the explanation of locatives, this link.
The compiler turns aref into ar-1 , ar-2 , etc. according to the number of subscripts specified, turns aset into as-1 , as-2 , etc., and turns aloc into ap-1 , ap-2 , etc. For arrays with more than 3 dimensions the compiler uses the slightly less efficient form since the special routines only exist for 1, 2, and 3 dimensions. There is no reason for any program to call ar-1 , as-1 , ar-2 , etc. explicitly; they are documented because there used to be such a reason, and many existing programs use these functions. New programs should use aref , aset , and aloc .
arraycall ignored array &rest subscripts
(arraycall nil array sub1 sub2...) is the same as (aref array sub1 sub2...) . It exists for Maclisp compatibility.
get-list-pointer-into-array array-ref
The argument array-ref is ignored, but should be a reference to an art-q-list array by applying the array to subscripts (rather than by aref ). This returns a list object which is a portion of the "list" of the array, beginning with the last element of the array which has been referenced.
g-l-p array
array should be an art-q-list array. This returns a list which shares the storage of array . The art-q-list type exists so that g-l-p can be used. 
Example:
(setq a (make-array nil 'art-q-list 4))
(aref a 0) => nil
(setq b (g-l-p a)) => (nil nil nil nil)
(rplaca b t)
b => (t nil nil nil)
(aref a 0) => t
(aset 30 a 2)
b => (t nil 30 nil)
get-locative-pointer-into-array array-ref
get-locative-pointer-into-array is similar to get-list-pointer-into-array , except that it returns a locative, and doesn't require the array to be art-q-list .
arraydims array
array may be any array; it also may be a symbol whose function cell contains an array, for Maclisp compatibility (see LINK:(maclisp-array)). It returns a list whose first element is the symbolic name of the type of array , and whose remaining elements are its dimensions. 
Example:
(setq a (make-array nil 'art-q '(3 5)))
(arraydims a) => (art-q 3 5)
array-dimensions array
array-dimensions returns a list whose elements are the dimensions of array . 
Example:
(setq a (make-array nil 'art-q '(3 5)))
(array-dimensions a) => (3 5)
Note: the list returned by (array-dimensions x) is equal to the cdr of the list returned by (arraydims x) .
array-in-bounds-p array &rest subscripts
This function checks whether the subscripts are all legal subscripts for array , and returns t if they are; otherwise it returns nil .
array-length array
array may be any array. This returns the total number of elements in array . For a one-dimensional array, this is one greater than the maximum allowable subscript. (But if fill pointers are being used, you may want to use array-active-length (see LINK:(array-active-length-fun))). 
Example:
(array-length (make-array nil 'art-q 3)) => 3
(array-length (make-array nil 'art-q '(3 5)))
		=> 17  ;octal, which is 15. decimal
array-/#-dims array
Returns the dimensionality of array . Note that the name of the function includes a "#", which must be slashified if you want to be able to compile your program with the compiler running in Maclisp. 
Example:
(array-/#-dims (make-array nil 'art-q '(3 5))) => 2
array-dimension-n n array
array may be any kind of array, and n should be a fixnum. If n is between 1 and the dimensionality of array , this returns the n 'th dimension of array . If n is 0 , it returns the length of the leader of array ; if array has no leader it returns nil . If n is any other value, it returns nil . 
Examples:
(setq a (make-array nil 'art-q '(3 5) nil 7))
(array-dimension-n 1 a) => 3
(array-dimension-n 2 a) => 5
(array-dimension-n 3 a) => nil
(array-dimension-n 0 a) => 7
array-type array
Returns the symbolic type of array . 
Example:
(setq a (make-array nil 'art-q '(3 5)))
(array-type a) => art-q
fillarray array x
Note: for the present, all arrays concerned must be one-dimensional. array may be any type of array, or, for Maclisp compatibility, a symbol whose function cell contains an array. There are two forms of this function, depending on the type of x . If x is a list, then fillarray fills up array with the elements of list . If x is too short to fill up all of array , then the last element of x is used to fill the remaining elements of array . If x is too long, the extra elements are ignored. If x is an array (or, for Maclisp compatibility, a symbol whose function cell contains an array), then the elements of array are filled up from the elements of x . If x is too small, then the extra elements of array are not affected. fillarray returns array .
listarray array &optional limit
Note: for the present, all arrays concerned must be one-dimensional. array may be any type of array, or, for Maclisp compatibility, a symbol whose function cell contains an array. listarray creates and returns a list whose elements are those of array . If limit is present, it should be a fixnum, and only the first limit (if there are more than that many) elements of array are used, and so the maximum length of the returned list is limit .
copy-array-contents from to
from and to must be arrays. The contents of from is copied into the contents of to , element by element. Presently the first subscript varies fastest in multi-dimensional arrays (opposite from Maclisp). If to is shorter than from , the excess is ignored. If from is shorter than to , the rest of to is filled with nil if it is a q-type array or 0 if it is a numeric array or 200 if it is a string. t is always returned. Note that even if from or to has a leader, the whole array is used; the convention with leader element 0 being the "active" length of the array is not used by this function.
copy-array-portion from-array from-start from-end to-array to-start to-end
The portion of the array from-array with indices greater than or equal to from-start and less than from-end is copied into the portion of the array to-array with indices greater than or equal to to-start and less than to-end , element by element. If there are more elements in to-array , the extra elements are filled as in copy-array-contents . t is always returned.
10.5 Array Leaders

Array leaders were introduced at the beginning of the chapter. This section presents various functions which operate on array leaders.

array-has-leader-p array
array may be any array. This predicate returns t if array has a leader; otherwise it returns nil .
array-leader-length array
array may be any array. This returns the length of array 's leader if it has one, or nil if it does not.
array-leader array i
array should be an array with a leader, and i should be a fixnum. This returns the i 'th element of array 's leader. This is analogous to aref .
store-array-leader x array i
array should be an array with a leader, and i should be a fixnum. x may be any object. x is stored in the i 'th element of array 's leader. store-array-leader returns x . This is analogous to aset .
ap-leader array i
array should be an array with a leader, and i should be a fixnum. This returns a locative pointer to the i 'th element of array 's leader. See the explanation of locatives, this link. This is analogous to aloc .
array-active-length array
If array does not have a fill pointer, then this returns whatever (array-length array) would have. If array does have a fill pointer, array-active-length returns it. See the general explanation of the use of fill pointers, which is at the beginning of this section.
array-push array x
array must be a one-dimensional array which has a fill pointer, and x may be any object. array-push attempts to store x in the element of the array designated by the fill pointer, and increase the fill pointer by one. If the fill pointer does not designate an element of the array (specifically, when it gets too big), it is unaffected and array-push returns nil ; otherwise, the two actions (storing and incrementing) happen uninterruptibly, and array-push returns the former value of the fill pointer (one less than the one it leaves in the array). If the array is of type art-q-list , an operation similar to nconc has taken place, in that the element has been added to the list by changing the cdr of the formerly last element.
array-push-extend array x
array-push-extend is just like array-push except that if the fill pointer gets too large, the array is grown to fit the new element; i.e. it never "fails" the way array-push does, and so never returns nil .
array-pop array
array must be a one-dimensional array which has a fill pointer. The fill pointer is decreased by one, and the array element designated by the new value of the fill pointer is returned. If the new value does not designate any element of the array (specifically, if it has reached zero), an error is caused. The two operations (decrementing and array referencing) happen uninterruptibly. If the array is of type art-q-list , an operation similar to nbutlast has taken place.
list-array-leader array &optional limit
array may be any type of array, or, for Maclisp compatibility, a symbol whose function cell contains an array. list-array-leader creates and returns a list whose elements are those of array 's leader. If limit is present, it should be a fixnum, and only the first limit (if there are more than that many) elements of array 's leader are used, and so the maximum length of the returned list is limit . If array has no leader, nil is returned.
copy-array-contents-and-leader from to
This is just like copy-array-contents (see LINK:(copy-array-contents-fun)), but the leaders of from and to are also copied.
10.6 Maclisp Array Compatibility
Note: the functions in this section should not be used in new programs. In Maclisp, arrays are usually kept on the array property of symbols, and the symbols are used instead of the arrays. In order to provide some degree of compatibility for this manner of using arrays, the array , *array , and store functions are provided, and when arrays are applied to arguments, the arguments are treated as subscripts and apply returns the corresponding element of the array. However, the *rearray , loadarrays , and dumparrays functions are not provided. Also, flonum , readtable , and obarray type arrays are not supported.
array "e symbol type &eval &rest dims
This creates an art-q type array in default-array-area with the given dimensions. (That is, dims is given to make-array as its third argument.) type is ignored. If symbol is nil , the array is returned; otherwise, the array is put in the function cell of symbol , and symbol is returned.
*array symbol type &rest dims
This is just like array , except that all of the arguments are evaluated.
store "e array-ref x
x may be any object; array-ref should be a form which references an array by calling it as a function (aref forms are not acceptable). First x is evaluated, then array-ref is evaluated, and then the value of x is stored into the array cell which was referenced by the evaluation of array-ref .
xstore x array-ref
This is just like store , but it is not a special form; this is because the arguments are in the other order. This function only exists for the compiler to compile the store special form, and should never be used by programs.