![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ch9.n CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / lisp / doc|
Return to ch9.n CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / lisp / doc |
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.