![[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] / 42BSD / ucb / lisp / lisplib / manual|
Return to ch9.r CVS log | Up to [CSRG BSD Unix] / 42BSD / 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.