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