;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Introduction to Arrays =Text: 3INTRODUCTION TO ARRAYS* An 1array* is a Lisp object that consists of a group of cells, each of which may contain an object. The individual cells are selected by numerical 1subscripts*. The type predicate 2arrayp* (4(PRIMOBJTYPE-1)Data Type Predicates*) can be used to test whether an object is an array. The 1rank* of an array (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 rank may be any integer from zero to seven, inclusively. An array of rank zero has a single element which is addressed using no subscripts. An array of rank one is called a 1vector*; the predicate 2vectorp* (see 4(PRIMOBJTYPE-1)Data Type Predicates*) tests whether an object is a vector. A series of functions called the generic sequence functions accept either a vector or a list as argument indiscriminantly (see 4(GENERIC-0)Generic Sequence Functions*). 3array-rank-limit* 1Constant* A constant giving the upper limit on the rank of an array. It is 8, indicating that 7 is the highest possible rank. 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. 3array-dimension-limit* 1Constant* Any one dimension of an array must be smaller than this constant. The 1total size* of an array is the number of elements in it. It is the product of the sizes of the dimensions of the array. 3array-total-size-limit* 1Constant* The total number of elements of any array must be smaller than this constant. A vector can have a 1fill pointer* which is a number saying how many elements of the vector are 1active*. For many purposes, only that many elements (starting with element zero) are used. The most basic primitive functions for handling arrays are: 2make-array*, which is used for the creation of arrays, 2aref*, which is used for examining the contents of arrays, and 2aset*, 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. There are many functions, described in this chapter, which take arrays as arguments and perform useful operations on them. 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. Zetalisp supports this style by allowing an array to be 1applied* to arguments, as if it were a function. The arguments are treated as subscripts and the array is referenced appropriately. The 2store* special form (see 4(ARRAYS-3)Maclisp Array Compatibility*) is also supported. This kind of array referencing is considered to be obsolete and is slower than the usual kind. It should not be used in new programs. =Node: Array Types =Text: 3ARRAY TYPES* There are several types of arrays, which differ primarily in which kinds of elements they are allowed to hold. Some types of arrays can hold Lisp objects of any type; such arrays are called 1general* arrays. The other types of array restrict the possible elements to a certain type, usually a numeric type. Arrays of these types are called 1specialized* arrays, or 1numeric* arrays if the elements must be numbers. For example, one array type permits only complex numbers with floating components to be stored in the array. Another permits only the numbers zero and one; Common Lisp calls these 1bit arrays*. The contents of a black-and-white screen are stored in a bit array. Several predicates exist for finding out which of these classifications an array belongs to: 2simple-vector-p* (4(PRIMOBJTYPE-1)Data Type Predicates*), 2bit-vector-p*, 2simple-bit-vector-p*, 2stringp* (4(PRIMOBJTYPE-1)Data Type Predicates*), and 2simple-string-p*. The array types are known by a set of symbols whose names begin with 2art-* (for `ARray Type'). The most commonly used type is called 2art-q*. An 2art-q* array simply holds Lisp objects of any type. Similar to the 2art-q* type is the 2art-q-list*. Like the 2art-q*, its elements may be any Lisp object. The difference is that the 2art-q-list* array doubles as a list; the function 2g-l-p* takes an 2art-q-list* array and returns a list whose elements are those of the array, and whose actual substance is that of the array. If you 2rplaca* elements of the list, the corresponding element of the array is changed, and if you store into the array, the corresponding element of the list changes the same way. An attempt to 2rplacd* the list causes a 2sys:rplacd-wrong-representation-type* error, since arrays cannot implement that operation. The most important type of specialized array is the 1string*, which is a vector of character objects. Character strings are implemented by the 2art-string* array type. Many important system functions, including 2read*, 2print*, and 2eval*, treat 2art-string* arrays very differently from the other kinds of arrays. There are also many functions specifically for operating on strings, described in chapter 4(CHARSTR-0)Characters and Strings*. As viewed by Common Lisp programs, the elements of a string are character objects. As viewed by traditional programs, the elements are integers in the range 0 to 255. While most code still accesses strings in the traditional manner and gets integers out, the Common Lisp viewpoint is considered the correct one. See 4(CHARSTR-0)Characters and Strings* for a discussion of this conflict of conventions and its effect on programs. An 2art-fat-string* array is a character string with wider characters, containing 16 bits rather than 8 bits. The extra bits are ignored by many string operations, such as comparison, on these strings; typically they are used to hold font information. There is a set of types called 2art-1b, art-2b, art-4b, art-8b*, and 2art-16b*; these names are short for `1 bit', `2 bits', and so on. Each element of an 2art-1n*b* array is a non-negative fixnum, and only the least significant 1n* bits are remembered in the array; all of the others are discarded. Thus 2art-1b* arrays store only 0 and 1, and if you store a 5 into an 2art-2b* array 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 2art-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 of an 2art-1b* array or 2 elements of an 2art-16b* array fit into one word). There are also 2art-32b* arrays which have 32 bits per element. Since fixnums only have 24 bits anyway, these are the same as 2art-q* arrays except that they only hold fixnums. They are not compatible with the other ``bit'' array types and generally should not be used. An 2art-half-fix* array contains half-size fixnums. Each element of the array is a signed 16-bit integer; the range is from -32768 to 32767 inclusive. The 2art-float* array type is a special-purpose type whose elements are floats. When storing into such an array the value (any kind of number) is converted to a float, using the 2float* function (see 4(NUMBERS-2)Numeric Type Conversions*). The advantage of storing floats in an 2art-float* array rather than an 2art-q* array is that the numbers in an 2art-float* array are not true Lisp objects. Instead the array remembers the numerical value, and when it is 2aref*'ed creates a Lisp object (a float) to hold the value. Because the system does special storage management for bignums and floats that are intermediate results, the use of 2art-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 special variable, a non-2art-float* array, or list structure. 2art-float* arrays also provide a locality of reference advantage over 2art-q* arrays containing floats, since the floats are contained in the array rather than being separate objects probably on different pages of memory. The 2art-fps-float* array type is another special-purpose type whose elements are floats. The internal format of this array is compatible with the PDP-11/VAX single-precision floating-point format. The primary purpose of this array type is to interface with the FPS array processor, which can transfer data directly in and out of such an array. Any type of number may be stored into an 2art-fps-float* array, but it is, in effect, converted to a float, and then rounded off to the 24-bit precision of the PDP-11. If the magnitude of the number is too large, the largest valid floating-point number is stored. If the magnitude is too small, zero is stored. When an element of an 2art-fps-float* array is read, a new float is created containing the value, just as with an 2art-float* array. The 2art-complex* array type is a special purpose type whose elements are arbitrary numbers, which may be complex numbers. (Most of the numeric array types can only hold real numbers.) As compared with an ordinary 2art-q* array, 2art-complex* provides an advantage in garbage collection similar to what 2art-float* provides for floating point numbers. The 2art-complex-float* array type is a special purpose type whose elements are numbers (real or complex) whose real and imaginary parts are both floating point numbers. (If you store a non-floating-point number into the array, its real and imaginary parts are converted to floating point.) This provides maximum advantage in garbage collection if all the elements you wish to store in the array are numbers with floating point real and imaginary parts. The 2art-complex-fps-float* array type is similar to 2art-complex-float* but each real or imaginary part is stored in the form used by the FPS array processor. Each element occupies two words, the first being the real part and the second being the imaginary part. There are three types of arrays which exist only for the implementation of 1stack groups*; these types are called 2art-stack-group-head, art-special-pdl*, and 2art-reg-pdl*. Their elements may be any Lisp object; their use is explained in the section on stack groups (see 4(STACKGROUPS-0)Stack Groups*). 3array-types* 1Constant* The value of 2array-types* is a list of all of the array type symbols such as 2art-q*, 2art-4b*, 2art-string* and so on. The values of these symbols are internal array type code numbers for the corresponding type. 3array-types* 1array-type-code* Given an internal numeric array-type code, returns the symbolic name of that type. 3array-elements-per-q* 1Constant* 2array-elements-per-q* is an association list (see 4(MANLISTSTR-2)Association Lists*) 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. 3array-elements-per-q* 1array-type-code* Given the internal array-type code number, returns 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. 3array-bits-per-element* 1Constant* The value of 2array-bits-per-element* is an association list (see 4(MANLISTSTR-2)Association Lists*) which associates each array type symbol with the number of bits of unsigned number it can hold, or 2nil* if it can hold Lisp objects. This can be used to tell whether an array can hold Lisp objects or not. 3array-bits-per-element* 1array-type-code* Given the internal array-type code numbers, returns the number of bits per cell for unsigned numeric arrays, or 2nil* for a type of array that can contain Lisp objects. 3array-element-size* 1array* Given an array, returns the number of bits that fit in an element of that array. For arrays that can hold general Lisp objects, the result is 25., based on the assumption that you will be storing fixnums in the array. =Node: Extra Features of Arrays =Text: 3EXTRA FEATURES OF ARRAYS* Any array may have an 1array leader*. An array leader is like a one-dimensional 2art-q* array which is attached to the main array. So an array which has a leader acts like two arrays joined together. The leader can be stored into and examined by a special set of functions, different from those used for the main array: 2array-leader* and 2store-array-leader*. The leader is always one-dimensional, and always can hold any kind of Lisp object, regardless of the type or rank of the main part of the array. Very often the main part of an array is used as a homogeneous set of objects, while the leader is used to remember a few associated non-homogeneous pieces of data. In this case the leader is not used like an array; each slot is used differently from the others. Explicit numeric subscripts should not be used for the leader elements of such an array; instead the leader should be described by a 2defstruct* (see 4(DEFSTRUCT-1)How to Use Defstruct*). By convention, element 0 of the array leader of an array is used to hold the number of elements in the array that are ``active''. When the zeroth element is used this way, it is called a 1fill pointer*. Many array-processing functions recognize the fill pointer. For instance, if a string (an array of type 2art-string*) has seven elements, but its fill pointer contains the value five, then only elements zero through four of the string are considered to be active; the string's printed representation is five characters long, string-searching functions stop after the fifth element, etc. Fill pointers are a Common Lisp standard, but the array leader which is the Lisp Machine's way of implementing them is not standard. 3fill-pointer* 1array* Returns the fill pointer of 1array*, or 2nil* if it does not have one. This function can be used with 2setf* to set the array's fill pointer. The system does not provide a way to turn off the fill-pointer convention; any array that has a leader must reserve element 0 for the fill pointer or avoid using many of the array functions. Leader element 1 is used in conjunction with the ``named structure'' feature to associate a user-defined data type with the array; see 4(DEFSTRUCT-2)Named Structures*. Element 1 is treated specially only if the array is flagged as a named structure. =Node: Displaced Arrays =Text: 3DISPLACED ARRAYS* The following explanation of 1displaced 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 is represented as 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, or the bitmap memory which generates the TV image. 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 2make-array* a fixnum or a locative as the value of the 2:displaced-to* option, it creates a displaced array referring to that location of virtual memory and its successors. References to elements of the displaced array will access that part of storage, and return the contents; the regular 2aref* and 2aset* 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 and the garbage collector could be damaged. If the array is one whose elements are bytes (such as an 2art-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. 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 1indirect array*, and is created by giving 2make-array* an array as the value of the 2:displaced-to* option. 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 rank, the manner of accessing the elements differs. Thus, creating a one-dimensional array of nine elements, indirected to a second, two-dimensional array of three elements by three, allows access to the elements in either a one-dimensional or a two-dimensional manner. Weird effects can be produced if the new array is of a different type than the old array; this is not generally recommended. Indirecting an 2art-1m*b* array to an 2art-1n*b* array does the obvious thing. For instance, if 1m* is 4 and 1n* is 1, each element of the first array contains four bits from the second array, in right-to-left order. It is also possible to create an 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 1index-offset*. It is specified at the time the indirect array is created, by giving a fixnum to 2make-array* as the value of the 2:displaced-index-offset* option. The length of the indirect array need not be the full length of the array it indirects to; it can be smaller. Thus the indirect array can cover just a subrange of the original array. The 2nsubstring* function (see 4(CHARSTR-2)Basic String Operations*) creates such arrays. When using index offsets with multi-dimensional arrays, there is only one index offset; it is added in to the linearized subscript which is the result of multiplying each subscript by an appropriate coefficient and adding them together. =Node: Constructing Arrays =Text: 3CONSTRUCTING ARRAYS vector* &rest 1elements* Constructs and returns a vector (one-dimensional array) whose elements are the arguments given. 3make-array* 1dimensions* &rest 1options.* This is the primitive function for making arrays. 1dimensions* should be a list of fixnums which are the dimensions of the array; the length of the list is the rank of the array. For convenience you can specify a single fixnum rather than a list of one fixnum, when making a one-dimensional array. 1options* are alternating keywords and values. The keywords may be any of the following: 2:area* The value specifies in which area (see 4(AREAS-0)Areas*) the array should be created. It should be either an area number (a fixnum), or 2nil* to mean the default area. 2:type* The value should be a symbolic name of an array type; the most common of these is 2art-q*, which is the default. 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 floats, then every element of the array is initially 0 or 0.0; otherwise, every element is initially 2nil*. See the description of array types in 4(ARRAYS-1)Array Types*. The value of the option may also be the value of a symbol which is an array type name (that is, an internal numeric array type code). 2:element-type* 1element-type* is the Common Lisp way to control the type of array made. Its value is a Common Lisp type specifier (see 4(PRIMOBJTYPE-0)Primitive Object Types*). The array type used is the most specialized which can allow as an element anything which fits the type specifier. For example, if 1element-type* is 2(mod 4)*, you get an 2art-2b* array. If 1element-type* is 2(mod 3)*, you still get an 2art-2b* array, that being the most restrictive which can store the numbers 0, 1 and 2. If 2element-type* is 2string-char*, you get a string. 2:initial-value* 2make-array*Specifies the value to be stored in each element of the new array. If it is not specified, it is 2nil* for arrays that can hold arbitrary objects, or 0 or 0.0 for numeric arrays. 2:initial-value* is obsolete. 2:initial-contents* Specifies the entire contents for the new array, as a sequence of sequences of sequences... Array element 1 3 4 of a three-dimensional array would be 2(elt (elt* 2(elt 1initial-contents* 1) 3) 4)*. Recall that a sequence is either a list or a vector, and vectors include strings. 2:displaced-to* If this is not 2nil*, a 1displaced* array is constructed. If the value is a fixnum or a locative, 2make-array* creates a regular displaced array which refers to the specified section of virtual address space. If the value is an array, 2make-array* creates an indirect array (see 4(ARRAYS-1)Displaced Arrays*). 2:leader-length* The value should be a fixnum. The array is made with a leader containing that many elements. The elements of the leader are initialized to 2nil* unless the 2:leader-list* option is given (see below). 2:leader-list* The value should be a list. Call the number of elements in the list 1n*. The first 1n* elements of the leader are initialized from successive elements of this list. If the 2:leader-length* option is not specified, then the length of the leader is 1n*. If the 2:leader-length* option is given, and its value is greater than 1n*, then the 1n*th and following leader elements are initialized to 2nil*. If its value is less than 1n*, an error is signaled. The leader elements are filled in forward order; that is, the car of the list is stored in leader element 0, the cadr in element 1, and so on. 2:fill-pointer* The value should be a fixnum. The array is made with a leader containing at least one element, and this fixnum is used to initialize that first element. Using the 2:fill-pointer* option is equivalent to using 2:leader-list* with a list one element long. It avoids consing the list, and is also compatible with Common Lisp. 2:displaced-index-offset* If this is present, the value of the 2:displaced-to* option should be an array, and the value should be a non-negative fixnum; it is made to be the index-offset of the created indirect array. (See 4(ARRAYS-1)Displaced Arrays*.) 2:named-structure-symbol* If this is not 2nil*, it is a symbol to be stored in the named-structure cell of the array. The array made is tagged as a named structure (see 4(DEFSTRUCT-2)Named Structures*.) If the array has a leader, then this symbol is stored in leader element 1 regardless of the value of the 2:leader-list* option. If the array does not have a leader, then this symbol is stored in array element zero. Array leader slot 1, or array element 0, cannot be used for anything else in a named structure. 2:adjustable-p* In strict Common Lisp, a non-2nil* value for this keyword makes the array 1adjustable*, which means that it is permissible to change the array's size with 2adjust-array* (4(ARRAYS-2)Changing the Size of an Array*). This is because other Lisp systems have multiple representations for arrays, one which is simple and fast to access, and another which can be adjusted. The Lisp Machine does not require two representations: any array's size may be changed, and this keyword is ignored. Examples: 2;; Create a one-dimensional array of five elements.* 3(make-array 5)* 2;; Create a two-dimensional array,* 2;; three by four, with four-bit elements.* 3(make-array '(3 4) :type 'art-4b)* 2;; Create an array with a three-element leader.* 3(make-array 5 :leader-length 3)* 2;; Create an array containing 5 t's,* 2;; and a fill pointer saying the array is full.* 3(make-array 5 :initial-value t :fill-pointer 5)* 2;; Create a named-structure with five leader* 2;; elements, initializing some of them.* 3(setq b (make-array 20 :leader-length 5 * 3 :leader-list '(0 nil foo)* 3 :named-structure-symbol 'bar))* 3(array-leader b 0) => 0* 3(array-leader b 1) => bar* 3(array-leader b 2) => foo* 3(array-leader b 3) => nil* 3(array-leader b 4) => nil* 2make-array* returns the newly-created array, and also returns, as a second value, the number of words allocated in the process of creating the array, i.e. the 2%structure-total-size* of the array. When 2make-array* was originally implemented, it took its arguments in the following fixed pattern: 3 (make-array 1area* 1type* 1dimensions** 3 &optional 1displaced-to* 1leader** 3 1displaced-index-offset** 3 1named-structure-symbol*)* 1leader* was a combination of the 2:leader-length* and 2:leader-list* options, and the list was in reverse order. This obsolete form is still supported so that old programs will continue to work, but the new keyword-argument form is preferred.