|
Empty Frames in SHARP APL Introduction APL functions apply to arrays of data. Recent systematization of the rules for their application has extended (at least in principle) to many more functions some of the properties previously enjoyed only by the “scalar” (rank 0) functions. Explicit use of the rank operator, or implicit use of rank by primitives or derived functions, allows much more flexibility than heretofore for combining parts of different arrays in a simple fashion. However, these facilities have given rise to a new class of problem in the design of the language. The functions traditionally called “scalar” not only applied to scalar arguments, but also produced scalar results. This allowed language designers to solve the question of result shape trivially: the shape of the result of a scalar function is the shape of one or both of its arguments. In particular, this rule applies equally well to empty arrays, even though there are actually no scalars in them. The generalization provided by rank requires more thought on this question, and in general the result shape is quite satisfactorily specified by a rule such as that given in [1]:
Unfortunately, such rules fail in some cases, known as the “empty frame” cases: whenever the frame contains at least one zero, there are no cells. For example, the expression ,⍤2 (n,4 5)⍴⎕av ravels each of n (the frame) cells, having a cell shape of 4 5. This produces a result of shape n,20 — unless n is 0, the “empty frame” case. Since the frame is 0, there are no cells. Yet any APL programmer expects the general rule — results of shape n,20 — to hold for this case too, giving an array of shape 0 20. The initial — and still in effect (release 17) — definition of rank on SHARP APL took a straightforward approach to this problem: if there were no cells, there was no contribution to the result shape from the cells. This is the simplest extrapolation from the traditional treatment of scalar functions; but for scalar functions, not only is the result cell shape empty, so was the argument cell shape, and so are expected results in the corresponding non-empty cases. Therefore this method works well for the scalar functions, but anomalies quickly became apparent for other functions. For example, for the case cited above, the result of ,⍤2 (n,4 5)⍴⎕av in SHARP APL through the release 17 level has shape 0 rather than the expected 0 20. Anomalies of this sort have repeatedly been reported as bugs by APL programmers in the field, both at IPSA and at customer sites. Some method is clearly required of calculating a cell
shape for the “empty frame” cases, to produce a
result which fits the pattern of result shapes for
each function applied to otherwise similar arrays
with non-empty frames.
Recapitulation: earlier attempts at solutions Prototypes. Because “prototypes”, as defined by Trenchard More [2] or as implemented in IBM’s APL2 [3], were intended to smooth over perceived anomalies involving emptiness, it is often expected that they would provide a solution to this problem. They do not, for several reasons. First, the usefulness of prototypes is greatest in systems of APL extensions that depend heavily on enclosure for definition of other facilities, since prototypes reduce to the familiar 0 or blank fill where enclosure is not involved. SHARP APL extensions are largely not defined in terms of enclosure. Second, prototypes do not solve this particular problem in any case. For example, in the APL2 IUP, while there wasn’t a rank operator, similar effects could be obtained with other facilities — for example, the expression 2↑⍤0 ⍳n in (which should give results of shape n,2, and runs into the empty frame case for n=0) cannot be written with APL2 primitive facilities, but the same effect can be obtained from their expression ⊃2↑¨⍳n. In the IUP, no special thought had been given to empty frames, and this expression — like ours — gave the wrong result for n=0, regardless of the presence of prototypes (though prototype use did mean that the APL2 IUP got a different wrong answer from SHARP APL in that case). In the APL2 program product, this has been corrected through the use of a technique involving “fill functions” [3], two for each primitive, for this purpose — a technique almost identical to that proposed in [4], which is discussed below. Shape Expressions. An early method discussed
internally in IPSA for addressing this problem was
called “shape expressions”. A “shape expression”
would be associated with each function, as one of
its independent parts such as the rank or the
inverse. This executable expression would
describe, on the basis of argument-cell shape, the
shape of a result of the function; since in
empty-frame cases the cell shape is known, even
though there are no cells, this method seemed
promising. Indeed, it would work for a class of
functions that can be called “uniform” functions —
those whose result shapes depend exclusively on
the argument shapes. For example, the result of ,⍵
is known to be of shape ×/⍴⍵ regardless of the
value of ⍵, so this approach would be able to
produce the proper 0 20 shape for the first
example in this note. However, shape expressions
fail in general: for example, in the
expression 2↑⍤0 ⍳n
mentioned above, the result shape
depends not only on the shape of the right
argument, but also on the value (2) of the left
argument.
Surrogate arguments This led to a search for alternative solutions. All other proposals to date can be characterized as “surrogate argument” proposals, and they all have one feature in common: for the empty-frame cases, when there is no data (no argument cells) to apply a function to, a surrogate cell is invented and passed to the appropriate function. Note in particular that all surrogate-argument proposals share the characteristic that, in the expression f⍤n ⍵, the function f executes at least once, regardless of whether ⍵ has any cells to apply to. The differences between “surrogate argument” proposals lie in the method used to invent the surrogate argument cell. An Operator Calculus. The proposal in [4] to address this issue is similar to the earlier “shape expressions” approach in that it depends on a function part. In this case, the new function part, rather than describing the shape of the result directly, specifies separately for each case (monadic argument, left argument, right argument) of each function an algorithm to create the surrogate argument, on the basis of cell shape and argument value. A general rule is given to describe how the surrogate part was chosen for each primitive (to give the smallest possible result shape) but this rule cannot be applied automatically. The particular strength of this proposal is that it applies to all primitive functions. The weakness of this proposal is that it does not apply in any obvious way to derived functions, save those derived from the rank operator with primitive arguments. The paper does not discuss the general derived-function case with regard to this issue, but its approach suggests that there might be two alternatives: either derived functions “inherit” this function part from one of the arguments of an operator, or else derived functions lack this part, and therefore do not include empty-frame cases in their domains. The latter is clearly unacceptable, as it creates an even stronger discontinuity than the problem we wish to address. The former does not work with the primitive parts suggested in the paper; for example, a surrogate part for monadic f⍤g cannot be derived from g, because then ÷⍤+ would fail (on domain error) for empty frames; conversely, it cannot be derived from f for the parallel reason. Specific surrogate parts could certainly be invented for specific derived functions, but this procedure has obvious limits. Overtake. An alternative approach was implemented in [5], and consists in using an existing part of data (the type or fill) rather than a new part of functions, to define the surrogates: surrogate cells are, here, created via overtake of the empty-frame array. This approach has the advantages of providing a simple alternative rule, of applying to derived (or defined) functions equally well as to primitive functions, and of achieving all this without a need for a new part of functions (or data, for that matter). Unfortunately, it has one serious drawback: it doesn’t apply to all primitives (or to all derived functions), since the fill of an arbitrary array is not necessarily in the domain of an arbitrary function. For example, if applied rigorously, this method requires that ÷⍳0 fail with a domain error rather than returning the empty result we are accustomed to. Comparison, evaluation, extension. The second
approach to surrogate arguments is superior in
terms of consistency and simplicity. It is therefore
preferable. Unfortunately, its limitations also make
it unacceptable. However, extensions on the basis
of the notion of nil
(the term and its description as
used here are from
[1];
similar ideas may also be
found in sources listed as
[6])
can make it apply in
general. This set of extensions is the subject of the
remainder of this note.
Nil use with surrogate arguments Nil. A nil is a scalar value, whose type is different from that of all other APL data. It is used to extend the domains of APL primitives in the following way: whenever a primitive encounters an argument cell outside of its normal domain, the corresponding result cell is made up of nils. Since the drawback of the overtake approach to generating surrogates was a greater incidence of domain errors, the application of nils to the problem is straightforward. No nils in results. An interesting characteristic of the empty-frames problem with regard to nil is that these extensions need only be based on nil in their specification and design. Since all acceptable results in empty-frame situations are empty, no nils ever actually appear in a result, even if those results are defined in terms of nils. Thus the implementation of these extensions does not require an APL with a representation for nil. How nils are used. There are two conceivable ways of using nil to derive cell-shape information with surrogate arguments. First, the overtake solution could be applied, but where the resulting surrogate fell outside the domain of a function, nils could then be produced, preserving the required shape information. Second, the surrogate-argument cell could itself be made up of nils in the first place. The second may seem less straightforward, but it preferable for the following reasons:
The rule for generating surrogate argument cells is therefore to use, in all circumstances, an array of the required shape, made up completely of nils. Required domain extensions. For many cases, such as functions derived completely from the old familiar scalar functions, or monadic structural functions, or right arguments of structural functions, the foregoing is sufficient to produce the desired uniformity of result shapes. The scalar functions return scalar nils for any argument (including nil itself) outside their domains. Inclusion of the structural functions in this category is extension in a sense, since they did not previously apply to nils; but they are to apply to nils in the same way that they apply to all other arrays, and in that sense are not considered explicit extensions. The functions covered by this sort of systematic extension are monadic , ⊃ ⊢ ⍴ ⍉ ⌽ ⊖ < > and dyadic ⍳ ⍒ ⍋ , ⊃ ⊢ ⊣ ∊ ≡. The right arguments of dyadic ⍴ ↑ ↓ ⍉ ⌽ ⊖ are also covered by this sort of systematic extension, though the left arguments will require explicit treatment of nil cells. The right argument of an indexing function { would also fall in this class if we had an indexing function. Some more difficult cases, however, require explicit extension of some primitive function kernels to nil arrays, in order to produce nil results of the right shapes. Since nil arrays are always used for surrogates, and since the extensions are to the function kernel, we can be assured that no further extensions will be required for derived functions: the primitive kernels in derived functions will have the information they require to handle these cases. The primitive functions requiring special extension of their domains to nil arrays are system functions, ⌶, and the following:
Cases that treat nil as 0: Many of these can simply treat nil identically with their treatment of 0, in particular all the left-argument cases (for ⍉, origin 0 is assumed in this definition). Monadic ⍳ and dyadic ⍕ are also covered in this treatment. The remainder require special definitions:
Fill or type. Due to the traditional APL provision of
fill for empty arrays, to guarantee that no nils will
become visible due to the use of nil for surrogate
arguments requires that the fill — or type, if that
formulation should be preferable — for results be
defined in such a way that nil is never produced by
a subsequent overtake or expansion. This can be
achieved bv any definition of the APL primitives
that specifies result fill (or result type)
as one of the properties of the kernel of a function.
It is important that fill be an effect of the kernel, not an
independent part of functions, to guarantee that
the question does not immediately recur at some
derived-function level. A set of definitions for
primitive result fill is given in
[7],
and is compatible with this note provided that treatment of
rank is defined so that splitting an array into cells
gives each cell the fill of the original array. In
particular, fill in surrogates is defined (using the
notation of that note) so that a surrogate argument
cell w is generated
from an empty-frame argument ⍵)
as w←(∪⍵)∪(f↓⍴⍵)⍴nil,
where f covers the frame of ⍵.
(In words, this means that the fill of the
surrogate cell, like that of any other cell,
is the fill of the original argument). The equivalent
formulation in terms of type is probably more
complicated, and may require three nils; one of
each type, numeric, character, or boxed.
Conclusion Using cells made up entirely of nils for surrogate arguments combines the advantages of the two earlier surrogate argument proposals; like that of [4], it applies equally well to all primitive functions, but because, like that of [5], it requires no separate function part to support it, it also applies equally well to all derived functions. This simplifies the operator calculus. Moreover, the solution is in principle also extensible to the application of rank to user-defined functions, without requiring (as “fill functions” or independent function parts would) special provisions in function representation. In practice, this extension does depend on several other extensions, but these extensions can at least be argued for on their own merits: heterogeneous arrays, application of operators to defined functions, and creation of an environment in which nil can be a result accessible to users, are immediately apparent. However, this solution is also immediately useful,
since for the primitive and derived-function cases
these extensions are only necessary for the
definition, being required neither for user-visible
results nor, therefore, for implementation.
References
Originally appeared in the APL86 Conference Proceedings, APL Quote Quad, Volume 16, Number 4, 1986-07.
|