[qv]<IDL>History>DesignMemos.dm!1>Design.Arrays

The nature of assignment is the major area of consistent differences in user visible semantics. In LISP, expressions evaluate to their value, rather than the location in which that value is stored (in the event that such a location exists). Thus, there is a proliferation of special assignment forms (SETQ, RPLACA etc.) the sole justification of each of which is to take a left hand argument which contains the location to be side effected and dereference it, rather than taking the location itself (which would be evaluated to its contents before the assignment could take place). Thus, we have (RPLACA X Y) rather than (CAR X)←Y. As the IDL PPL semantics are defined to allow the left hand side (hereafter lhs) of an assignment to be an expression (e.g. (IF mumble THEN A ELSE B) ← 7), this is a basic inconsistency between the two environments. We do not have a principled solution to this problem, and it will remain a research topic. Currently, we define IDL.ASSIGN to be an NLAMBDA as follows:
Evaluate both arguments.
If the lhs is a selection on an array, sideeffect the selected sections.
Otherwise, if the lhs form is an atom, rebind it, else error.
Extensions to this semantics (e.g. to interpret a larger class of lhs expressions) may be made at a later date.

Despite this upheaval, we will continue to use copy semantics for assignment. This may seem surprising as that aspect of IDL-PPL might appear a reflection of the assignment semantics of PPL, and therefore a decision to be changed in the LISP environment which has a sharing default for assignment. However, copying semantics is necessary in order to have a consistent meaning for assignment across rebinding and substructure modification. If one is assigning into a typed substructure of an aggregate, sharing assignment is tricky, as the right hand side (hereafter rhs) of the assignment must be defined to share the value of the lhs. As both may be referenced by many other objects, the implementation requires indirects (e.g. pointers or hash links) to the cells in which the actual values are stored (pointers are the solution used for ordinary variable bindings). As this is unacceptably inefficient for large aggregates of uniformly typed, frequently accessed values (such as IDL arrays), we have decided on a systematic copy semantics. Consequently, there are two types of assignment. The first is IDL.ASSIGN (written ←) which can both rebind atoms and handle assignments into structure (e.g. A[1->6] ← [2 4 6 8 0 1]), and which copies, and regular LISP assignment (e.g. SETQ, LAMBDA bindings, RPLACA etc.) which makes a sharing pointer as usual (it is very difficult to make it do anything else!). Consequently, the user can make a variable either share or have a private copy of an array value. This implies that the user can get a "window" onto an array which he can pass around (using LISP bindings) and eventually store through (i.e. which shares storage with the array from which it was generated) until it eventually is copied by an IDL assignment and the sharing is broken.

We continue to use copy semantics for selectors. That is, a selection appears to copy its selector arguments, so that in
B←A[X Y]
X[5]←8
B does not change its value across the assignment to X (i.e. X is thought of as being copied at the time of the selection). However, as the selection may appear on the lhs of an assignment (in which case the changes are supposed to appear in A, rather than in some pure value produced by the selection), A is shared until the selection is copied by IDL.ASSIGN (or COPY, of course).

Although the user visible semantics present a very clean, principled view of the world, their straightforward implementation would be so inefficient that the user would soon begin using clumsy, but more efficient, expressions in their place. Consequently, we must make sure that the basic operations are known to be efficiently implemented. Therefore, in at least two places (copying on assignment and the evaluation of large aggregate producing expressions), we substitute different underlying representations in the interests of efficiency.

In the case of assignment, this alternative implementation is simply to share as long as possible and break the sharing relations only when someone tries to side effect a copy of something that is being shared in reality, although not from the user’s point of view. Thus, assignments (even of the copy kind) are in practice very economical of both time and space until some change is made to one of the copies.

In the case of the evaluation of operations which produce large arrays, we observe that the results of many of these do not need to be elementwise simultaneously available. All that is required is that their elements be available to the caller in some systematic order. Thus, if the function producing the array can produce its results one at a time in that order there is no need to actually build the array at all! This facility is obtained by treating some functions as generators of their results, rather than strict evaluators. Such functions are those that, in addition to being able to generate their elements sequentially, are able to do so saving a minimum of state from one element to the next, and frequently produce large objects. The two major candidates at the moments are RESHAPE (when called to produce a vector), and the MAP function (used to apply functions to aggregates of greater dimensionality than they expect e.g. A+B for array A and B). As we get more experience, we will also try out optimizing generator trees so that a minimum of intermediate computation is carried out for each element of the result. Not at first though.

The fundamental object in the system is the IDL array. Arrays come in three basic flavors: simple arrays; selections; and generators. (An additional complication is that simple arrays can be resident on files as well as in memory. We will not deal with these initially.) Simple arrays hold the data elements and labels and are the basis for all the more complex structures. Selections are arrays which are described in terms of some selection of data cells and/or labels of some other array (the virtual arrays of IDL PPL). Generators are arrays described in terms of the application of some function to other array descriptions.

These are sufficient for a simple array. Selections have an additional fields giving the selectors (the TTAB field of IDL PPL) and the base array from which the selection is to be made (i.e. a pointer to another frame). We must distinguish here between selections which are sharing their base array (so that they may be used to side effect it) and those that are sharing to economize use of storage. This is done by having a sharing selection point to the base array’s frame (with no adjustments of any reference counts), and a "copied" selection point to a copy of that frame which shares, having incremented the appropriate reference counts, the blocks of the original array. The incrementing of the reference counts (done by IDL.ASSIGN, which is the only function that causes a sharing selector to become an independent array) causes side effects to produce copies of the affected blocks, leaving the base array of the original selection unchanged. [Note also that some "copy" selections may be made by actually copying the appropriate elements of the base into a new array. This decision should be made on the basis of the relative sizes of the new array and the indirection blocks.] Generators have additional fields which are described below.

The Element Block: This consists of a LISP array containing the actual elements and several other fields of information. The actual numbers are stored unboxed as a contiguous block within this structure (i.e. there are no element by element indirects). The mapping from subscripts to linear offsets is the same as used in IDL PPL - i.e. row-major allocation, modulo the format code. The other fields contain at least

The requirement for reference counts arises from the need, when side effecting a block that is shared between many user objects each of whom allegedly has a private copy, to sort out which object the user intended to side effect. This is handled by changing the frame given in the side effecting expression to refer to the copy of the object (possibly made for the occasion, e.g. if others were (surreptitiously) sharing it) which we have updated. All bindings to this frame, including any created by SETQ, LAMBDA bindings, or anything else, will now see the altered block, while the others with which it was covertly sharing will remain untouched. Consequently, no reference counted block is ever given to the user except as a component of a frame, and no frame is ever altered except to update it to point to a copy that has been made of a block that it has been (covertly) sharing (e.g. to permit a side effect on this object, or as a result of an in-place evaluation of a generator). An implementation consequence of this is that the frame itself should be as small an object as possible, as every array producing function must allocate a new one, even if the elements themselves are shared.

Reference counts are updated in the following ways. If a new array frame is allocated and takes a pointer to a block, and passes that array outside its scope (i.e. potentially back to the user), then the reference counts of the referenced blocks are incremented. (Note that array frames whose use is confined to within a system function (see below) may take pointers to blocks without updating their reference counts. This is only permissible because such internal arrays are never side effected.) If an array which shares a block with count greater than one is forced to copy the block (e.g. to side effect it - i.e. the function in question is IDL.ASSIGN) then the reference count of the original block is decremented. Clearly, this count is very conservative, as array frames will sometimes be garbage collected while their memory lives on in the (too high) count. At some later date, the garbage collector may help by decrementing counts when it collects frames. At the moment, however, we will just be conservative. Note, however, that the copy still only takes place on an attempt to write.

Generators function as follows: A function that evaluates to a generator copies its arguments, its setup function, and its modes into the generator frame and returns (at some point it may also do some optimization of the generator tree). It will be awakened by one of two things happening to it. It will either be hit with a hard subscript (i.e. an attempt to access it at random) or will be given to a call on SETUP. In either case, if it is capable of responding to that type of access it will produce a generator state block (which will indicate (roughly) the state of the enumeration) containing a function which can compute the next element in response to a call of NEXT or a hard subscript, an indication as to whether the enumeration is complete (to be tested by the function DONE?), and the appropriate state information (a subblock whose format is completely determined by the next-element function). It is this block which is pumped by the user of the generator. If the generator cannnot honor the access mode specified by SETUP, then the array must be evaluated in temporary storage (this should rewrite the frame in place). Note that this can be done by a general routine which just streams the generator in the way it demanded!

This not only avoids the overhead of having some other function unpack a user supplied generator but allows the statement of the algorithm to be independent of the details of accessing the elements of the array. This is important both for reasons of modularity and because it is possible for the system to assemble a very fast generator (possibly even to the extent of compiling it open, if the appropriate information is given declaratively) for enumeration of a simple array. In order to do this, SETUP must be defined to produce a dummy generator in the case that it is called on a non-generator array frame (SETUP must have something like this capacity anyway, as it must be able to build a real array corresponding to a generator and a setup request of incompatible modes). Some amount of work should be done to have SETUP produce very fast accessing functions for the commmon cases (e.g. row major or don’t care access for simple arrays).

The other important technique is the use of virtual arrays (selections) to delimit an area of an array for use by a system function. Such internal selections can be built very quickly by the system functions that underlie user selection (without even adjusting the reference counts, if they are sure that you won’t pass the resultant frame out to the user) and provide a very flexible and powerful tool for windowing an array. For example, in PRETTY PRINT, which carves the array to be printed into two dimensional slices, and then into pieces determined by the physical size of the page before putting out their elements, there is no need to do that decomposition by subscript manipulation (as is done by IDL PPL). Instead, a selection of the right size and orientation for each slice that is to be put on consecutive areas of paper can be laid on the array, and then pumped in row major order until dry. This technique is capable of major reductions in the complexity of the code in many parts of the system.