CommonLisp-Compatible Array Functions

File:		<lispusers>CMLARRAY.tty
Revised:	Feb 21, Jul 1, and Sep 28, 1983, by JonL White



    The following functions are based on the definitions in the
CommonLisp community, and provide many features lacking in Interlisp's
ARRAY support, in particular multi-dimensional arrays, shared arrays,
and super-fast accessing ("open-coding" of access with "unsafe"
primitives).  These definitions follow those from the "Excelsior" edition
of the CommonLisp manual (5 August 1983, copyright Guy L. Steele Jr.)
and some of the prose below is reproduced from the aforesaid "Excelsior" 
edition by permission.

                    Documentation Terminology

    Not all options and features of the Common Lisp specifiction are 
implemented; descriptions of limitations are encolsed as notes within 
double square brackets.  Furthermore, for the benefit of Interlisp-D users, 
some non-portable extensions have been made, and these are described as 
noted within single square brackets.

    A number of functions take arguments in "keyword" format; this means
that the arglist, after some point, alternates between an argument which
names the meaning of the next argument and the next "real" argument.
E.g., suppose  COLORMYWORLD is a function with conceptually dozens
of parameters, but which is typically called with only one or two of
them set to a non-default value.  Then you might see
    (COLORMYWORLD SOMEBITMAP 'HUE BLUE 'DURATION 5HOURS)
where the first argument is "required", but all the others are optional
and are obtained from the appropriate pair in the real arglist;  in this
example, one such "keyword" argument is called HUE, and it will be set 
to the value of the variable BLUE; also "coloring" will last for a
duration of time found in the variable 5HOURS.

    As a general rule, any symbol ("litatom" in the Interlisp sense)
which has a "-" in its name, will have those "-"'s removed in the
Interlisp incarnation (because of weird potential interaction with 
CLISP).  Thus, MAKE-ARRAY in the CommonLisp manual becomes MAKEARRAY
in the Interlisp world.  Also, since Interlisp doesn't have &optional,
&rest, or &key argument spreading, then any function with such an
argument spectrum will be implemented as a no-spread lambda; curly
brackets will enclose the name for a sequence of such arguments.



                        Creation of Arrays

    An array, for the purpose of this documentation, is an instance of a
new datatype (called CMLARRAY), and is not related to the previously-
documented Interlisp array facility.  By convention, all indexing in the
CommonLisp world is 0-origin.

(MAKEARRAY  <dimensionslst>  ... {keyword-arguments} ... )

    <dimensionslst> is a list of non-negative integers that are to be
the dimensions of the array; the length of the list will be the rank, or
dimensionality, of the array.  Note that if <dimensionslst> is NIL, then 
a zero-dimensional array is created.  For convenience when making a one-
dimensional array, the single dimension may be provided as an integer 
rather than a list of one integer.  

The keyword arguments are:
    ELEMENTTYPE
      -  T, [or NIL, or POINTER] means that the elements are all  general
           Lisp "pointers"; this is the default.
      -  FIXNUM, [or FIXP, or CELL] for entries which are integers stored 
           as 2's complement 32-bits [[31-bits in Interlisp/VAX, 36-bits
           in Interlisp-10]]
      -  FLONUM, [or FLOATP] entries are all 32-bit IEEE format floating-point
           [[36-bit pdp10 format for Interlisp-10]]
      The following type specifiers are sub-types of INTEGER for which the
      accessing is much more efficient than for other random field sizes.   
      -  (MOD 65536) [or DOUBLEBYTE; or additionally, for Interlisp-D only,
           WORD or SMALLPOSP] for 16-bit non-negative integers.
      -  (MOD 256) [or BYTE, or CHARACTER] for 8-bit non-negative integers.
      -  (MOD 16) [or NIBBLE] for  4-bit non-negative integers.
      -  (MOD 2), or BIT, for single-bit entries.
      [[In general, the CommonLisp type heirarchy isn't supported; thus only
        the explicit names above will work.  However, for Interlisp-D, as of
        28-Sep-83, the type (MOD n) for any reasonable "n", is supported.]]
    INITIALELEMENT 
      -  Argument must be a quantity of the type specified by the ELEMENTTYPE 
          argument, and is used to initalize all the entries of the array.  
          Default is NIL for pointer type, and zero for numeric types.
    INITIALCONTENTS 
      -  If the array is zero-dimensional, the this specifies its contents;
          otherwise, it must a sequence whose length is equal to the first
          dimension, and each element thereof must be a nested structure for 
          an array whose dimensions are the remaining dimensions, and so on.
    DISPLACEDTO
      -  Argument will be an array whose linearized data segment will be 
          shared with the one being "made";  see also the DISPLACEDOFFSET 
          argument also.   
    DISPLACEDINDEXOFFSET
      -  When the data vector is being "shared", this specifies the offset 
          from the origin of the data vector at which the new array will have 
          its zero-origin.

The implementational constraints, as specified by the symbolic constants 
ARRAY-RANK-LIMIT, ARRAY-DIMENSION-LIMIT, and ARRAY-TOTAL-SIZE-LIMIT are: 
Ranks up to 63 are supported; each individual dimension of an array is 
constrained only to be a FIXP; in Interlisp-D, the total storage for the 
data block of an array may not exceed (2^16-5)*2^5 bits, and since a pointer 
requires 32 bits, then an array may contain up to 2^16-5 pointer elements, 
or 2^18-20 byte elements; Interlisp/VAX and Interlisp-10 may have other 
constraints.

[[The following limitations exist as of 9-MAY-84:
 (1) the :FILL-POINTER keyword argument is not implemented at all; 
 (2) all arrays automatically have the :ADJUSTABLE property;
 (3) the "nested structures" used to specify the :INITIAL-CONTENTS may be
     either another array of the same dimensionality, or else just lists of
     lists.
 (4) the symbolic constants ARRAY-RANK-LIMIT, ARRAY-DIMENSION-LIMIT, and
     ARRAY-TOTAL-SIZE-LIMIT are not actually in the code.  Just be aware
     of these limits by reading the documentation presented above.]]

Examples:
    (MAKEARRAY 5)  -  Create a one-dimensional array of five elements
    (MAKEARRAY '(3 4) 'ELEMENTTYPE '(MOD 256))  -- Create a two-
        dimensional array, 3 by 4, with 8-bit elements;
    (SETQ A (MAKEARRAY '(4 2 3) 'INITIALCONTENTS 
                       '(((a b c) (1 2 3))
                         ((d e f) (3 1 2))
                         ((g h i) (2 3 1))
                         ((j k l) (0 0 0)))))
    (MAKEARRAY '(4 2 3) 'INITIALCONTENTS A)
    (SETQ B (MAKEARRAY 107 'ELEMENTTYPE 'BIT))  
    (SETQ C (MAKEARRAY   8 'ELEMENTTYPE 'BYTE 
                           'DISPLACEDTO  A 
                           'DISPLACEDINDEXOFFSET 51)
    Thus B and C share their data portion; the second element of C, with 
      index 1, is the byte obtained by concatening the bits with indices 67 
      through 74 of B.   Note that element type specification of BYTE is 
      equivalent to that in the first example of (MOD 256).  

Compatibililty note: For multi-dimension arrays, both LispMachineLisp and 
FORTRAN store in column-major order; MacLisp stores arrays in row-major order.
A "row" is the collection of all elements obtained by holding all but the
last index constant, and cycling through that index in order from 0 to its
limit.  [This package generally stores in row-major order, but there may be 
ocasional "gaps" in the index-sequencing if the ALIGNMENT options is used.
See below for a description of the non-CommonLisp option ALIGNMENT.]




              Accessing and Changing the Elements of an Array

The main primitive to access the elements of an array is called AREF
(for "Array REFerence of element").

(AREF <array> ... {subscripts} ... )
    This returns the element of <array> specified by the subscripts (which 
are all the remaining arguments after <array>), and each subscript must be 
a non-negative integer less than the corresponding array dimension.

[The main primitive to change the contents of an array is called ASET  (for
 "Array SET value of element"), modeled after the MIT Lisp Machine name.
 Ultimately, ASET will operate so as to translate into the same code that
 SETF would have produced thus Interlisp users need not fear that such code 
 won't run on a "by-the-book" CommonLisp implementation.
    (ASET <newvalue> <array> ... {subscripts} ... )
 Changes the contents of the element of <array> accessed by 
    (AREF <array> ... {subscripts} ... )
 to be <newvalue>.]

[[CommonLisp does not require separate names for the update functions; 
updating may always be specified by the SETF construct, which takes an 
access expression and a "new value" much the way Interlisp's CHANGE does.
As of 28-Sep-83, there is no changetran entry for AREF, but it is expected
to be added someday.]]


                    Informational Functions

(ARRAYELEMENTTYPE <array>)
    Returns a type specifier for the set of objects that can be stored in 
<array>.  This set may be larger than the set requested when <array> was 
created; that is, 
    (ARRAYELEMENTTYPE (MAKEARRAY 5 'ELEMENTTYPE '(MOD 8)))
could be (MOD 8), or BYTE, or (MOD 256), etc., or even POINTER.
[[as of 28-Sep-83, only the types enumerated above under MAKEARRAY are 
supported; there is no "coercion upwards" in order to find a type-specifier 
which could hold the elements of some non-enumerated type.  Remember also
that the Interlisp-D version supports (MOD n) for all integral n.]]

(ARRAYRANK <array>)
    Returns the number of dimensions (axes) of <array>; to parallel the
indexing range, this is a zero-origin number and thus will be a non-negative 
integer.

(ARRAYDIMENSION <array> <axis-number>)
    Returns the length of dimension number <axis-number> of <array> [which
may be any kind of array, i.e., any instance of the \CMLARRAY datatype];
<axis-number> should be a non-negative integer less than the rank of <array>. 

(ARRAYDIMENSIONS <array> <optionslst>)
    Returns a list whose elements are the dimensions of <array>.   [The
second argument, <optionslst>, is not a CommonLisp argument -- it is provided 
in Interlisp so that one may specify the NOCOPY option.  Default action is 
to return a copy of the internal dimensions list.]

(ARRAYTOTALSIZE <array> <in-bits-p>)
    Returns the total number of elements in <array>, calculated as the product
of all the dimensions.  Roughly equivalent to 
    (APPLY 'TIMES (ARRAYDIMENSIONS <array>))
Note that the total size of a zero-dimensional array is 1.  [The second 
argument, <in-bits-p>, is not a CommonLisp argument -- it is provided in
Interlisp in order to find out how much space is actually occupied by the
array, including any gaps caused by the ALIGNMENT option.]

(ARRAYINBOUNDSP <array> ... {subscripts} ... )
    This predicate checks whether the subscripts are all legal subscripts 
for <array> and is true if they are;  otherwise it is false.  The subscripts 
must be integers.  The number of subscripts supplied must equal the rank of 
the array.   E.g., if HA is a three-dimensional array, then 
    (ARRAYINBOUNDSP HA 4 25 62) 
makes the check such that (AREF HA 4 25 62) will not cause an illegal 
subscript error.

(ARRAYROWMAJORINDEX <array> ... {subscripts} ... )
    This function takes an array and valid subscripts for the array, and
returns a single non-negative integer less than the total size of the array 
that identifies the accessed element in the row-major ordering of the elements.
The number of subscripts supplied must equal the rank of the arry.  Each
subscript must be a non-negative integer less than the corresponding array
dimension.  For a one-dimensional array, the result of this function always
equals the supplied subscript.  [However, if the ALIGNMENT option is used for
a multi-dimensional array in Interlisp-D, then the maximum linearized index 
will exceed the value returned by ARRAYTOTALSIZE.  In such a case, the value
returned by (ARRAYTOTALSIZE <array> T) will be the field size per element
times one plus the maximum linearized index.   The quantity
    (fetch (CMLARRAY CMLIMAX) of <array>)
will always be this maximum linearized index.]  




          Changing the Dimensions of an Array

(ADJUSTARRAY <array> <dimensionslst>)
    Takes an array, and a list of dimensions just as with MAKEARRAY; the
number of dimensions specified by <dimensionslst> must equal the rank of
<array>.  Returns <array>, whose components have been updated to conform
to the new specifications (but if the new dimensions require more space in
the block data area,  this will cause a copying into a newly allocated block,
and <array> will be DISPLACEDTO to this new block.)
[[None of the keyword options mentioned in the CommonLisp manual are supported
as of 28-Sep-83.]]



      Extensions to the Interlisp CommonLisp Array Functions

Although the following facilities aren't specified by the "Excelsior Edition",
they may be quite useful in Interlisp-D systems programming:

 *) Filepkg com:  CMLARRAYS  is similar to the BITMAPS com -- namely
      (CMLARRAYS <var1> <var2> <var3> . . . )
    will save and restore the value of each global variable <vari>, assuming
    it holds a CMLARRAY.

 *) Additional ELEMENTTYPE values for MAKEARRAY:
        -  XPOINTER is like POINTER, except that the entries aren't reference
             counted for the garbage collector;  beware, beware!
        -  DISPLACEDTOBASE is like DISPLACEDTO except its value is
             just a random pointer/address, rather than another CMLARRAY.
             This way, one can use the CommonLisp array functions to access
             parts of Interlisp-D's memory such as the screen bitmap.
        -  ALIGNMENT is for multi-dimensional arrays;  each row may be 
             required to begin a multiple of some integer, with nulls or zeros
             filling any space between "rows".  For example, it might be that 
             a bitmap array must have the raster scans beginning on a word
             boundary;  since there are 16 bits/word, then an alignment of 16
             would be used.

 *) Functions Interfaceing to LISTPs:
      (LISTARRAY <array> <startindex> <endindex>)
        The second and third arguments are optional, and have meaning similar 
        to the corresponding arguments to SUBSTRING, but negative indicies
        aren't allowed.  Elements are selected from the <array> in row-major
        order, and CONS's up into a list.
      (FILLARRAY <array> <list> <startindex> <endindex>)
        Similar to LISTARRAY, except that the elements of the <list> are 
        stored into the corresponding parts of the <array>.  As a convenience,
        if <list> isn't a LISTP, then it is converted into (LIST <list>); 
        furthermore, if there aren't enough elements in <list> to fill out the
        range specified by <startindex> and <no.of.elements>, then the last 
        element of <list> is repeated until finished.  Thus, for example, one 
        could fill an array with a single value by a construct like 
            (FILLARRAY SOMEARRAY (LIST THISVAL))

 *) "Fast" accessing functions:
    (PAREF  <array> ... {subscripts} ... )
    (NAREF  <array> ... {subscripts} ... )
    (LAREF  <array> ... {subscripts} ... )
    (16AREF <array> ... {subscripts} ... )
    (8AREF  <array> ... {subscripts} ... )
    (4AREF  <array> ... {subscripts} ... )
    (1AREF  <array> ... {subscripts} ... )
    These are essentially the same as AREF, but have a  consequence that, for
      PAREF, <array> must be a POINTER or T array; and correspondingly, for
      NAREF a FIXNUM array,  for LAREF a FLONUM array, for 16AREF a
      DOUBLEBYTE or (MOD 65536) array, for 8AREF a BYTE or (MOD 256)
      array,  for 4AREF a NIBBLE or (MOD 16) array, and for 1AREF a BIT or
     (MOD 2) array.  
    Furthermore, when compiled, these functions will be compiled "open", with 
      little or no error checking, realizing orders of magnitude speed-up over 
      AREF;  however, *** there is no certification as to what kind of value
      will be returned should the subscripts be "out of range".   To aid in
      debugging, the run-time code actually toggles on the global variable
      AREFSissyFLG, and when the flg is non-NIL, will call the function 
      AREF instead of the fast-but-unchecked "in-line" accessing.
    However, one may omit even these simple checks for "all out, no holds 
      barred" code by prefixing a \ to these names (e.g. \PAREF ...)

 *)  "Fast"  setting functions:
    (PASET  <newvalue> <array> ... {subscripts} ... )
    (NASET  <newvalue> <array> ... {subscripts} ... )
    (LASET  <newvalue> <array> ... {subscripts} ... )
    (16ASET <newvalue> <array> ... {subscripts} ... )
    (8ASET  <newvalue> <array> ... {subscripts} ... )
    (4ASET  <newvalue> <array> ... {subscripts} ... )
    (1ASET  <newvalue> <array> ... {subscripts} ... )
    These are essentially the same as ASET, but have a consequence that, for
      PASET, <array> must be a POINTER or T array; and correspondingly, for 
      NASET a FIXNUM array, for LAREF a FLONUM array, for 16ASET a DOUBLEBYTE 
      or (MOD 65536) array, for 8ASET a BYTE or (MOD 256) array, for 4ASET a 
      NIBBLE or (MOD 16) array, and for 1ASET a BIT or (MOD 2) array.  
    Furthermore, when compiled, these functions will be compiled "open", with 
      little or no error checking, realizing orders of magnitude speed-up over
      ASET;  although some checking is performed to insure memory system
      integrity (i.e. that the word modified will actually be within the data
      block of the specified array), **** there is no certification as to 
      which word will be clobbered should the subscripts be "out of range".  As
      with AREF, the run-time code toggles on the global variable AREFSissyFLG,
      and will call the function ASET when the flg is non-NIL.
    However, one may omit even these simple checks for "all out, no holds 
      barred" code by prefixing a \ to these names (e.g. \PASET ...).  If
      you use this option, there is no guarantee of memory integrity, and
      likely no one will want to listen to reports of any "system" bugs
      encountered while such "unsafe" options were being exercised.