[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
An array 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 subscripts.
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. 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 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 (store-fun)) 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.
.setq array-type page 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 or flonums. The array types are known by a set of symbols whose names begin with "art-" (for ARray Type).
.vindex art-q The most commonly used type is called art-q. An art-q array simply holds Lisp objects of any type.
.vindex art-q-list .setq art-q-list-var page 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 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. An attempt to rplacd the list will cause an error, since arrays cannot implement that operation.
.vindex art-1b .vindex art-2b .vindex art-4b .vindex art-8b .vindex art-16b 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-nb array is a non-negative fixnum, and only the least significant n bits are remembered in the array; all of the others are discarded. Thus art-1b arrays store only 0 and 1, and if you store a 5 into an art-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 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 of an art-1b array or 2 elements of an art-16b array will fit into one word).
.vindex art-32b There are also art-32b arrays which have 32 bits per element. Since fixnums only have 24 bits anyway, these are the same as art-q arrays except that they only hold fixnums. They do not behave consistently with the other "bit" array types, and generally they should not be used.
.vindex art-string 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 strings, and chapter (string-chapter) of this manual deals with functions that manipulate them.
.vindex art-fat-string An art-fat-string array is a character string with wider characters, containing 16 bits rather than 8 bits. The extra bits are ignored by string operations, such as comparison, on these strings; typically they are used to hold font information.
.vindex art-half-fix An art-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.
.vindex art-float The art-float array type is a special-purpose type whose elements are flonums. When storing into such an array the value (any kind of number) will be converted to a flonum, using the float function (see (float-fun)). 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, a non-art-float array, or list structure. art-float arrays also provide a locality of reference advantage over art-q arrays containing flonums, since the flonums are contained in the array rather than being separate objects probably on different pages of memory.
.vindex art-fps-float The art-fps-float array type is another special-purpose type whose elements are flonums. The internal format of this array is compatible with the pdp11/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. When storing into an art-fps-float array any kind of number may be stored. It will be rounded off to the 24-bit precision of the pdp11. If the magnitude of the number is too large, the largest valid floating-point number will be stored. If the magnitude is too small, zero will be stored. When reading from an art-fps-float array, a new flonum is created containing the value, just as with an art-float array.
.vindex art-stack-group-head .vindex art-reg-pdl .vindex art-special-pdl There are three types of arrays which exist only for the implementation of stack groups; these types are called art-stack-group-head, art-special-pdl, and art-reg-pdl. Their elements may be any Lisp object; their use is explained in the section on stack groups (see (stack-group)).
.setq column-major section-page Currently, multi-dimensional arrays are stored in column-major order rather than row-major order as in Maclisp. 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. This has an effect on paging performance when using large arrays; if you want to reference every element in a multi-dimensional array and move linearly through memory to improve locality of reference, you must vary the first subscript fastest rather than the last.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Very often the main part of an array will be a homogeneous set of objects, while the leader will be 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 defstruct (see (defstruct-fun)).
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" in some sense. When the zeroth element is used this way, it is called a fill pointer. @setq fill-pointer page Many array-processing functions recognize the fill pointer. For instance, if a string (an array of type art-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 will be five characters long, string-searching functions will stop after the fifth element, etc.
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 "data type" with the array; see (named-structure). Element 1 is only treated specially if the array is flagged as a named structure.
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 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 make-array a fixnum or a locative as the value of the :displaced-to option, it will create 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 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 and the garbage collector could be damaged. 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.
.setq indirect-array page 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 the value of the :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 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. 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 art-mb array to an art-nb array will do the "obvious" thing. For instance, if m is 4 and n is 1, each element of the first array will contain four bits from the second array, in right-to-left order.
.setq index-offset page 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 index-offset, and is specified at the time the indirect array is created, by giving a fixnum to make-array as the value of the :displaced-index-offset option. Similarly, the length of the indirect array need not be the full length of the array it indirects to; it can be smaller. The nsubstring function (see (nsubstring-fun)) 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.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
options are alternating keywords and values. The keywords may be any of the following:
Examples: ;; Create a one-dimensional array of five elements. (make-array 5) ;; Create a two-dimensional array, ;; three by four, with four-bit elements. (make-array '(3 4) ':type 'art-4b) ;; Create an array with a three-element leader. (make-array 5 ':leader-length 3) ;; Create an array with a leader, providing ;; initial values for the leader elements. (setq a (make-array 100 ':type 'art-1b ':leader-list '(t nil))) (array-leader a 0) => t (array-leader a 1) => nil |
make-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 %structure-total-size of the array.
When make-array was originally implemented, it took its arguments in the following fixed pattern:
(make-array area type dimensions &optional displaced-to leader displaced-index-offset named-structure-symbol) |
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 old programs use these functions. New programs should use aref, aset, and aloc.
A related function, provided only for Maclisp compatibility, is arraycall ((arraycall-fun)).
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Example: (setq a (make-array '(3 5))) (array-type a) => art-q |
Example: (array-length (make-array 3)) => 3 (array-length (make-array '(3 5))) => 17 ;octal, which is 15. decimal |
Example: (array-#-dims (make-array '(3 5))) => 2 |
Examples: (setq a (make-array '(3 5) ':leader-length 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 |
Example: (setq a (make-array '(3 5))) (array-dimensions a) => (3 5) |
Example: (setq a (make-array '(3 5))) (arraydims a) => (art-q 3 5) |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
If array is made smaller, the extra elements are lost; if array is made bigger, the new elements are initialized in the same fashion as make-array (see (make-array-fun)) would initialize them: either to nil or 0, depending on the type of array.
Example: (setq a (make-array 5)) (aset 'foo a 4) (aref a 4) => foo (adjust-array-size a 2) (aref a 4) => an error occurs |
Unlike adjust-array-size, array-grow always creates a new array rather than growing or shrinking the array in place. But array-grow of a multi-dimensional array can change all the subscripts and move the elements around in memory to keep each element at the same logical place in the array.
If you still have any references to array anywhere in the Lisp world after this function returns, the garbage collector can get a fatal error if it sees them. Since the form that calls this function must get the array from somewhere, it may not be clear how to legally call return-array. One of the only ways to do it is as follows:
(defun func () (let ((array (make-array 100))) ... (return-array (prog1 array (setq array nil))))) |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
These functions manipulate art-q-list arrays, which were introduced on (art-q-list-var).
Example: (setq a (make-array 4 ':type 'art-q-list)) (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) |
The following two functions work strangely, in the same way that store does, and should not be used in new programs.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Note that even if from or to has a leader, the whole array is used; the convention that leader element 0 is the "active" length of the array is not used by this function. The leader itself is not copied.
copy-array-contents works on multi-dimensional arrays. from and to are "linearized" subscripts, and column-major order is used, i.e. the first subscript varies fastest (opposite from fillarray).
The top-left corner of the source rectangle is (aref from-array from-x from-y). The top-left corner of the destination rectangle is (aref to-array to-x to-y). width and height are the dimensions of both rectangles. If width or height is zero, bitblt does nothing.
from-array and to-array are allowed to be the same array. bitblt normally traverses the arrays in increasing order of x and y subscripts. If width is negative, then (abs width) is used as the width, but the processing of the x direction is done backwards, starting with the highest value of x and working down. If height is negative it is treated analogously. When bitblt'ing an array to itself, when the two rectangles overlap, it may be necessary to work backwards to achieve the desired effect, such as shifting the entire array upwards by a certain number of rows. Note that negativity of width or height does not affect the (x,y) coordinates specified by the arguments, which are still the top-left corner even if bitblt starts at some other corner.
If the two arrays are of different types, bitblt works bit-wise and not element-wise. That is, if you bitblt from an art-2b array into an art-4b array, then two elements of the from-array will correspond to one element of the to-array.
If bitblt goes outside the bounds of the source array, it wraps around. This allows such operations as the replication of a small stipple pattern through a large array. If bitblt goes outside the bounds of the destination array, it signals an error.
If src is an element of the source rectangle, and dst is the corresponding element of the destination rectangle, then bitblt changes the value of dst to (boole alu src dst). See the boole function ((boole-fun)). There are symbolic names for some of the most useful alu functions; they are tv:alu-seta (plain copy), tv:alu-ior (inclusive or), tv:alu-xor (exclusive or), and tv:alu-andca (and with complement of source).
bitblt is written in highly-optimized microcode and goes very much faster than the same thing written with ordinary aref and aset operations would. Unfortunately this causes bitblt to have a couple of strange restrictions. Wrap-around does not work correctly if from-array is an indirect array with an index-offset. bitblt will signal an error if the first dimensions of from-array and to-array are not both integral multiples of the machine word length. For art-1b arrays, the first dimension must be a multiple of 32., for art-2b arrays it must be a multiple of 16., etc.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The functions in this section perform some useful matrix operations. The matrices are represented as two-dimensional Lisp arrays. These functions are part of the mathematics package rather than the kernel array system, hence the "math:" in the names.
The next two functions are used to solve sets of simultaneous linear equations. math:decompose takes a matrix holding the coefficients of the equations and produces the LU decomposition; this decomposition can then be passed to math:solve along with a vector of right-hand sides to get the values of the variables. If you want to solve the same equations for many different sets of right-hand side values, you only need to call math:decompose once. In terms of the argument names used below, these two functions exist to solve the vector equation A x = b for x. A is a matrix. b and x are vectors.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
A plane is an array whose bounds, in each dimension, are plus-infinity and minus-infinity; all integers are legal as indices. Planes are distinguished not by size and shape, but by number of dimensions alone. When a plane is created, a default value must be specified. At that moment, every component of the plane has that value. As you can't ever change more than a finite number of components, only a finite region of the plane need actually be stored.
The regular array accessing functions don't work on planes. You can use make-plane to create a plane, plane-aref or plane-ref to get the value of a component, and plane-aset or plane-store to store into a component. array-#-dims will work on a plane.
A plane is actually stored as an array with a leader. The array corresponds to a rectangular, aligned region of the plane, containing all the components in which a plane-store has been done (and others, in general, which have never been altered). The lowest-coordinate corner of that rectangular region is given by the plane-origin in the array leader. The highest coordinate corner can be found by adding the plane-origin to the array-dimensions of the array. The plane-default is the contents of all the elements of the plane which are not actually stored in the array. The plane-extension is the amount to extend a plane by in any direction when the plane needs to be extended. The default is 32.
If you never use any negative indices, then the plane-origin will be all zeroes and you can use regular array functions, such as aref and aset, to access the portion of the plane which is actually stored. This can be useful to speed up certain algorithms. In this case you can even use the bitblt function on a two-dimensional plane of bits or bytes, provided you don't change the plane-extension to a number that is not a multiple of 32.
Example:
(make-plane 2 ':type 'art-4b ':default-value 3) |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The functions in this section are provided only for Maclisp compatibility, and should not be used in new programs.
Fixnum arrays do not exist (however, see Zetalisp's small-positive-integer 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. Readtables and obarrays are represented as arrays, but unlike Maclisp special array types are not used. See the descriptions of read ((read-fun)) and intern ((intern-fun)) for information about readtables and obarrays (packages). There are no "dead" arrays, nor are Multics "external" arrays provided.
The arraycall function exists for compatibility but should not be used (see aref, (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. For example, 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, subscript errors will be caught if and only if they refer to storage outside the array; some errors are undetected, but they will only clobber some other element of the same array rather than clobbering something completely unpredictable.
Currently, multi-dimensional arrays are stored in column-major order rather than row-major order as in Maclisp. See (column-major) for further discussion of this issue.
loadarrays and dumparrays are not provided. However, arrays can be put into "QFASL" files; see (fasdump).
The *rearray function is not provided, since not all of its functionality is available in Zetalisp. The most common uses can be replaced by adjust-array-size.
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.
[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |