






                         CHAPTER  9


                     Arrays and Vectors




     Arrays and vectors are two means of  expressing  aggre-
gate  data objects in FRANZ LISP.  Vectors may be thought of
as sequences of data.  They are intended as  a  vehicle  for
user-defined  data  types.   This  use  of  vectors is still
experimental and subject to  revision.   As  a  simple  data
structure,  they  are similar to hunks and strings.  Vectors
are used to implement closures, and are useful  to  communi-
cate with foreign functions.  Both of these topics were dis-
cussed in Chapter 8.  Later in this chapter, we describe the
current  implementation of vectors, and will advise the user
what is most likely to change.

     Arrays in FRANZ LISP provide a programmable data struc-
ture  access  mechanism.   One  possible  use for FRANZ LISP
arrays is to implement Maclisp style arrays which are simple
vectors of fixnums, flonums or general lisp values.  This is
described in more detail in 9.3 but first we  will  describe
how array references are handled by the lisp system.

     The structure of an array object is given in 1.3.10 and
reproduced here for your convenience.


8_______________________________________________________________
  Subpart name     Get value   Set value          Type

8______________________________________________________________________________________________________________________________
 access function   getaccess   putaccess      binary, list
                                                or symbol
8_______________________________________________________________
    auxiliary       getaux      putaux           lispval
8_______________________________________________________________
      data         arrayref     replace    block of contiguous
                                  set            lispval
8_______________________________________________________________
     length        getlength   putlength         fixnum
8_______________________________________________________________
      delta        getdelta    putdelta          fixnum
8_______________________________________________________________
7|7|7|7|7|7|7|7|7|7|7|7|










                |7|7|7|7|7|7|7|7|7|7|7|










                            |7|7|7|7|7|7|7|7|7|7|7|










                                        |7|7|7|7|7|7|7|7|7|7|7|










                                                              |7|7|7|7|7|7|7|7|7|7|7|















   9.1.  general arrays   Suppose the evaluator is  told  to
      evaluate (_f_o_o _a _b) and the function cell of the symbol
      foo contains an  array  object  (which  we  will  call
      foo_arr_obj).   First  the evaluator will evaluate and
      stack the values of _a and _b.  Next it will  stack  the


9Arrays and Vectors                                       9-1







Arrays and Vectors                                       9-2


      array  object  foo_arr_obj.   Finally it will call the
      access function of foo_arr_obj.  The  access  function
      should  be  a  lexpr[] or a symbol whose function cell
      contains a lexpr.  The access function is  responsible
      for  locating  and  returning  a value from the array.
      The array access function is  free  to  interpret  the
      arguments  as it wishes.  The Maclisp compatible array
      access function which  is  provided  in  the  standard
      FRANZ  LISP  system  interprets  the arguments as sub-
      scripts in the same way as languages like Fortran  and
      Pascal.

           The array access function  will  also  be  called
      upon  to  store  elements  in the array.  For example,
      (_s_t_o_r_e (_f_o_o _a _b) _c) will automatically expand to  (foo
      c  a  b)  and when the evaluator is called to evaluate
      this, it will evaluate the arguments _c, _b and _a.  Then
      it will stack the array object (which is stored in the
      function cell of foo) and call the array access  func-
      tion  with  (now)  four  arguments.   The array access
      function must be able to tell this is a  store  opera-
      tion,  which it can do by checking the number of argu-
      ments it has been given (a  lexpr  can  do  this  very
      easily).



   9.2.  subparts of an array object   An array  is  created
      by allocating an array object with _m_a_r_r_a_y and  filling
      in the fields.  Certain lisp functions  interpret  the
      values  of the subparts of the array object in special
      ways as described  in  the  following  text.   Placing
      illegal  values  in  these subparts may cause the lisp
      system to fail.



      9.2.1.  access function   The purpose  of  the  access
         function has been described above.  The contents of
         the access function should be  a  lexpr,  either  a
         binary  (compiled  function) or a list (interpreted
         function).  It may also be a symbol whose  function
         cell  contains a function definition.  This subpart
         is used by _e_v_a_l, _f_u_n_c_a_l_l, and _a_p_p_l_y when evaluating
         array references.



____________________
9   []A lexpr is a function which accepts any number of argu-
ments which are evaluated before the function is called.



9                                      Printed: July 21, 1983







Arrays and Vectors                                       9-3


      9.2.2.  auxiliary   This can be used for any  purpose.
         If  it is a list and the first element of that list
         is the symbol unmarked_array then the data  subpart
         will  not  be marked by the garbage collector (this
         is used in the Maclisp compatible array package and
         has  the  potential  for  causing strange errors if
         used incorrectly).



      9.2.3.  data   This is either nil or points to a block
         of  data  space  allocated  by  _s_e_g_m_e_n_t  or  _s_m_a_l_l-
         _s_e_g_m_e_n_t.



      9.2.4.  length   This is a fixnum whose value  is  the
         number of elements in the data block.  This is used
         by the garbage collector and by _a_r_r_a_y_r_e_f to  deter-
         mine if your index is in bounds.



      9.2.5.  delta   This is a fixnum whose  value  is  the
         number  of bytes in each element of the data block.
         This will be four for an array of fixnums or  value
         cells,  and eight for an array of flonums.  This is
         used by the garbage collector and _a_r_r_a_y_r_e_f as well.



   9.3.  The Maclisp compatible array package

           A Maclisp style array is similar to what is known
      as  arrays  in other languages: a block of homogeneous
      data elements which is indexed by one or more integers
      called  subscripts.  The data elements can be all fix-
      nums, flonums or general lisp objects.   An  array  is
      created  by  a  call  to the function _a_r_r_a_y or *_a_r_r_a_y.
      The only difference is that *_a_r_r_a_y evaluates its argu-
      ments.   This call: (_a_r_r_a_y _f_o_o _t _3 _5) sets up an array
      called foo of dimensions 3 by 5.  The  subscripts  are
      zero  based.  The first element is (_f_o_o _0 _0), the next
      is (_f_o_o _0 _1) and so on up to (_f_o_o _2 _4).  The  t  indi-
      cates  a  general  lisp  object array which means each
      element of foo can be any type.  Each element  can  be
      any  type  since  all that is stored in the array is a
      pointer to a  lisp  object,  not  the  object  itself.
      _A_r_r_a_y  does  this  by  allocating an array object with
      _m_a_r_r_a_y and then allocating a segment of 15 consecutive
      value  cells  with _s_m_a_l_l-_s_e_g_m_e_n_t and storing a pointer
      to that segment in  the  data  subpart  of  the  array
      object.   The  length  and  delta subpart of the array


                                      Printed: July 21, 1983







Arrays and Vectors                                       9-4


      object are filled in (with 15 and 4 respectively)  and
      the  access  function  subpart  is set to point to the
      appropriate  array  access  function.   In  this  case
      there is a special access function for two dimensional
      value cell arrays called arrac-twoD, and  this  access
      function  is  used.   The  auxiliary subpart is set to
      (t 3 5) which describes the  type  of  array  and  the
      bounds of the subscripts. Finally this array object is
      placed in the function cell of the  symbol  foo.   Now
      when (_f_o_o _1 _3) is evaluated, the array access function
      is invoked with three arguments: 1, 3  and  the  array
      object.   From the auxiliary field of the array object
      it gets a description of  the  particular  array.   It
      then determines which element (_f_o_o _1 _3) refers to  and
      uses arrayref to extract that element.  Since this  is
      an  array  of  value cells, what arrayref returns is a
      value cell whose value is what we want, so we evaluate
      the   value  cell  and  return  it  as  the  value  of
      (_f_o_o _1 _3).

           In Maclisp the call (_a_r_r_a_y _f_o_o _f_i_x_n_u_m _2_5) returns
      an  array  whose  data  object is a block of 25 memory
      words.  When fixnums are stored  in  this  array,  the
      actual  numbers  are stored instead of pointers to the
      numbers as is done  in  general  lisp  object  arrays.
      This  is  efficient  under  Maclisp but inefficient in
      FRANZ LISP since every time  a  value  was  referenced
      from an array it had to be copied and a pointer to the
      copy returned to prevent aliasing[].  Thus  t,  fixnum
      and  flonum  arrays  are  all  implemented in the same
      manner.  This should not affect the  compatibility  of
      Maclisp  and  FRANZ  LISP.  If there is an application
      where a block of fixnums or flonums is required,  then
      the  exact  same effect of fixnum and flonum arrays in
      Maclisp can be  achieved  by  using  fixnum-block  and
      flonum-block  arrays.  Such arrays are required if you
      want to pass a large number of arguments to a  Fortran
      or C coded function and then get answers back.

           The Maclisp compatible array package is just  one
      example  of  how  a general array scheme can be imple-
      mented.  Another type of  array  you  could  implement
      would  be  hashed  arrays.   The  subscript  could  be
____________________
9   []Aliasing is when  two  variables  are  share  the  same
storage  location.   For  example  if  the copying mentioned
weren't done then after (_s_e_t_q _x (_f_o_o _2)) was done, the value
of x and (foo 2) would share the same location.  Then should
the value of (foo 2) change, x's value would change as well.
This  is  considered  dangerous and as a result pointers are
never returned into the data space of arrays.



9                                      Printed: July 21, 1983







Arrays and Vectors                                       9-5


      anything, not just  a  number.   The  access  function
      would  hash the subscript and use the result to select
      an array element.  With the generality of arrays  also
      comes  extra cost; if you just want a simple aggregate
      of (less than 128) general lisp objects you  would  be
      wise to look into using hunks.



   9.4.   vectors    Vectors  were  invented  to   fix   two
      shortcommings with hunks.  They can be longer than 128
      elements.  They also have a tag associated with  them,
      which is intended to say, for example, "Think of me as
      an _B_l_o_b_i_t."  Thus a vector is an arbitrary sized  hunk
      with a property list.

           Continuing the example, the lisp kernel  may  not
      know how to print out or evaluate _b_l_o_b_i_t_s, but this is
      information which will be common to all  _b_l_o_b_i_t_s.   On
      the  other hand, for each individual blobits there are
      particulars  which  are  likely  to  change,  (height,
      weight,  eye-color).  This is the part that would pre-
      viously have been stored in the individual entries  in
      the hunk, and are stored in the data slots of the vec-
      tor.  Once again we summarize the structure of a  vec-
      tor in tabular form:


8         ________________________________________________
          Subpart name   Get value   Set value    Type

8         ________________________________________________________________________________________________
            datum[_i]       vref        vset      lispval
8         ________________________________________________
            property       vprop     vsetprop    lispval
                                     vputprop
8         ________________________________________________
              size         vsize         -       fixnum
8         ________________________________________________
7        |7|7|7|7|7|7|7|






                      |7|7|7|7|7|7|7|






                                  |7|7|7|7|7|7|7|






                                              |7|7|7|7|7|7|7|






                                                        |7|7|7|7|7|7|7|








      Vectors are created specifying size and optional  fill
      value using the function (_n_e_w-_v_e_c_t_o_r  'x_size ['g_fill
      ['g_prop]]), or by  initial  values:  (_v_e_c_t_o_r  ['g_val
      ...]).



   9.5.  anatomy  of  vectors    There  are  some  technical
      details about vectors, that the user should know:








9                                      Printed: July 21, 1983







Arrays and Vectors                                       9-6


      9.5.1.  size   The user is not free to alter this.  It
         is noted when the vector is created, and is used by
         the garbage collector.  The garbage collector  will
         coallesce  two free vectors, which are neighbors in
         the heap.  Internally, this is kept as  the  number
         of  bytes of data.  Thus, a vector created by (_v_e_c_-
         _t_o_r 'foo), has a size of 4.



      9.5.2.  property   Currently, we expect  the  property
         to  be either a symbol, or a list whose first entry
         is a symbol.  The symbols fclosure  and  structure-
         value-argument  are  magic,  and  their  effect  is
         described in Chapter  8.   If  the  property  is  a
         (non-null)  symbol,  the vector will be printed out
         as <symbol>[<size>]. Another case is  if  the  pro-
         perty  is  actually  a (disembodied) property-list,
         which contains a value  for  the  indicator  print.
         The value is taken to be a Lisp function, which the
         printer will invoke with two arguments:  the vector
         and the current output port.  Otherwise, the vector
         will be printed as vector[<size>].  We  have  vague
         (as  yet unimplemented) ideas about similar mechan-
         isms for evaluation  properties.   Users  are  cau-
         tioned  against  putting anything other than nil in
         the property entry of a vector.



      9.5.3.  internal order   In memory, vectors start with
         a  longword containing the size (which is immediate
         data within the vector).  The next cell contains  a
         pointer  to  the property.  Any remaining cells (if
         any) are for data.  Vectors are handled differently
         from  any  other  object  in  FRANZ LISP, in that a
         pointer to a vector is pointer to  the  first  data
         cell,  i.e.  a pointer to the _t_h_i_r_d longword of the
         structure.  This was done for  efficiency  in  com-
         piled   code  and  for  uniformity  in  referencing
         immediate-vectors  (described  below).   The   user
         should  never return a pointer to any other part of
         a vector, as this may cause the  garbage  collector
         to follow an invalid pointer.



   9.6.  immediate-vectors   Immediate-vectors  are  similar
      to  vectors.   They  differ,  in  that binary data are
      stored in space directly within the vector.  Thus  the
      garbage  collector will preserve the vector itself (if
      used), and will only traverse the property cell.   The
      data  may  be  referenced as longwords, shortwords, or


                                      Printed: July 21, 1983







Arrays and Vectors                                       9-7


      even bytes.   Shorts  and  bytes  are  returned  sign-
      extended.   The  compiler  open-codes such references,
      and will avoid  boxing  the  resulting  integer  data,
      where  possible.   Thus, immediate vectors may be used
      for efficiently processing character data.   They  are
      also  useful in storing results from functions written
      in other languages.


8        __________________________________________________
         Subpart name   Get value    Set value     Type

8        ____________________________________________________________________________________________________
           datum[_i]     vrefi-byte   vseti-byte   fixnum
                        vrefi-word   vseti-word   fixnum
                        vrefi-long   vseti-long   fixnum
8        __________________________________________________
           property       vprop       vsetprop    lispval
                                      vputprop
8        __________________________________________________
             size         vsize          -        fixnum
                        vsize-byte                fixnum
                        vsize-word                fixnum
8        __________________________________________________
7       |7|7|7|7|7|7|7|7|7|7|7|










                     |7|7|7|7|7|7|7|7|7|7|7|










                                  |7|7|7|7|7|7|7|7|7|7|7|










                                               |7|7|7|7|7|7|7|7|7|7|7|










                                                         |7|7|7|7|7|7|7|7|7|7|7|












      To create immediate vectors specifying size  and  fill
      data,  you  can  use  the  functions _n_e_w-_v_e_c_t_o_r_i-_b_y_t_e,
      _n_e_w-_v_e_c_t_o_r_i-_w_o_r_d, or _n_e_w-_v_e_c_t_o_r_i-_l_o_n_g.  You  can  also
      use   the  functions  _v_e_c_t_o_r_i-_b_y_t_e,  _v_e_c_t_o_r_i-_w_o_r_d,  or
      _v_e_c_t_o_r_i-_l_o_n_g.  All of these functions are described in
      chapter 2.


























9                                      Printed: July 21, 1983



