;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Copying an Array =Text: 3COPYING AN ARRAY* The new functions 2replace* (4(GENERIC-1)Simple Sequence Operations*) and 2fill* (4(GENERIC-1)Simple Sequence Operations*) are useful ways to copy parts of arrays. 3array-initialize* 1array* 1value* &optional 1start* 1end* Stores 1value* into all or part of 1array*. 1start* and 1end* are optional indices which delimit the part of 1array* to be initialized. They default to the beginning and end of the array. This function is by far the fastest way to do the job. 3fillarray* 1array* 1x* 1array* may be any type of array, or, for Maclisp compatibility, a symbol whose function cell contains an array. It can also be 2nil*, in which case an array of type 2art-q* is created. There are two forms of this function, depending on the type of 1x*. If 1x* is a list, then 2fillarray* fills up 1array* with the elements of 1list*. If 1x* is too short to fill up all of 1array*, then the last element of 1x* is used to fill the remaining elements of 1array*. If 1x* is too long, the extra elements are ignored. If 1x* is 2nil* (the empty list), 1array* is filled with the default initial value for its array type (2nil* or 0). If 1x* is an array (or, for Maclisp compatibility, a symbol whose function cell contains an array), then the elements of 1array* are filled up from the elements of 1x*. If 1x* is too small, then the extra elements of 1array* are not affected. If 1array* is multi-dimensional, the elements are accessed in row-major order: the last subscript varies the most quickly. The same is true of 1x* if it is an array. 2fillarray* returns 1array*; or, if 1array* was 2nil*, the newly created array. 3listarray* 1array* &optional 1limit* 1array* may be any type of array, or, for Maclisp compatibility, a symbol whose function cell contains an array. 2listarray* creates and returns a list whose elements are those of 1array*. If 1limit* is present, it should be a fixnum, and only the first 1limit* (if there are more than that many) elements of 1array* are used, and so the maximum length of the returned list is 1limit*. If 1array* is multi-dimensional, the elements are accessed in row-major order: the last subscript varies the most quickly. 3list-array-leader* 1array* &optional 1limit* 1array* may be any type of array, or, for Maclisp compatibility, a symbol whose function cell contains an array. 2list-array-leader* creates and returns a list whose elements are those of 1array*'s leader. If 1limit* is present, it should be a fixnum, and only the first 1limit* (if there are more than that many) elements of 1array*'s leader are used, and so the maximum length of the returned list is 1limit*. If 1array* has no leader, 2nil* is returned. 3copy-array-contents* 1from* 1to* 1from* and 1to* must be arrays. The contents of 1from* is copied into the contents of 1to*, element by element. If 1to* is shorter than 1from*, the rest of 1from* is ignored. If 1from* is shorter than 1to*, the rest of 1to* is filled with 2nil*, 0 or 0.0 according to the type of array. This function always returns 2t*. The entire length of 1from* or 1to* is used, ignoring the fill pointers if any. The leader itself is not copied. 2copy-array-contents* works on multi-dimensional arrays. 1from* and 1to* are linearized subscripts, and elements are taken in row-major order. 3copy-array-contents-and-leader* 1from* 1to* Like 2copy-array-contents*, but also copies the leader of 1from* (if any) into 1to*. 3copy-array-portion* 1from-array* 1from-start* 1from-end* 1to-array* 1to-start* 1to-end* The portion of the array 1from-array* with indices greater than or equal to 1from-start* and less than 1from-end* is copied into the portion of the array 1to-array* with indices greater than or equal to 1to-start* and less than 1to-end*, element by element. If there are more elements in the selected portion of 1to-array* than in the selected portion of 1from-array*, the extra elements are filled with the default value as by 2copy-array-contents*. If there are more elements in the selected portion of 1from-array*, the extra ones are ignored. Multi-dimensional arrays are treated the same way as 2copy-array-contents* treats them. This function always returns 2t*. 2%blt* and 2%blt-typed* (4(SUBPRIMITIVES-2)Copying Data*) are often useful for copying parts of arrays. They can be used to shift a part of an array either up or down. =Node: Bit Array Functions =Text: 3BIT ARRAY FUNCTIONS* These functions perform bitwise boolean operations on the elements of arrays. 3bit-and* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-ior* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-xor* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-eqv* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-nand* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-nor* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-andc1* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-andc2* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-orc1* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* 3bit-orc2* 1bit-array-1* 1bit-array-2* &optional 1result-bit-array* Perform boolean operations element by element on bit arrays. The arguments must match in their size and shape, and all of their elements must be integers. Corresponding elements of 1bit-array-1* and 1bit-array-2* are taken and passed to one of 2logand*, 2logior*, etc. to get an element of the result array. If the third argument is non-2nil*, the result bits are stored into it, modifying it destructively. If it is 2t*, the results are stored in 1bit-array-1*. Otherwise a new array of the same type as 1bit-array-1* is created and used for the result. In any case, the value returned is the array where the results are stored. These functions were introduced for the sake of Common Lisp, which defines them only when all arguments are specialized arrays that hold only zero or one. In the Lisp machine, they accept not only such arrays (2art-1b* arrays) but any arrays whose elements are integers. 3bit-not* 1bit-array* &optional 1result-bit-array* Performs 2lognot* on each element of 1bit-array* to get an element of the result. If 1result-bit-array* is non-2nil*, the result elements are stored in that; it must match 1bit-array* in size and shape. Otherwise, a new array of the same type as 1bit-array* is created and used to hold the result. The value of 2bit-not* is the array where the results are stored. 3bitblt* 1alu* 1width* 1height* 1from-array* 1from-x* 1from-y* 1to-array* 1to-x* 1to-y* 1from-array* and 1to-array* must be two-dimensional arrays of bits or bytes (2art-1b*, 2art-2b*, 2art-4b*, 2art-8b*, 2art-16b*, or 2art-32b*). 2bitblt* copies a rectangular portion of 1from-array* into a rectangular portion of 1to-array*. The value stored can be a Boolean function of the new value and the value already there, under the control of 1alu* (see below). This function is most commonly used in connection with raster images for TV displays. The top-left corner of the source rectangle is 2(ar-2-reverse 1from-array* 1from-x* 1from-y*)*. The top-left corner of the destination rectangle is 2(ar-2-reverse 1to-array* 1to-x* 1to-y*)*. 1width* and 1height* are the dimensions of both rectangles. If 1width* or 1height* is zero, 2bitblt* does nothing. The 1x* coordinates and 1width* are used as the second dimension of the array, since the horizontal index is the one which varies fastest in the screen buffer memory and the array's last index varies fastest in row-major order. 1from-array* and 1to-array* are allowed to be the same array. 2bitblt* normally traverses the arrays in increasing order of 1x* and 1y* subscripts. If 1width* is negative, then 2(abs 1width*)* is used as the width, but the processing of the 1x* direction is done backwards, starting with the highest value of 1x* and working down. If 1height* is negative it is treated analogously. When 2bitblt*'ing an array to itself, when the two rectangles overlap, it may be necessary to work backwards to achieve effects such as shifting the entire array downwards by a certain number of rows. Note that negativity of 1width* or 1height* does not affect the (1x*, 1y*) coordinates specified by the arguments, which are still the top-left corner even if 2bitblt* starts at some other corner. If the two arrays are of different types, 2bitblt* works bit-wise and not element-wise. That is, if you 2bitblt* from an 2art-2b* array into an 2art-4b* array, then two elements of the 1from-array* correspond to one element of the 1to-array*. If 2bitblt* 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 2bitblt* goes outside the bounds of the destination array, it signals an error. If 1src* is an element of the source rectangle, and 1dst* is the corresponding element of the destination rectangle, then 2bitblt* changes the value of 1dst* to 2(boole 1alu* 1src* 1dst*)*. See the 2boole* function (4(NUMBERS-2)Logical Operations on Numbers*). There are symbolic names for some of the most useful 1alu* functions; they are 2tv:alu-seta* (plain copy), 2tv:alu-ior* (inclusive or), 2tv:alu-xor* (exclusive or), and 2tv:alu-andca* (and with complement of source). 2bitblt* is written in highly-optimized microcode and goes very much faster than the same thing written with ordinary 2aref* and 2aset* operations would. Unfortunately this causes 2bitblt* to have a couple of strange restrictions. Wrap-around does not work correctly if 1from-array* is an indirect array with an index-offset. 2bitblt* signals an error if the second dimensions of 1from-array* and 1to-array* are not both integral multiples of the machine word length. For 2art-1b* arrays, the second dimension must be a multiple of 32., for 2art-2b* arrays it must be a multiple of 16., etc. =Node: Order of Array Elements =Text: 3ORDER OF ARRAY ELEMENTS* Currently, multi-dimensional arrays are stored in row-major order, as in Maclisp., and as specified by Common Lisp. This means that successive memory locations differ in the last subscript. In older versions of the system, arrays were stored in column-major order. Most user code has no need to know about which order array elements are stored in. There are three known reasons to care: use of multidimensional indirect arrays; paging efficiency (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 last subscript fastest in row-major order); and access to the TV screen or to arrays of pixels copied to or from the screen with 2bitblt*. The latter is the most important one. The bits on the screen are actually stored in rows, which means that the dimension that varies fastest has to be the horizontal position. As a result, if arrays are stored in row-major order, the horizontal position must be the second subscript, but if arrays are stored in column-major order, the horizontal position must be the first subscript. To ease the conversion of code that uses arrays of pixels, several bridging functions are provided: 3make-pixel-array* 1width* 1height* &rest 1options* This is like 2make-array* except that the dimensions of the array are 1width* and 1height*, in whichever order is correct. 1width* is used as the dimension in the subscript that varies fastest in memory, and 1height* as the other dimension. 1options* are passed along to 2make-array* to specify everything but the size of the array. 3pixel-array-width* 1array* Returns the extent of 1array*, a two-dimensional array, in the dimension that varies faster through memory. For a screen array, this is always the width. 3pixel-array-height* 1array* Returns the extent of 1array*, a two-dimensional array, in the dimension that varies slower through memory. For a screen array, this is always the height. 3ar-2-reverse* 1array* 1horizontal-index* 1vertical-index* Returns the element of 1array* at 1horizontal-index* and 1vertical-index*. 1horizontal-index* is used as the subscript in whichever dimension varies faster through memory. 3as-2-reverse* 1newvalue* 1array* 1horizontal-index* 1vertical-index* Stores 1newvalue* into the element of 1array* at 1horizontal-index* and 1vertical-index*. 1horizontal-index* is used as the subscript in whichever dimension varies faster through memory. Code that was written before the change in order of array indices can be converted by replacing calls to 2make-array*, 2array-dimension*, 2aref* and 2aset* with these functions. It can then work either in old systems or in new ones. In more complicated circumstances, you can facilitate conversion by writing code which tests this variable. 3sys:array-index-order* 1Constant* This is 2t* in more recent system versions which store arrays in row-major order (last subscript varies fastest). It is 2nil* in older system versions which store arrays in column-major order. =Node: Matrices and Systems of Linear Equations =Text: 3MATRICES AND SYSTEMS OF LINEAR EQUATIONS* 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 `2math:*' in the names. 3math:multiply-matrices* 1matrix-1* 1matrix-2* &optional 1matrix-3* Multiplies 1matrix-1* by 1matrix-2*. If 1matrix-3* is supplied, 2multiply-matrices* stores the results into 1matrix-3* and returns 1matrix-3*, which should be of exactly the right dimensions for containing the result of the multiplication; otherwise it creates an array to contain the answer and returns that. All matrices must be either one- or two-dimensional arrays, and the first dimension of 1matrix-2* must equal the second dimension of 1matrix-1*. 3math:invert-matrix* 1matrix* &optional 1into-matrix* Computes the inverse of 1matrix*. If 1into-matrix* is supplied, stores the result into it and returns it; otherwise it creates an array to hold the result and returns that. 1matrix* must be two-dimensional and square. The Gauss-Jordan algorithm with partial pivoting is used. Note: if you want to solve a set of simultaneous equations, you should not use this function; use 2math:decompose* and 2math:solve* (see below). 3math:transpose-matrix* 1matrix* &optional 1into-matrix* Transposes 1matrix*. If 1into-matrix* is supplied, stores the result into it and returns it; otherwise it creates an array to hold the result and returns that. 1matrix* must be a two-dimensional array. 1into-matrix*, if provided, must be two-dimensional and have exactly the right dimensions to hold the transpose of 1matrix*. 3math:determinant* 1matrix* Returns the determinant of 1matrix*. 1matrix* must be a two-dimensional square matrix. The next two functions are used to solve sets of simultaneous linear equations. 2math:decompose* takes a matrix holding the coefficients of the equations and produces the LU decomposition; this decomposition can then be passed to 2math: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 2math:decompose* once. In terms of the argument names used below, these two functions exist to solve the vector equation 1A* 1x* = 1b* for 1x*. 1A* is a matrix. 1b* and 1x* are vectors. 3math:decompose* 1a* &optional 1lu* 1ps* Computes the LU decomposition of matrix 1a*. If 1lu* is non-2nil*, stores the result into it and returns it; otherwise it creates an array to hold the result, and returns that. The lower triangle of 1lu*, with ones added along the diagonal, is L, and the upper triangle of 1lu* is U, such that the product of L and U is 1a*. Gaussian elimination with partial pivoting is used. The 1lu* array is permuted by rows according to the permutation array 1ps*, which is also produced by this function; if the argument 1ps* is supplied, the permutation array is stored into it; otherwise, an array is created to hold it. This function returns two values, the LU decomposition and the permutation array. 3math:solve* 1lu* 1ps* 1b* &optional 1x* This function takes the LU decomposition and associated permutation array produced by 2math:decompose* and solves the set of simultaneous equations defined by the original matrix 1a* given to 2math:decompose* and the right-hand sides in the vector 1b*. If 1x* is supplied, the solutions are stored into it and it is returned; otherwise an array is created to hold the solutions and that is returned. 1b* must be a one-dimensional array. 3math:list-2d-array* 1array* Returns a list of lists containing the values in 1array*, which must be a two-dimensional array. There is one element for each row; each element is a list of the values in that row. 3math:fill-2d-array* 1array* 1list* This is the opposite of 2math:list-2d-array*. 1list* should be a list of lists, with each element being a list corresponding to a row. 1array*'s elements are stored from the list. Unlike 2fillarray* (see 4(ARRAYS-3)Copying an Array*), if 1list* is not long enough, 2math:fill-2d-array* ``wraps around'', starting over at the beginning. The lists which are elements of 1list* also work this way. 3math:singular-matrix* (3sys:arithmetic-error* 3error*) 1Condition* This is signaled when any of the matrix manipulation functions in this section has trouble because of a singular matrix. (In some functions, such as 2math:determinant*, a singular matrix is not a problem.) The 2:matrix* operation on the condition instance returns the matrix which is singular. =Node: Planes =Text: 3PLANES* A 1plane* is effectively an array whose bounds, in each dimension, are plus-infinity and minus-infinity; all integers are legal as indices. Planes may be of any rank. When you create a plane, you do not need to specify any size, just the rank. You also specify a default value. 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. When you refer to an element for which space has not actually been allocated, you just get the default value. The regular array accessing functions don't work on planes. You can use 2make-plane* to create a plane, 2plane-aref* or 2plane-ref* to get the value of a component, and 2plane-aset* or 2plane-store* to store into a component. 2array-rank* works on planes. 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 2plane-store* has been done (and, usually, others which have never been altered). The lowest-coordinate corner of that rectangular region is given by the 2plane-origin* in the array leader. The highest-coordinate corner can be found by adding the 2plane-origin* to the 2array-dimensions* of the array. The 2plane-default* is the contents of all the elements of the plane that are not actually stored in the array. The 2plane-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 2plane-origin* remains all zeroes and you can use regular array functions, such as 2aref* and 2aset*, to access the portion of the plane that is actually stored. This can be useful to speed up certain algorithms. In this case you can even use the 2bitblt* function on a two-dimensional plane of bits or bytes, provided you don't change the 2plane-extension* to a number that is not a multiple of 32. 3make-plane* 1rank* &key 1type* 1default-value* 1extension* 1initial-dimensions* 1initial-origins* Creates and returns a plane. 1rank* is the number of dimensions. The keyword arguments are 1type* The array type symbol (e.g. 2art-1b*) specifying the type of the array out of which the plane is made. 1default-value* The default component value as explained above. 1extension* The amount by which to extend the plane, as explained above. 1initial-dimensions* 2nil* or a list of integers whose length is 1rank*. If not 2nil*, each element corresponds to one dimension, specifying the width to allocate the array initially in that dimension. 1initial-origins* 2nil* or a list of integers whose length is 1rank*. If not 2nil*, each element corresponds to one dimension, specifying the smallest index in that dimension for which storage should initially be allocated. Example: 3(make-plane 2 :type 'art-4b :default-value 3)* creates a two-dimensional plane of type 2art-4b*, with default value 23*. 3plane-origin* 1plane* A list of numbers, giving the lowest coordinate values actually stored. 3plane-default* 1plane* This is the contents of the infinite number of plane elements that are not actually stored. 3plane-extension* 1plane* The amount to extend the plane by, in any direction, when 2plane-store* is done outside of the currently-stored portion. 3plane-aref* 1plane* &rest 1subscripts* 3plane-ref* 1plane* 1subscripts* These two functions return the contents of a specified element of a plane. They differ only in the way they take their arguments; 2plane-aref* wants the subscripts as arguments, while 2plane-ref* wants a list of subscripts. 3plane-aset* 1datum* 1plane* &rest 1subscripts* 3plane-store* 1datum* 1plane* 1subscripts* These two functions store 1datum* into the specified element of a plane, extending it if necessary, and return 1datum*. They differ only in the way they take their arguments; 2plane-aset* wants the subscripts as arguments, while 2plane-store* wants a list of subscripts. =Node: Maclisp Array Compatibility =Text: 3MACLISP ARRAY COMPATIBILITY* 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). Float 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 Zetalisp does not use special array types for them. See the descriptions of 2read* (4(READPRINT-3)Expression Input Functions*) and 2intern* (4(PACKAGES-2)Packages and Interning*) for information about readtables and obarrays (packages). There are no `dead'' arrays, nor are Multics ``external'' arrays provided. The 2arraycall* function exists for compatibility but should not be used (see 2aref*, 4(ARRAYS-2)Accessing Array Elements*.) Subscripts are always checked for validity, regardless of the value of 2*rset* and whether the code is compiled or not. However, in a multi-dimensional array, an error is caused only 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 occurs despite the fact that the reference is invalid; but if you refer to element 1 by 100, an error occurs. In other words, subscript errors are caught if and only if they refer to storage outside the array; some errors are undetected, but they can only clobber (alter randomly) some other element of the same array, not something completely unpredictable. 2loadarrays* and 2dumparrays* are not provided. However, arrays can be put into QFASL files; see 4(COMPILER-2)Putting Data in QFASL Files*. The 2*rearray* function is not provided, since not all of its functionality is available in Zetalisp. Its most common uses are implemented by 2adjust-array-size*. In Maclisp, arrays are usually kept on the 2array* 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 2array*, 2*array*, and 2store* functions are provided, and when arrays are applied to arguments, the arguments are treated as subscripts and 2apply* returns the corresponding element of the array. 3array* "e 1symbol* 1type* &eval &rest 1dims* Creates an 2art-q* type array in 2default-array-area* with the given dimensions. (That is, 1dims* is given to 2make-array* as its first argument.) 1type* is ignored. If 1symbol* is 2nil*, the array is returned; otherwise, the array is put in the function cell of 1symbol*, and 1symbol* is returned. 3*array* 1symbol* 1type* &rest 1dims* Is like 2array*, except that all of the arguments are evaluated. 3store* 1array-ref* 1x* 1Special Form* Stores 1x* into the specified array element. 1array-ref* should be a form which references an array by calling it as a function (2aref* forms are not acceptable). First 1x* is evaluated, then 1array-ref* is evaluated, and then the value of 1x* is stored into the array cell last referenced by a function call, presumably the one in 1array-ref*. 3xstore* 1x* 1array-ref* This is just like 2store*, 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 2store* special form into, and should never be used by programs. 3arraycall* 1ignored* 1array* &rest 1subscripts* 2(arraycall t 1array* 1sub1* 1sub2*...)* is the same as 2(aref 1array* 1sub1* 1sub2*...)*. It exists for Maclisp compatibility.