Implementor's notes for CommonLisp style arrays in InterLisp File: {eris}array>cmlarray.notes Created: 20-Jun-85 Author: Ron Fischer, AIS Arrays are actually an array record which points at a storage block, possibly with a linear index offset. Arrays can be displaced to other arrays. This is done by cacheing the displaced-to array's storage pointer in the displaced array's header record. These are kept up to date using a chain of displacee's in each header record. Every array always knows who displaces to him, and thus can update them if he's adjusted. The updating information is not kept if the array is not adjustable. [Major change: functions and keywords are named as in Commonlisp, ie with dashes in their names] adjust-array never moves storage around in an array to preserve element order. The order is always dereived from the linear order of elements referenced in row-major fashion. When shrinking or enlarging an existing array adjust-array copies the old one into a new storage block, changes the dimensions field in the header and and updates the encached information in arrays displaced to it. No copying occurs if the adjusted dimensions have the same linear size as the old ones. Only the dimensions information in the header is updated. In addition, if displaced-to is specified, no new storage is allocated (in fact the old storage block is lost). Note that if not explicitily "re" displaced, a displaced array is always copied when adjusted, losing its displaced status if it had any! A general comment: an interesting implication of displacement and adjustablility is that there is no way to easily tell whether the storage associated with an array is of an adequete size without using either hidden pointers or an update chain. In the case where an array A is displaced-to B, and B is shrunk using adjust-array, unless B "knows" all the arrays that displace to it they can't be checked. This tends to a final implication that without either of the above mechanisms AREF must check indices against dimensions and linear address offset against linear size of final displaced-to storage block ( which could be several displacements away). An outline for an implementation of CommonLisp type arrays in InterLisp follows, taking into account the need for speedy referencing, proper handling of displacement to adjustable arrays, etc. Array types: Primitive element types: bit byte word fixnum float pointer xpointer Metatypes for elements: flag-bit Index origin types: origin 0 origin 1 Index linearization types: 1 dimensional 2 dimensional n-dimensional Displacement types: displaced-to-adequete-size - adequete for the dimensions given displaced-to-smaller - delays the inevitable when the displaced-to array has shrunk [Implementation: displaced-to-smaller is not be necessary by CommonLisp standards, and thus these two additional types could collapse into one normal case.] Array headers: These contain: adjustable.p - "Can it be altered after creation?" flag element.type - common lisp style element type designator rank - number of dimensions dimensions.list - list of dimensions, used to linearize references displaced.to - base data block array is indirected to. updated at adjust with displacee-list displaced.index.offset - linear address it begins accesses at. Sum of index offset chain. fill.pointer - for variable length simple vectors (uh hum), only used by elt. Plus some info for optimizing: total.size - used by simple vector accessors displacee.start - beginning of chain of array headers that displace to this one. displacee.next - next one in the chain. displaced.to.adjustable - flag for the compiler. [Implementation: is displaced.to.adjustable useful?] make-array An array can have any of the properties listed above under Array types. In addition it can have a fill pointer, which is only paid attention by ELT. Only one of: initial-element, initial-contents, or displaced-to may be given. If displaced-to is given the storage block of the array being displaced into is copied into our header, and the displaced-index-offset is added to that of the displaced into array's own offset and encached as well. We add ourselves to the displacee-start chain only if the array displaced into is adjustable. Local extensions include the origin keyword arg, which may be 0 or 1, the xpointer and doublepointer types, and the displaced-to-base, page-align and alignment keyword arguments. displaced-to-base is makes the generated array header point at any block of storage. Type is assumed to be as per element-type's specification (its default value is T, for pointer). page-align and alignment are passed directly to the storage allocation function \ALLOCBLOCK as 3rd and 4th arguments. make-array will normalize element types up to the next enclosing primitive type as listed above. [Change: The margins option has been removed] adjust-array New dimensions must have the same rank as the array being adjusted. There are four types of adjustment based on what is done to the array's storage: same size storage different size storage remove displacement (was displaced, none specified so it loses old displacement) new displacement Any of the latter three operations must use the displacee.start chain in the array header to update arrays that point into this one. This has to be done because the latter three cases alter the base address of the storage block, whose cache must be updated in any displacee arrays. It is unclear when we should signal an error if we shrink an array that another array (with a larger linear size) displaces to. Currently we don't. References beyond the end of the array will be caught by the accessor and settor functions. aref Ignores fill pointers. Dispatches to an accessor function based on the type of the array's elements. There are several types of access: simple displaced to simple multi-dimensional to simple multi-dimensional to adjustable displaced multi-dimensional to non-adjustable displaced Compiled accesses should know if the array is adjustable or displaced to adjustable, in which case we probably have to use all the runtime dispatches, otherwise the cases are: simple displaced to simple multi-dimensional to simple aset [Note: this is not a Commonlisp function. It is provided until a suitable SETF module is implemented] [Unfinished: Say something about compatibility functions for the old array stuff?] ) )$$ )  HELVETICA HELVETICA € HELVETICA HELVETICA  HELVETICA ?1(DEFAULTFONT 1 (GACHA 10) (GACHA 8) (TERMINAL 8))  HELVETICA =+Óa Ó B µ*5 =Á    $@x , -4 RF B #5   : ^  aj7'   b 9  :  W  –Q0ÜòN#*.±gSM/zº