![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ch9.r CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / lisplib / manual|
Return to ch9.r CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / lisplib / manual |
1.1 root 1:
2:
3:
4:
5:
6:
7:
8: CHAPTER 9
9:
10:
11: Arrays and Vectors
12:
13:
14:
15:
16: Arrays and vectors are two means of expressing aggre-
17: gate data objects in FRANZ LISP. Vectors may be thought of
18: as sequences of data. They are intended as a vehicle for
19: user-defined data types. This use of vectors is still
20: experimental and subject to revision. As a simple data
21: structure, they are similar to hunks and strings. Vectors
22: are used to implement closures, and are useful to communi-
23: cate with foreign functions. Both of these topics were dis-
24: cussed in Chapter 8. Later in this chapter, we describe the
25: current implementation of vectors, and will advise the user
26: what is most likely to change.
27:
28: Arrays in FRANZ LISP provide a programmable data struc-
29: ture access mechanism. One possible use for FRANZ LISP
30: arrays is to implement Maclisp style arrays which are simple
31: vectors of fixnums, flonums or general lisp values. This is
32: described in more detail in 9.3 but first we will describe
33: how array references are handled by the lisp system.
34:
35: The structure of an array object is given in 1.3.10 and
36: reproduced here for your convenience.
37:
38:
39: 8_______________________________________________________________
40: Subpart name Get value Set value Type
41:
42: 8______________________________________________________________________________________________________________________________
43: access function getaccess putaccess binary, list
44: or symbol
45: 8_______________________________________________________________
46: auxiliary getaux putaux lispval
47: 8_______________________________________________________________
48: data arrayref replace block of contiguous
49: set lispval
50: 8_______________________________________________________________
51: length getlength putlength fixnum
52: 8_______________________________________________________________
53: delta getdelta putdelta fixnum
54: 8_______________________________________________________________
55: 7|7|7|7|7|7|7|7|7|7|7|7|
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66: |7|7|7|7|7|7|7|7|7|7|7|
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77: |7|7|7|7|7|7|7|7|7|7|7|
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88: |7|7|7|7|7|7|7|7|7|7|7|
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99: |7|7|7|7|7|7|7|7|7|7|7|
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115: 9.1. general arrays Suppose the evaluator is told to
116: evaluate (_f_o_o _a _b) and the function cell of the symbol
117: foo contains an array object (which we will call
118: foo_arr_obj). First the evaluator will evaluate and
119: stack the values of _a and _b. Next it will stack the
120:
121:
122: 9Arrays and Vectors 9-1
123:
124:
125:
126:
127:
128:
129:
130: Arrays and Vectors 9-2
131:
132:
133: array object foo_arr_obj. Finally it will call the
134: access function of foo_arr_obj. The access function
135: should be a lexpr[] or a symbol whose function cell
136: contains a lexpr. The access function is responsible
137: for locating and returning a value from the array.
138: The array access function is free to interpret the
139: arguments as it wishes. The Maclisp compatible array
140: access function which is provided in the standard
141: FRANZ LISP system interprets the arguments as sub-
142: scripts in the same way as languages like Fortran and
143: Pascal.
144:
145: The array access function will also be called
146: upon to store elements in the array. For example,
147: (_s_t_o_r_e (_f_o_o _a _b) _c) will automatically expand to (foo
148: c a b) and when the evaluator is called to evaluate
149: this, it will evaluate the arguments _c, _b and _a. Then
150: it will stack the array object (which is stored in the
151: function cell of foo) and call the array access func-
152: tion with (now) four arguments. The array access
153: function must be able to tell this is a store opera-
154: tion, which it can do by checking the number of argu-
155: ments it has been given (a lexpr can do this very
156: easily).
157:
158:
159:
160: 9.2. subparts of an array object An array is created
161: by allocating an array object with _m_a_r_r_a_y and filling
162: in the fields. Certain lisp functions interpret the
163: values of the subparts of the array object in special
164: ways as described in the following text. Placing
165: illegal values in these subparts may cause the lisp
166: system to fail.
167:
168:
169:
170: 9.2.1. access function The purpose of the access
171: function has been described above. The contents of
172: the access function should be a lexpr, either a
173: binary (compiled function) or a list (interpreted
174: function). It may also be a symbol whose function
175: cell contains a function definition. This subpart
176: is used by _e_v_a_l, _f_u_n_c_a_l_l, and _a_p_p_l_y when evaluating
177: array references.
178:
179:
180:
181: ____________________
182: 9 []A lexpr is a function which accepts any number of argu-
183: ments which are evaluated before the function is called.
184:
185:
186:
187: 9 Printed: July 21, 1983
188:
189:
190:
191:
192:
193:
194:
195: Arrays and Vectors 9-3
196:
197:
198: 9.2.2. auxiliary This can be used for any purpose.
199: If it is a list and the first element of that list
200: is the symbol unmarked_array then the data subpart
201: will not be marked by the garbage collector (this
202: is used in the Maclisp compatible array package and
203: has the potential for causing strange errors if
204: used incorrectly).
205:
206:
207:
208: 9.2.3. data This is either nil or points to a block
209: of data space allocated by _s_e_g_m_e_n_t or _s_m_a_l_l-
210: _s_e_g_m_e_n_t.
211:
212:
213:
214: 9.2.4. length This is a fixnum whose value is the
215: number of elements in the data block. This is used
216: by the garbage collector and by _a_r_r_a_y_r_e_f to deter-
217: mine if your index is in bounds.
218:
219:
220:
221: 9.2.5. delta This is a fixnum whose value is the
222: number of bytes in each element of the data block.
223: This will be four for an array of fixnums or value
224: cells, and eight for an array of flonums. This is
225: used by the garbage collector and _a_r_r_a_y_r_e_f as well.
226:
227:
228:
229: 9.3. The Maclisp compatible array package
230:
231: A Maclisp style array is similar to what is known
232: as arrays in other languages: a block of homogeneous
233: data elements which is indexed by one or more integers
234: called subscripts. The data elements can be all fix-
235: nums, flonums or general lisp objects. An array is
236: created by a call to the function _a_r_r_a_y or *_a_r_r_a_y.
237: The only difference is that *_a_r_r_a_y evaluates its argu-
238: ments. This call: (_a_r_r_a_y _f_o_o _t _3 _5) sets up an array
239: called foo of dimensions 3 by 5. The subscripts are
240: zero based. The first element is (_f_o_o _0 _0), the next
241: is (_f_o_o _0 _1) and so on up to (_f_o_o _2 _4). The t indi-
242: cates a general lisp object array which means each
243: element of foo can be any type. Each element can be
244: any type since all that is stored in the array is a
245: pointer to a lisp object, not the object itself.
246: _A_r_r_a_y does this by allocating an array object with
247: _m_a_r_r_a_y and then allocating a segment of 15 consecutive
248: value cells with _s_m_a_l_l-_s_e_g_m_e_n_t and storing a pointer
249: to that segment in the data subpart of the array
250: object. The length and delta subpart of the array
251:
252:
253: Printed: July 21, 1983
254:
255:
256:
257:
258:
259:
260:
261: Arrays and Vectors 9-4
262:
263:
264: object are filled in (with 15 and 4 respectively) and
265: the access function subpart is set to point to the
266: appropriate array access function. In this case
267: there is a special access function for two dimensional
268: value cell arrays called arrac-twoD, and this access
269: function is used. The auxiliary subpart is set to
270: (t 3 5) which describes the type of array and the
271: bounds of the subscripts. Finally this array object is
272: placed in the function cell of the symbol foo. Now
273: when (_f_o_o _1 _3) is evaluated, the array access function
274: is invoked with three arguments: 1, 3 and the array
275: object. From the auxiliary field of the array object
276: it gets a description of the particular array. It
277: then determines which element (_f_o_o _1 _3) refers to and
278: uses arrayref to extract that element. Since this is
279: an array of value cells, what arrayref returns is a
280: value cell whose value is what we want, so we evaluate
281: the value cell and return it as the value of
282: (_f_o_o _1 _3).
283:
284: In Maclisp the call (_a_r_r_a_y _f_o_o _f_i_x_n_u_m _2_5) returns
285: an array whose data object is a block of 25 memory
286: words. When fixnums are stored in this array, the
287: actual numbers are stored instead of pointers to the
288: numbers as is done in general lisp object arrays.
289: This is efficient under Maclisp but inefficient in
290: FRANZ LISP since every time a value was referenced
291: from an array it had to be copied and a pointer to the
292: copy returned to prevent aliasing[]. Thus t, fixnum
293: and flonum arrays are all implemented in the same
294: manner. This should not affect the compatibility of
295: Maclisp and FRANZ LISP. If there is an application
296: where a block of fixnums or flonums is required, then
297: the exact same effect of fixnum and flonum arrays in
298: Maclisp can be achieved by using fixnum-block and
299: flonum-block arrays. Such arrays are required if you
300: want to pass a large number of arguments to a Fortran
301: or C coded function and then get answers back.
302:
303: The Maclisp compatible array package is just one
304: example of how a general array scheme can be imple-
305: mented. Another type of array you could implement
306: would be hashed arrays. The subscript could be
307: ____________________
308: 9 []Aliasing is when two variables are share the same
309: storage location. For example if the copying mentioned
310: weren't done then after (_s_e_t_q _x (_f_o_o _2)) was done, the value
311: of x and (foo 2) would share the same location. Then should
312: the value of (foo 2) change, x's value would change as well.
313: This is considered dangerous and as a result pointers are
314: never returned into the data space of arrays.
315:
316:
317:
318: 9 Printed: July 21, 1983
319:
320:
321:
322:
323:
324:
325:
326: Arrays and Vectors 9-5
327:
328:
329: anything, not just a number. The access function
330: would hash the subscript and use the result to select
331: an array element. With the generality of arrays also
332: comes extra cost; if you just want a simple aggregate
333: of (less than 128) general lisp objects you would be
334: wise to look into using hunks.
335:
336:
337:
338: 9.4. vectors Vectors were invented to fix two
339: shortcommings with hunks. They can be longer than 128
340: elements. They also have a tag associated with them,
341: which is intended to say, for example, "Think of me as
342: an _B_l_o_b_i_t." Thus a vector is an arbitrary sized hunk
343: with a property list.
344:
345: Continuing the example, the lisp kernel may not
346: know how to print out or evaluate _b_l_o_b_i_t_s, but this is
347: information which will be common to all _b_l_o_b_i_t_s. On
348: the other hand, for each individual blobits there are
349: particulars which are likely to change, (height,
350: weight, eye-color). This is the part that would pre-
351: viously have been stored in the individual entries in
352: the hunk, and are stored in the data slots of the vec-
353: tor. Once again we summarize the structure of a vec-
354: tor in tabular form:
355:
356:
357: 8 ________________________________________________
358: Subpart name Get value Set value Type
359:
360: 8 ________________________________________________________________________________________________
361: datum[_i] vref vset lispval
362: 8 ________________________________________________
363: property vprop vsetprop lispval
364: vputprop
365: 8 ________________________________________________
366: size vsize - fixnum
367: 8 ________________________________________________
368: 7 |7|7|7|7|7|7|7|
369:
370:
371:
372:
373:
374:
375: |7|7|7|7|7|7|7|
376:
377:
378:
379:
380:
381:
382: |7|7|7|7|7|7|7|
383:
384:
385:
386:
387:
388:
389: |7|7|7|7|7|7|7|
390:
391:
392:
393:
394:
395:
396: |7|7|7|7|7|7|7|
397:
398:
399:
400:
401:
402:
403:
404:
405: Vectors are created specifying size and optional fill
406: value using the function (_n_e_w-_v_e_c_t_o_r 'x_size ['g_fill
407: ['g_prop]]), or by initial values: (_v_e_c_t_o_r ['g_val
408: ...]).
409:
410:
411:
412: 9.5. anatomy of vectors There are some technical
413: details about vectors, that the user should know:
414:
415:
416:
417:
418:
419:
420:
421:
422: 9 Printed: July 21, 1983
423:
424:
425:
426:
427:
428:
429:
430: Arrays and Vectors 9-6
431:
432:
433: 9.5.1. size The user is not free to alter this. It
434: is noted when the vector is created, and is used by
435: the garbage collector. The garbage collector will
436: coallesce two free vectors, which are neighbors in
437: the heap. Internally, this is kept as the number
438: of bytes of data. Thus, a vector created by (_v_e_c_-
439: _t_o_r 'foo), has a size of 4.
440:
441:
442:
443: 9.5.2. property Currently, we expect the property
444: to be either a symbol, or a list whose first entry
445: is a symbol. The symbols fclosure and structure-
446: value-argument are magic, and their effect is
447: described in Chapter 8. If the property is a
448: (non-null) symbol, the vector will be printed out
449: as <symbol>[<size>]. Another case is if the pro-
450: perty is actually a (disembodied) property-list,
451: which contains a value for the indicator print.
452: The value is taken to be a Lisp function, which the
453: printer will invoke with two arguments: the vector
454: and the current output port. Otherwise, the vector
455: will be printed as vector[<size>]. We have vague
456: (as yet unimplemented) ideas about similar mechan-
457: isms for evaluation properties. Users are cau-
458: tioned against putting anything other than nil in
459: the property entry of a vector.
460:
461:
462:
463: 9.5.3. internal order In memory, vectors start with
464: a longword containing the size (which is immediate
465: data within the vector). The next cell contains a
466: pointer to the property. Any remaining cells (if
467: any) are for data. Vectors are handled differently
468: from any other object in FRANZ LISP, in that a
469: pointer to a vector is pointer to the first data
470: cell, i.e. a pointer to the _t_h_i_r_d longword of the
471: structure. This was done for efficiency in com-
472: piled code and for uniformity in referencing
473: immediate-vectors (described below). The user
474: should never return a pointer to any other part of
475: a vector, as this may cause the garbage collector
476: to follow an invalid pointer.
477:
478:
479:
480: 9.6. immediate-vectors Immediate-vectors are similar
481: to vectors. They differ, in that binary data are
482: stored in space directly within the vector. Thus the
483: garbage collector will preserve the vector itself (if
484: used), and will only traverse the property cell. The
485: data may be referenced as longwords, shortwords, or
486:
487:
488: Printed: July 21, 1983
489:
490:
491:
492:
493:
494:
495:
496: Arrays and Vectors 9-7
497:
498:
499: even bytes. Shorts and bytes are returned sign-
500: extended. The compiler open-codes such references,
501: and will avoid boxing the resulting integer data,
502: where possible. Thus, immediate vectors may be used
503: for efficiently processing character data. They are
504: also useful in storing results from functions written
505: in other languages.
506:
507:
508: 8 __________________________________________________
509: Subpart name Get value Set value Type
510:
511: 8 ____________________________________________________________________________________________________
512: datum[_i] vrefi-byte vseti-byte fixnum
513: vrefi-word vseti-word fixnum
514: vrefi-long vseti-long fixnum
515: 8 __________________________________________________
516: property vprop vsetprop lispval
517: vputprop
518: 8 __________________________________________________
519: size vsize - fixnum
520: vsize-byte fixnum
521: vsize-word fixnum
522: 8 __________________________________________________
523: 7 |7|7|7|7|7|7|7|7|7|7|7|
524:
525:
526:
527:
528:
529:
530:
531:
532:
533:
534: |7|7|7|7|7|7|7|7|7|7|7|
535:
536:
537:
538:
539:
540:
541:
542:
543:
544:
545: |7|7|7|7|7|7|7|7|7|7|7|
546:
547:
548:
549:
550:
551:
552:
553:
554:
555:
556: |7|7|7|7|7|7|7|7|7|7|7|
557:
558:
559:
560:
561:
562:
563:
564:
565:
566:
567: |7|7|7|7|7|7|7|7|7|7|7|
568:
569:
570:
571:
572:
573:
574:
575:
576:
577:
578:
579:
580: To create immediate vectors specifying size and fill
581: data, you can use the functions _n_e_w-_v_e_c_t_o_r_i-_b_y_t_e,
582: _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
583: 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
584: _v_e_c_t_o_r_i-_l_o_n_g. All of these functions are described in
585: chapter 2.
586:
587:
588:
589:
590:
591:
592:
593:
594:
595:
596:
597:
598:
599:
600:
601:
602:
603:
604:
605:
606:
607:
608:
609:
610:
611:
612: 9 Printed: July 21, 1983
613:
614:
615:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.