Extending the Domains
Vector 18:3, page 115
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 115
0. Introduction¶
We all understand the meaning of the APL expression
The question is: how would you generalise that expression to n dimensions?
Our suggestion is that V⍳⌈/V should be sufficient for all inputs with rank ≥ 1.
1. Extending a Function’s Domain¶
A function mapping is always defined for the simplest case. This definition is then extended, or can be extended, to higher-order arrays provided the arguments meet certain rules of conformability.
This is another of those neat devices by which APL achieves its remarkably concise expressive power. The idea here is to generalise it a little.
1.1 A function is defined using formal parameters. When the formal parameter is given an actual value, we say the parameter is bound. In conventional logic, a parameter is either bound or free and, not for the first time, we find that concepts devised for static logic are inadequate for computing processes. We shall bind a parameter to an actual value one dimension at a time, so that a parameter may be free, partially bound, or fully bound.
There is a long established convention in APL that the leading, leftmost, earlier, slower cycling, outer dimensions represent a higher level of detail, and have a greater importance, than the later dimensions. Reduction, for instance, will, by default, collapse out the last, and therefore least important, dimension.
When an actual value has precisely the number of dimensions specified by the functional model, we say the parameter is fully bound; when it has more, it is partially bound.
(These are distinct from the similarly named concepts in conventional logic, where an n-place function is "fully bound" when all n parameters are given actual values. If some, but not all, parameters are known, the function is "partially bound". These are not concepts we need at this stage.)
1.2 When an actual value has more dimensions than are required by the functional model, the value is "split" on the leading dimension, the function is applied to each of the "slices" thus produced, and these partial results are then "joined", to give the actual result. This process of binding one (leading) dimension at a time, is applied recursively.
We do not need to define "splitting" and "joining" precisely, since they are not visible outside the interpreter. Suffice to say that one process is the inverse of the other.
With dyadic functions, the left and right arguments are both split at the same time. When both arguments are fully bound, the function can be applied.
For example:
requires us to split each argument on the first dimension:
+------------------+
|1 ⌽ 1 2 3 4 |
+------------------+
|0 ⌽ 5 6 7 8 |
+------------------+
|2 ⌽ 9 10 11 12 |
+------------------+
Now that each pair is fully bound, with a scalar left argument applied to a vector right argument, in accordance with a functional model of (ℝ*ℕ)↤⟨ℕ;ℝ*ℕ⟩, we can apply the function 3 times:
and join up the separate result items, to give us our the result proper:
1.3 Should the left argument be fully bound, while the right argument is only partially bound, the "splitting" process continues, and we test for conformability again, using the fully bound left argument with each slice of the right argument.
For example:
requires us to split each argument on the first dimension:
+----------------+
|10 + 1 2 3 4 |
+----------------+
|20 + 5 6 7 8 |
+----------------+
|30 + 9 10 11 12 |
+----------------+
so that we are fully bound on the left, but we need to split again on the (newly created) first dimension of each item in the right argument:
+-------+-------+-------+-------+
|10 + 1 |10 + 2|10 + 3|10 + 4|
+-------+-------+-------+-------+
|20 + 5 |20 + 6|20 + 7|20 + 8|
+-------+-------+-------+-------+
|30 + 9 |30 + 10|30 + 11|30 + 12|
+-------+-------+-------+-------+
Now that each pair is fully bound, with a scalar left argument and a scalar right argument, we can apply the function 12 times:
which we join
and join again, to give us our the result proper:
Similarly, should the right argument be fully bound, while the left argument is only partially bound, the "splitting" process continues, and we test for conformability again, using the fully bound right argument with each slice of the left argument.
1.4 With nested arrays, the process may well continue until all the outer dimensions have been bound. Binding the last dimension, which is equivalent to looping through a vector with a scalar index, effectively discloses each nested item in turn, at which point the conformance testing process is applied all over again.
requires us to split each argument on the first dimension, incidentally disclosing thereby each item in the right argument:
+---------------+
|10 + 99 |
+---------------+
|20 + 2 3 ⍴⍳6 |
+---------------+
|30 + 2 3 5 |
+---------------+
The conformability rules are applied anew to each of these items. The first item is already fully bound, left and right; the second item requires two further splits before achieving this happy state, and the third row requires just one more split. The result is a three element nested vector.
1.5 All this assumes that the intermediate results can be "joined" in some way: in particular, we wish to preserve rectangularity, and the structure (depth of nesting) should remain unaltered. No "fill" operation is defined.
If the process fails on any one item, the arguments are not conformable and the whole extension process fails. Compare
with the following:
1.6 Just briefly, a few standard (re)definitions:
Where the mapping for a monadic function is defined for a k-dimensional object, and it is applied to an n-dimensional object (with n ≥ k, necessarily), the function is applied to the last k dimensions.
The leading (n-k) dimensions are known, to use a term credited to Paul Berry, as the frame. When (n-k)=0, the frame is said to be empty.
Where the function is defined for any arbitrarily large array (monadic rho, for example, or transpose) and it is applied to an n-dimensional object, then we take k=n, and the frame is necessarily empty. All other functions are, to greater or lesser degree, pervasive.
With a dyadic function, the definitions are similar, except that k, n and (n-k) may be different for the left and right arguments. This gives rise to a left frame and a right frame, which may differ in length.
If the two frames differ by, say, d minor dimensions, the effect of the splitting and joining rules is to notionally extend the shorter frame by appending thereto a further d dimensions. (Note that it is the end of the frame that gets extended, not the whole dimension vector.) Not unnaturally, this is known as frame extension.
In the particular case where the function returns a scalar result from a scalar argument (left or right or both), and precisely one of the appropriate argument(s) is scalar before any splitting process begins, this feature is known as scalar extension1. This commonly occurs with the scalar dyadics, dyadic epsilon and dyadic iota.
When the left and right frames have the same rank, and the corresponding dimensions in each frame have the same length, the two arguments are said to conform.
More generally, if m is the length of the shorter of the left frame and the right frame, and the first m dimensions in each frame are identical in length, the two arguments are said to be conformable.
2. Applying the Extended Definition¶
2.1 The complete model for a function may be the sum of many simple mapping. These simple mappings must be such that we can unambiguously choose which mapping to apply, knowing only the type and rank of the arguments. Otherwise we have a DEFINITION ERROR.
(This is actually quite a difficult condition to enforce, in the general case. For example, a function defined over ((ℝ*ℕ)↤⟨ℕ;ℝ*ℕ⟩)⊕(ℝ*ℕ)↤⟨ℕ*ℕ;ℝ⟩ cannot sensibly be applied when both arguments are vector. This could be resolved by introducing some sort of ordering of the separate phrases in a function model. Or, more simply, by rejecting such esoteric structures with a NONCE ERROR.)
2.2 A rough definition of the process for applying a monadic function to n-dimensional arguments is given in the box.
2.3 The process of applying a dyadic function is an elaboration thereof.
We check whether we can bind either the left or the right argument.
If we can bind neither,
we compare the leading dimensions of the left and right rank vectors. The corresponding dimensions match if they are equal in length (or, perhaps, if one of them is unit-length).
In the event of a mis-match, we have a LENGTH ERROR.
In the event of a match, we split on the leading dimension, and the process is repeated recursively.
Once one argument is fully bound, we can treat the rest of process like the application of a monadic function. If that process fails to terminate in good order, and there are still candidate models to among, then we split along the leading dimension of the fully bound argument, and call the dyadic process recursively.
If we exhaust the second set of dimensions without finding an appropriate simple mapping, we have a DOMAIN ERROR.
2.4 This process is sufficiently general to accommodate any ad hoc extensions to higher rank.
In most cases, however, the mapping will be something simple like ℝ↤⟨ℝ;ℝ⟩ . Given an expression like (scalar+matrix) , we can immediately identify the left and right frames, and set up an addressing loop without needing to go through all this taradiddle.
While ad hoc extensions are deprecated there is no way we can guarantee that they will not occur in user-defined functions. Also, this very complexity may be useful later, when handling sub-components in arrays of user-defined objects.
3. Some Anomalies¶
3.1 To quote one of Scott and Strachey’s typically apposite phrases:
… any attitude of restricting generality is a bad habit which can be misleading in analogous but more complicated situations … .
Scott and Strachey do not specifically mention the dangers of inconsistent ad hoc extensions, but they too are an obstacle to generality, and we cannot ignore them.
3.2 In 1979, Paul Berry wrote:
"When a function takes two arguments, there may be a requirement that the shape of one argument in some manner conform to the shape of the other. The arguments may have to have the same rank, or the same shape, or to differ in rank or shape in a particular way.
Two arrays whose rank and shape are acceptable for a particular dyadic function are said to be conformable. The conformability requirements of a function are described with the definition of each."
Fifteen years later, this paragraph had disappeared from the Sharp APL Reference Manual, to be replaced by a discussion of the more general concepts of frame and cell, which are realised through the use of operators specific to that product. The designers will have found this approach necessary because, as implied above, the conformability requirements do not follow a consistent pattern. Some of the exceptions are outlined below.
3.3 The obvious functional model for catenation of character arrays would be (ℍ*ℕ)↤⟨ℍ*ℕ;ℍ*ℕ⟩ , that is to say, two vectors are joined to make a new vector. This works most of the time, but, applying the splitting and joining rules, to the expression
we note that the right argument is fully bound, but that we need to split the left:
At this point, we can apply the function twice, to derive two vectors:
which are then joined to give the result proper, just as it does in J. In APL, however, to quote page 6-85 of the current Sharp APL manual:
"If the arrays are not of the same rank, then either one of them must be a scalar, or of rank which differs from the other by one. If they differ by one in rank, the array of lesser rank is treated as if it had length 1 along the axis of joining. If one is a scalar, it is treated as an array of the same shape as the other except along the axis of join, which is treated as length 1."
which is a model of clarity in a difficult situation. However, the fact that an explanation is necessary is indicative of an anomaly.
If catenation had the mapping (ℍ*ℕ)↤⟨ℍ*ℕ;ℍ⟩, then with
we note that neither argument is fully bound, and we therefore split both
At this point, we can apply the function twice, to derive two vectors:
which are then joined to give the result demanded by the APL standard.
The catenation function for character arguments, then, uses one of the models
according to context — a context, moreover which is data-dependent, and can therefore only be determined at run-time. This is not incompatible with our objective of making all expressions automatically extendable to higher dimensions, but it does conflict with the objective of predictability.
Consistency and simplicity must be the priorities. If we adopt the mapping
for all cases, then
i) the function behaves as in J (no special-casing for ranks differing by 1);
ii) we can predict the function’s behaviour when the arguments differ in type.
Given F←(A;B;C)
then F←F,99 100 101
is fully bound on both sides, so the expression will deliver the vector
It is worth observing that
will deliver the vector
The result has acquired another degree of nesting, but is to all intents and purpose indistinguishable from the original vector of 99 100 101 . This is analogous to the way the result of 0.5+X-0.5 can be used in contexts restricted to integer values, even though it is quite possibly stored as floating-point.
3.4 The mapping for both take and drop on numeric arrays is
The standard definition for these two functions on higher-dimensions implies a mapping of
For instance, according to our split/join rules, the expression
should fail with LENGTH ERROR when the interpreter tries to split and partner off the two elements from the left argument and the three slices from the right argument, whereas the standard definition will return the result
If the take function were always applied with the mapping (ℝ*ℕ)↤⟨ℕ;ℝ*ℕ⟩ then we would have to use two separate calls to produce the above result, something along the lines of:
3.5 It may be totally useless, but our extension rules allow the following:
We have a problem. The ever popular idiom, ⍳⍴⍴A , should, according to our rules, return a (1 × N) matrix, given a mapping for monadic iota of (ℕ*ℕ)↤ℕ .
In fact, the model has been extended on an ad hoc basis to (ℕ*ℕ)↤ℕ⊕ℕ*1 . This conflicts with our objective of "automatic extension". If we restrict monadic iota to scalar arguments, then all arguments must be scalarised before being fed to monadic iota. This is easily done using the monadic head and tail functions which were suggested in "Reflexive Data Domains", with the following definitions:
The idiom ⍳⍴⍴A now becomes ⍳↑⍴⍴A , and, in general, use of head and tail will lead to slightly untidier code for some idioms, but shorter code and greater generality for many utilities.
3.6 The reverse happens with compress and expand, because here we find a scalar can be interpreted as a single-element vector. Somewhat exceptionally, both left and right arguments are interpreted as unit-length vectors, even when both are scalar. A vector result from, e.g, 1/6 , is the only possible consistent treatment, given that 0/6 must also be a vector. Both instances are clearly ad hoc extensions of the obvious models: (ℝ*ℕ)↤⟨ℕ*ℕ;ℝ*ℕ⟩ in the case of replication, and (ℝ*ℕ)↤⟨𝟚*ℕ;ℝ*ℕ⟩ in the case of expansion.
As it happens, ad hoc extensions to lower rank cause us no problems, because the split-and-join rules will first find and apply the definition for vectors.
3.7 A slightly different thing happens with the scalar dyadics, where a number of implementations treat single-element vectors as scalars. In such cases, 1 2 3 +,99 returns a three element vector.
In effect, the unit-length vector has been extended, and this has lead to proposals that all unit-length dimensions be deemed to "match" the corresponding dimension of the other argument. Except that this extension would not occur if the other argument were a scalar.
This is getting messy, but a consistent set of rules is possible. And it could be useful. For instance, with
we could specify either
or
which involve changes in the dope vector only, and avoid the usual replication.
3.8 It is really unfortunate, but we have introduced an anomaly of our own: scalar extension does not apply to the left argument of membership (∊) when the right argument is a domain. The function model is 𝟚↤⟨𝕌;𝔻⟩ .
When the right argument is drawn from the normal data domain, the present model for dyadic epsilon is
Had the function model been 𝟚↤⟨𝕌;𝕌*ℕ⟩ we would have been able to look for a given array within a list of arrays, which might have been useful for table lookup, but with this definition the left argument would not be pervasive.
3.9 It might be possible to extend the definition of assignment, if we had a definition of "namelists" which we could use as the left argument.
3.10 Domino, inner and outer products, encode and decode have their own rules of application. Inner and outer products are our first examples of dyadic operations involving domain expressions, and will have to wait; encode and decode can then be formalised in terms of inner and outer products. The extension of monadic domino to vector and scalar arguments causes us no problems; dyadic domino remains an exception.
4. Conclusions¶
4.1 This is not a new problem. When Byron wrote
Our souls at last congenial meet,
Nor can thy lot my rank disgrace;
Our intercourse is not less sweet,
Since worth of rank supplies the place.
he was obviously thinking of frame extension. The couple of hundred years that have elapsed since that was written have seen a number of other approaches to the problems of conformance.
4.2 Such approaches have typically concentrated on the problems of making certain functions pervasive on nested arrays. The less complicated approach taken here is to define rules which apply to all functions equally, be they primitive, derived or user-defined. These rules can then be made a part of the definition of function application, and would not need defining specially for any of the primitives.
4.3 Such an approach requires consistency in the definition of primitive functions, and so the principal costs associated with this approach are
- the need to redefine catenation, take and drop and monadic iota;
- which, in turn, makes it incompatible with all existing implementations.
4.4 The benefit is that a function written for the simplest case can be automatically extended by the interpreter to any number of dimensions and any depth of nesting.
This is a goal worth pursuing.
How we get there is another matter.
The naïve formulation given above can be explained and understood in approximately 5 minutes, but it currently stands in need of further work.
4.5 For the working programmer, there is only one sensible course of action: live with the present restrictions until a better implementation appears.
Designers and implementors of new interpreters, however, recognising that almost all implementations are dialects of the standard, need not feel so constrained.
5. References¶
5.1 [anon.], Sharp APL Reference Manual
Soliton Associates, Toronto [1994]
5.2 Paul Berry, Sharp APL Reference Manual
I P Sharp Associates Ltd, Toronto [1979]
5.3 George Gordon, Lord Byron, To E——.
(in) Hours of Idleness [1807]
5.4 Dana Scott and Christopher Strachey
Towards a Mathematical Semantics for Computer Languages
(in) Proc. of Symposium on Computers and Automata (ed. J Fox)
Polytechnic Institute of Brooklyn Press, New York [1971]
-
a slightly unfortunate term, since it is actually the empty frame which gets extended ↩