Return to ch9.n CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / lisp / doc

Annotation of 43BSDTahoe/ucb/lisp/doc/ch9.n, revision 1.1

1.1     ! root        1: .\" Copyright (c) 1980 Regents of the University of California.
        !             2: .\" All rights reserved.  The Berkeley software License Agreement
        !             3: .\" specifies the terms and conditions for redistribution.
        !             4: .\"
        !             5: .\"    @(#)ch9.n       6.2 (Berkeley) 5/14/86
        !             6: .\"
        !             7: ." $Header: ch9.n 1.4 83/07/21 21:08:57 sklower Exp $
        !             8: .Lc Arrays\ and\ Vectors 9
        !             9: .pp
        !            10: Arrays and vectors are two means of expressing aggregate
        !            11: data objects in
        !            12: .Fr .
        !            13: Vectors may be thought of as sequences of data.
        !            14: They are intended as a vehicle for user-defined
        !            15: data types.
        !            16: This use of vectors is still experimental and subject
        !            17: to revision.
        !            18: As a simple data structure, they are similar to
        !            19: hunks and strings.
        !            20: Vectors are used to implement closures,
        !            21: and are useful to communicate with foreign functions.
        !            22: Both of these topics were discussed in Chapter 8.
        !            23: Later in this chapter,
        !            24: we describe the current implementation of vectors, and will
        !            25: advise the user what is most likely to change.
        !            26: .pp
        !            27: Arrays in 
        !            28: .Fr
        !            29: provide a programmable data structure access mechanism.
        !            30: One possible use for 
        !            31: .Fr
        !            32: arrays is to implement Maclisp style arrays which are simple vectors
        !            33: of fixnums, flonums or general lisp values.
        !            34: This is described in more detail in \(sc9.3 but first
        !            35: we will describe how array references are handled by
        !            36: the lisp system.
        !            37: .pp
        !            38: The structure of an array object is given in \(sc1.3.10 and reproduced here
        !            39: for your convenience.
        !            40: .(b
        !            41: .TS
        !            42: box center ;
        !            43: c | c | c | c .
        !            44: Subpart name   Get value       Set value       Type
        !            45: 
        !            46: =
        !            47: access function        getaccess       putaccess       binary, list
        !            48:                        or symbol
        !            49: _
        !            50: auxiliary      getaux  putaux  lispval
        !            51: _
        !            52: data   arrayref        replace block of contiguous
        !            53:                set     lispval
        !            54: _
        !            55: length getlength       putlength       fixnum
        !            56: _
        !            57: delta  getdelta        putdelta        fixnum
        !            58: .TE
        !            59: .)b
        !            60: .sh 2 "general arrays" \n(ch 1
        !            61: Suppose the evaluator is told to evaluate \fI(foo\ a\ b)\fP
        !            62: and the function cell of the symbol foo contains an array object
        !            63: (which we will call foo_arr_obj).
        !            64: First the evaluator will evaluate and stack the values of 
        !            65: .i a 
        !            66: and 
        !            67: .i b .
        !            68: Next it will stack the array object foo_arr_obj.
        !            69: Finally it will call the access function of foo_arr_obj.
        !            70: The access function should be a lexpr\*[\(dg\*]
        !            71: or a symbol whose 
        !            72: function cell contains a lexpr.
        !            73: .(f
        !            74: \*[\(dg\*]A lexpr is a function which accepts any number of arguments
        !            75: which are evaluated before the function is called.
        !            76: .)f
        !            77: The access function is responsible for locating and returning 
        !            78: a value from the array.
        !            79: The array access function is free to interpret the arguments as it wishes.
        !            80: The Maclisp compatible array access function which is provided 
        !            81: in the standard
        !            82: .Fr
        !            83: system interprets the arguments as subscripts in the same way as 
        !            84: languages like Fortran and Pascal.
        !            85: .pp
        !            86: The array access function will also be called upon to store elements in 
        !            87: the array.
        !            88: For example, \fI(store\ (foo\ a\ b)\ c)\fP
        !            89: will automatically expand to (foo c a b) and when the evaluator is called
        !            90: to evaluate this, it will evaluate the arguments 
        !            91: .i c , 
        !            92: .i b 
        !            93: and
        !            94: .i a .
        !            95: Then it will
        !            96: stack the array object (which is stored 
        !            97: in the function cell of foo) and call the array access function
        !            98: with (now) four arguments.
        !            99: The array access function must be able to tell this is a store operation,
        !           100: which it can do by checking the number of arguments it has been
        !           101: given (a lexpr can do this very easily).
        !           102: .sh 2 "subparts of an array object"
        !           103: An array is created by allocating an
        !           104: array object with
        !           105: .i marray
        !           106: and  filling in the fields.
        !           107: Certain lisp functions interpret the values of the subparts 
        !           108: of the array object in special
        !           109: ways as described in the following text.
        !           110: Placing illegal values in these subparts may cause
        !           111: the lisp system to fail.
        !           112: .sh 3 "access function"
        !           113: The purpose of the access function has been described above.
        !           114: The contents of the access function should be a lexpr, 
        !           115: either a binary (compiled function) or a list (interpreted function).
        !           116: It may also be a symbol whose function cell contains a function 
        !           117: definition.
        !           118: This subpart 
        !           119: is used by 
        !           120: .i eval , 
        !           121: .i funcall , 
        !           122: and 
        !           123: .i apply
        !           124: when evaluating array references.
        !           125: .sh 3 auxiliary
        !           126: This can be used for any purpose. If it is a list and the first element
        !           127: of that list is the symbol unmarked_array then the data subpart will
        !           128: not be marked by the garbage collector (this is used in the Maclisp
        !           129: compatible array package and has the potential for causing strange errors
        !           130: if used incorrectly).
        !           131: .sh 3 data
        !           132: This is either nil or points to a block of data space allocated by 
        !           133: .i segment 
        !           134: or 
        !           135: .i small-segment.
        !           136: .sh 3 length
        !           137: This is a fixnum whose value is the number of elements in the
        !           138: data block.  This is used by the garbage collector and by 
        !           139: .i arrayref
        !           140: to determine if your index is in bounds.
        !           141: .sh 3 delta
        !           142: This is a fixnum whose value is the number of bytes in each element of 
        !           143: the data block.
        !           144: This will be four for an array of fixnums or value cells, and eight
        !           145: for an array of flonums.
        !           146: This is used by the garbage collector and 
        !           147: .i arrayref
        !           148: as well.
        !           149: .sh 2 "The Maclisp compatible array package"
        !           150: .pp
        !           151: A Maclisp style array is similar to what is known as arrays in other
        !           152: languages: a block of homogeneous data elements which
        !           153: is indexed by one or more integers called subscripts.
        !           154: The data elements can be all fixnums, flonums or general lisp objects.
        !           155: An array is created by a call to the function 
        !           156: .i array 
        !           157: or \fI*array\fP.
        !           158: The only difference is that 
        !           159: .i *array
        !           160: evaluates its arguments.
        !           161: This call: 
        !           162: .i "(array foo t 3 5)"
        !           163: sets up an array called foo of dimensions 3 by 5.
        !           164: The subscripts are zero based. 
        !           165: The first element is \fI(foo\ 0\ 0)\fP, the next is \fI(foo\ 0\ 1)\fP
        !           166: and so on up to \fI(foo\ 2\ 4)\fP.
        !           167: The t indicates a general lisp object array which means each element of
        !           168: foo can be any type.
        !           169: Each element can be any type since all that is stored in the array is
        !           170: a pointer to a lisp object, not the object itself.
        !           171: .i Array 
        !           172: does this by allocating an array object
        !           173: with
        !           174: .i marray
        !           175: and then allocating a segment of 15 consecutive value cells with
        !           176: .i small-segment
        !           177: and storing a pointer to that segment in the data subpart of the array
        !           178: object.
        !           179: The length and delta subpart of the array object are filled in (with 15
        !           180: and 4 respectively) and the access function subpart is set to point to 
        !           181: the appropriate  array access function.
        !           182: In this case there is a special access function for two dimensional
        !           183: value cell arrays called arrac-twoD, and this access function is used.
        !           184: The auxiliary subpart is set to (t\ 3\ 5) which describes the type of array
        !           185: and the bounds of the subscripts.  
        !           186: Finally this array object is placed in the function cell of the symbol foo.
        !           187: Now when 
        !           188: .i "(foo 1 3)"
        !           189: is evaluated, the array access function is invoked with three arguments:
        !           190: 1, 3 and the array object.  From the auxiliary field of the
        !           191: array object it gets a description of the particular array.
        !           192: It then determines which element \fI(foo\ 1\ 3)\fP refers to  and 
        !           193: uses arrayref to extract that element.
        !           194: Since this is an array of value cells, what arrayref returns is a
        !           195: value cell whose value is what we want, so we evaluate the value cell
        !           196: and return it as the value of \fI(foo\ 1\ 3)\fP.
        !           197: .pp
        !           198: In Maclisp the call \fI(array\ foo\ fixnum\ 25)\fP
        !           199: returns an array whose data object is a block of 25 memory words.
        !           200: When fixnums are stored in this array, the actual numbers are 
        !           201: stored instead of pointers to the numbers as is done in general lisp
        !           202: object arrays.
        !           203: This is efficient under Maclisp but inefficient in
        !           204: .Fr
        !           205: since every time a value was referenced from an array it had to be copied
        !           206: and a pointer to the copy returned to prevent aliasing\*[\(dg\*].
        !           207: .(f
        !           208: \*[\(dg\*]Aliasing is when two variables are share the same storage location.
        !           209: For example if the copying mentioned weren't done then after 
        !           210: \fI(setq\ x\ (foo\ 2))\fP was done, the value of x and 
        !           211: (foo\ 2) would share the same 
        !           212: location.
        !           213: Then should the value of (foo\ 2) change, x's value would change as well.
        !           214: This is considered dangerous and as a result pointers are never returned
        !           215: into the data space of arrays.
        !           216: .)f
        !           217: Thus t, fixnum and flonum arrays are all implemented in the same 
        !           218: manner.
        !           219: This should not affect the compatibility of Maclisp
        !           220: and 
        !           221: .Fr .
        !           222: If there is an application where a block of fixnums or flonums is required,
        !           223: then the exact same effect of fixnum and flonum arrays in Maclisp
        !           224: can be achieved by using fixnum-block and flonum-block arrays.
        !           225: Such arrays are required if you want to pass a large number of arguments to a 
        !           226: Fortran or C coded function and then get answers back.
        !           227: .pp
        !           228: The Maclisp compatible array package is 
        !           229: just one example of how a general array scheme can be implemented.
        !           230: Another type of array you could implement would be hashed arrays.
        !           231: The subscript could be anything, not just a number.
        !           232: The access function would hash the subscript and use the result to
        !           233: select an array element.
        !           234: With the generality of arrays also comes extra cost; if you just
        !           235: want a simple aggregate of (less than 128) general lisp objects
        !           236: you would be wise to look into using hunks.
        !           237: .sh 2 vectors
        !           238: Vectors were invented to fix two shortcommings with hunks.
        !           239: They can be longer than 128 elements.  They also have a
        !           240: tag associated with them, which is intended to say, for example,
        !           241: "Think of me as an \fIBlobit\fP."  Thus a \fBvector\fP
        !           242: is an arbitrary sized hunk with a property list.
        !           243: .pp
        !           244: Continuing the example,
        !           245: the lisp kernel may not know how to print out
        !           246: or evaluate \fIblobits\fP, but this is information which will
        !           247: be common to all \fIblobits\fP.  On the other hand, for each
        !           248: individual blobits there are particulars which are likely to change,
        !           249: (height, weight, eye-color).  This is the part that would
        !           250: previously have been stored in the individual entries in the hunk,
        !           251: and are stored in the data slots of the vector.
        !           252: Once again we summarize the structure of a vector in tabular form:
        !           253: .(b
        !           254: .TS
        !           255: box center ;
        !           256: c | c | c | c .
        !           257: Subpart name   Get value       Set value       Type
        !           258: 
        !           259: =
        !           260: datum[\fIi\fP] vref    vset    lispval
        !           261: _
        !           262: property       vprop   vsetprop        lispval
        !           263:                vputprop
        !           264: _
        !           265: size   vsize   \-      fixnum
        !           266: .TE
        !           267: .)b
        !           268: Vectors are created specifying size and optional fill value using the
        !           269: function (\fInew-vector\fP  'x_size ['g_fill ['g_prop]]), or by
        !           270: initial values: (\fIvector\fP ['g_val ...]).
        !           271: .sh 2 "anatomy of vectors"
        !           272: There are some technical details about vectors, that the user should
        !           273: know:
        !           274: .sh 3 size
        !           275: The user is not free to alter this.  It is noted when the vector
        !           276: is created, and is used by the garbage collector.  The garbage
        !           277: collector will coallesce two free vectors, which are neighbors
        !           278: in the heap.  Internally, this is kept as the number of bytes
        !           279: of data.  Thus, a vector created by (\fIvector\fP 'foo), has a
        !           280: size of 4.
        !           281: .sh 3 property
        !           282: Currently, we expect the property to be either a symbol, or a list
        !           283: whose first entry is a symbol.  The symbols \fBfclosure\fP and
        !           284: \fBstructure-value-argument\fP are magic, and their effect is described in
        !           285: Chapter 8.  If the property is a (non-null) symbol, the vector
        !           286: will be printed out as <symbol>[<size>].  
        !           287: Another case is if the property is actually a (disembodied) property-list, which
        !           288: contains a value for the indicator \fBprint\fP.
        !           289: The value is taken to be a Lisp function, which the printer
        !           290: will invoke with two arguments:  the vector and the current output port.
        !           291: Otherwise, the vector will be printed as vector[<size>].
        !           292: We have vague (as yet unimplemented) ideas
        !           293: about similar mechanisms for evaluation properties.
        !           294: Users are cautioned against putting anything other than nil
        !           295: in the property entry of a vector.
        !           296: .sh 3 "internal order"
        !           297: In memory, vectors start with a longword containing the size
        !           298: (which is immediate data within the vector).
        !           299: The next cell contains a pointer to the property.
        !           300: Any remaining cells (if any) are for data.
        !           301: Vectors are handled differently from any other object in
        !           302: .Fr,
        !           303: in that a pointer to a vector is pointer to the first data
        !           304: cell, i.e. a pointer to the \fIthird\fP longword of the structure.
        !           305: This was done for efficiency in compiled code and for uniformity
        !           306: in referencing immediate-vectors (described below).
        !           307: The user should never return a pointer to any other part
        !           308: of a vector, as this may cause the garbage collector to follow an
        !           309: invalid pointer.
        !           310: .sh 2 "immediate-vectors"
        !           311: Immediate-vectors are similar to vectors.  They differ, in
        !           312: that binary data are stored in space directly within the vector.
        !           313: Thus the garbage collector will preserve the vector itself (if used),
        !           314: and will only traverse the property cell.
        !           315: The data may be referenced as longwords, shortwords, or even bytes.
        !           316: Shorts and bytes are returned sign-extended.
        !           317: The compiler open-codes such references,
        !           318: and will avoid boxing the resulting integer data, where possible.
        !           319: Thus, immediate vectors may be used for efficiently processing
        !           320: character data.
        !           321: They are also useful in storing results from functions written
        !           322: in other languages.
        !           323: .(b
        !           324: .TS
        !           325: box center ;
        !           326: c | c | c | c .
        !           327: Subpart name   Get value       Set value       Type
        !           328: 
        !           329: =
        !           330: datum[\fIi\fP] vrefi-byte      vseti-byte      fixnum
        !           331:        vrefi-word      vseti-word      fixnum
        !           332:        vrefi-long      vseti-long      fixnum
        !           333: _
        !           334: property       vprop   vsetprop        lispval
        !           335:                vputprop
        !           336: _
        !           337: size   vsize   \-      fixnum
        !           338:        vsize-byte              fixnum
        !           339:        vsize-word              fixnum
        !           340: .TE
        !           341: .)b
        !           342: To create immediate vectors specifying size and fill data,
        !           343: you can use the functions
        !           344: \fInew-vectori-byte\fP,
        !           345: \fInew-vectori-word\fP,
        !           346: or \fInew-vectori-long\fP.
        !           347: You can also use the functions
        !           348: \fIvectori-byte\fP,
        !           349: \fIvectori-word\fP,
        !           350: or \fIvectori-long\fP.
        !           351: All of these functions are described in
        !           352: chapter 2.

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.