﻿ Empty Frames in SHARP APL

Empty Frames in SHARP APL

Roland H. Pesch

APL Development Group
I.P. Sharp Associates
Palo Alto, California  94306
USA

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]:

 the shape of a result is the frame of the argument (relative to the cells to which the verb applies) catenated with the shape produced by applying the verb to the individual cells.

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 whetherhas 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:

 a. Most importantly, more information is available when nils are used in the first place. An array of 0’s or blanks, which would be the surrogate for most cases under the first alternative, provides a function with no clue as to its origins; on the other hand an array of nils clearly indicates an exceptional situation. For most primitive functions, this information should be unnecessary; but for some, such as ⌹ (discussed further under Required domain extensions) it is the only way to preserve uniform behavior short of very far-reaching extensions. b. In addition, in a sense the second approach — though less familiar — is even more straightforward than the first: all surrogate arguments are made up of the same item.

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:

 Monadics: ⍳ ⍋ ⍒ ⌹ ⍎ ⍕. Dyadics: ? ⌹ ⍕ ⊥ ⊤ for both arguments; for left argument only, ⍴ ↑ ↓ ⍉ ⌽ ⊖, and { (indexing) if we had it.

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). Monadicand 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

 [1] K.E. Iverson, A Dictionary of the APL Language, I.P. Sharp Associates, DRAFT - 5, September 85. [2] A starting point for the interested reader to explore T. More’s prolific work on “array theory” might be his paper “The Nested Rectangular Array as a Model of Data”, APL79 Conference Proceedings (APL Quote Quad Vol. 9 No. 4, June 1979), part 1, p. 55, and its rich set of references to earlier papers by the same author. [3] J.A. Brown, The Principles of APL2 (IBM Santa Teresa Technical Report TR 03.247, March 1984) [4] K.E. Iverson, R.H. Pesch, and J.H. Schueler, “An Operator Calculus”, Conference Proceedings APL84 (APL Quote Quad Vol. 14 No. 4, June 1984). p. 213 [5] Arthur T. Whitney, Robert D. Hodgkinson, and Laurie J. Gellatly, SAPL/HP interpreter (Sidney, Australia, 1985) [6] T. More’s work (see [2]) includes a similar concept called “fault”. The notion of “bottom” in Backus’ work on functional programming is also similar. See J. Backus, “Can Programming Be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs”, Communication of the ACM Vol. 21, no. 8, August 1978, p. 613 [7] R. Pesch, “On the Question of Fill”, APL Quote Quad Vol. 15 No. 1, September 1984, p. 9

Originally appeared in the APL86 Conference Proceedings, APL Quote Quad, Volume 16, Number 4, 1986-07.

 created: 2013-02-28 22:05 updated: 2013-03-02 21:05