|
Rank and Uniformity Abstract Rank is elucidated through an executable model. Integrated rank support for specific functions can be vastly more efficient than the general algorithm in computing v"r , and uniform verbs provide a way to extend the more efficient implementation to a large class of verbs. Acknowledgment Ideas presented herein evolved over many conversations with K.E. Iverson. 0 Rank Verb (function) rank was introduced by Iverson [1978 §6], further developed in Iverson [1983, 1987, 1995], and implemented in SHARP APL, SHARP APL/HP, SAX, A, and J (see Bernecky et al. [1983, 1987], Hodgkinson [1986], Steinbrook [1986], Whitney [1989], and Hui et al. [1990], respectively). A verb of rank r is defined on arguments with rank bounded by r ; the extension to higher-rank arguments is the same for all verbs. The rank conjunction " (operator) augments the default ranks of a verb by user-specified ranks. It provides for the generalization of a verb to higher-rank arrays, and could justifiably be called the generalization or extension operator; it also provides for consistent application to lower-rank arrays, subsuming and superseding the anomalous bracket-axis operator. Various aspects of rank are here discussed in terms of a model in J, updated from Hui [1987 §A.2, 1992 §3.2]. The notation is defined in Iverson [1995], and additional annotated examples can be found in Appendix A. Frames and Cells. A rank r splits the argument shape into the frame and the cell shape; a positive r specifies the number of trailing cell axes, while a negative r specifies the negative of the number of leading frame axes.
rk =. #@$
er =. (0:>.(+rk))`(<.rk) @. (0:<:[)
fr =. -@er }. $@]
cs =. -@er {. $@]
boxr =. ]`(<@$ , [ $: */@[}.])@.(*@#@])
cells =. fr $ cs boxr ,@]
For rank r and argument y , the phrase r er y computes the effective rank (non-negative and bounded by #$y); r fr y computes the frame and r cs y the cell shape; and r cells y computes the array of cells with shape r fr y , each cell individually boxed and shaped s=. r cs y (r cells y ↔ <"r y). The recursively-defined verb s boxr y produces the list of such cells. The model is shown in action on x*"0 _1 y , the atoms (scalars) of x times the items of y : x=. 1 2 3 y=. i.3 2
Agreement. In the dyad v"r , commonly the left and right frames match, that is, the two cell arrays have the same shape; if not, several design choices are possible: In scalar agreement, one frame must be empty, and the single cell is reshaped using the other frame; in suffix agreement, one frame must be a suffix of the other, and again the list of cells is reshaped using the other frame; finally, in prefix agreement, one frame must be a prefix of the other, and each cell is reshaped with the excess in the other frame. All three agreements are proper generalizations of scalar extension in APL\360, with cells acting the role of scalars. Agreement results in the two cell arrays having the same shape (“the frame”). Prefix agreement is adopted in J as suggested by Whitney [1992], because it best fits the emphasis on leading axes.
pfx =. <.&rk
agree =. (pfx {. $@[) -: (pfx {. $@])
frame =. [:`($@([^:(>&rk))) @. agree
rag =. frame $ ([: */ rk@]}.$@[) # ,@]
lag =. rag~
rag and lag apply to both cell arrays (the results of cells in the previous section), producing cell arrays with the same shape. If v"r itself were used in the model, rag could be defined more directly from the specification: (rk@]}.$@[) $"1 0 ] — each cell is reshaped with the excess in the other frame. In the continuing example, rag and lag have no effect because the left and right frames match.
Assembly. After agreement, the phrase v&.> applies v under > to corresponding boxed left and right argument cells, to produce an array of boxed result cells. It remains to assemble the overall result from the individual results. Cells are brought to a common rank by adding leading unit axes, then to a common shape by padding. The overall shape is fm,sir , where fm is the frame and sir is the common shape of the individual results. This is a design choice: the individual results could be required to have a common shape without further intervention, but this permissive assembly proves useful. For example, open > on a list of boxed words yields a matrix with the words padded to a common length.
mrk =. >./@:(rk&>)@,
crank =. mrk ,:@]^:(-rk)&.> ]
msh =. >./@:( $&>)@,
cshape=. <@msh {.&.> ]
asm =. > @ cshape @ crank
rank =. 2 : 0
'm l r'=.3&$&.|.y.
([: asm [: x.&.> m&cells) : ↵
([: asm l&cells@[ (lag x.&.> rag) r&cells@])
)
The conjunction rank (with a 2-line body) integrates the model components. The left argument x. is the verb v ; the right argument y. is reshaped from the right to exactly 3 numbers and assigned to m , l , and r . [ za=. xa*&.>ya ┌───┬───┬─────┐ │0 1│4 6│12 15│ └───┴───┴─────┘ asm za 0 1 4 6 12 15 x * rank 0 _1 y 0 1 4 6 12 15 Zero Frame. If the frame contains 0 (as in 3 *"1 i. 0 4), there are no argument cells to apply v to, and the shape of a result cell (the value of sir) is indeterminate. Pesch [1986] describes a variety of strategies to address this problem. In J, the shape is calculated if v is uniform (see below); otherwise v is applied to a cell of fills. 1 Integrated Rank Support While the rank conjunction as modelled above can be used for any verb, much more efficient implementation of v"r exists for particular v . The specialized implementation is called integrated rank support (IRS) because the code resides with each v . The strategy was first used in SHARP APL to good effect (Bernecky & Bezoff [1986]). The increased efficiency derives from (a) exploiting specific properties of v ; (b) avoiding explicit construction of the argument and result cells; and (c) reducing the overhead in separate application of v to each cell or pair of cells (e.g. in x+y , validating that x and y are numeric for each pair of cells). We consider two examples: Head {."1 y yields the first element of each row. The general routine builds an argument cell for each row, only to have {. discard most of it; in contrast, {. with IRS strides through y one row at a time, taking the first element, without explicitly constructing each row vector. In this case, IRS provides an order of magnitude improvement: constant time vs. linear time for each row. Itemize/laminate ,: provides a less extreme example. The monad adds a leading unit axis to the argument, and ,:"r y ↔ (((-r)}.$y),1,(-r){.$y)$,y . The dyad x,:"(r,s)y can be computed as follows: r1=. r+p=. 0<r s1=. s+q=. 0<s ,:"0^:(p+:q)(,:"r^:p x),"(r1,s1),:"s^:q y Exactly which verbs should have integrated rank support is a trade-off between the expected utility, interpreter size, and implementation effort. v"r invokes IRS as appropriate; conversely, v invokes the general rank routine for any sub-case that it chooses not to handle specifically. In J, IRS is provided for all atomic (scalar) verbs and for the following verbs, where † indicates IRS planned but not yet implemented and ‡ indicates IRS not planned.
The following table lists the speed-up in execution for v"r using the general routine versus v"r with IRS, on the arrays defined at the end of the table. The factors were obtained from JPC386 release 2.04 running on a 80486/50 machine (and are roughly applicable to all machines).
2 Uniform Functions A verb v is uniform if the result shape depends only on the argument shape(s), and the result rank depends only on the argument rank(s). That is, there is a shape calculator vs and a rank calculator vr such that
Iverson [1978 §6] defines a uniform function as one whose result shape depends only on the argument shapes, and the result rank is a number associated with each verb. The advantages of having a rank calculator will be apparent shortly. Keenan [1979] defines uniformity in terms of shape and type; however, the extra consideration of type does not greatly enhance the concept, and leads to the conclusion that verbs such as + and * are not uniform. The so-called scalar functions (+ - * % etc.) are uniform. Ravel/append is uniform. Integers i. is not uniform: 3 and 4 have identical shape but i.3 and i.4 do not. Take {. is not uniform, but m&{. (take with a fixed left argument) is; likewise drop, reshape, and replicate. Appendix B lists the primitive verbs together with either rank/shape calculators or an invalidating example. If u and v are uniform, then so are the compositions u@:v and u&:v , with the rank and shape calculators of the composition being the composition of the calculators. The related compositions u@v and u&v are complicated by that they inherit the ranks of v (denoted m , l , and r respectively for the monadic, left, and right ranks). But since v is uniform, the result cells in v y are exactly the rank (vr m<.#$y) cells, and the result cells in x v y are the rank (l<.#$x)vr(r<.#$y) cells. Thus:
The expressions on the right hand side can be much more efficient to evaluate than those on the left. For example, on two 8000-element floating point vectors, x *:@+ y (square the element-wise sums) takes over 24 times as long as the equivalent *:"0 x+y . The former applies *: to + on two atoms, 8000 times; the latter applies + once to x and y in toto, then applies *:"0 once to that, reaping the benefits from the integrated rank support in *: and + . The greater efficiency is due to the same factors as for IRS: obviating the explicit construction of cells and replacing multiple application to cells by one application to entire arguments. Moreover, u@v is uniform, with the following calculators:
fl =. ] - <. NB. frame length
fa =. -@[ }. ] NB. frame axes
ca =. ([ -@<. #@]) {. ] NB. cell axes
The computations derive by straightforward consideration of the workings of the rank conjunction (Section 0). Each expression consists of the contribution from the frame joined to the contribution from the cells. For the shape calculator , catenates the frame axes to the result cell axes, while for the rank calculator + adds the frame length to the cell rank. A similar analysis leads to the conclusion that if u , v , and w are uniform and n and r are nouns, then the following verbs are also uniform:
It remains to implement a calculus of uniform verbs so that like integrated rank support, the more efficient code for uniform verbs can be invoked automatically when possible, reducing the need to sacrifice readability for efficiency (for example, using (u0"r0)@:(u1"r1)@:(u2"r2) instead of the more readable u0@u1@u2). It appears that a calculus on rank alone suffices to produce much benefit. The rank calculus, being concerned with single numbers, is simpler than the shape calculus, and makes an important and useful intermediate step. We conjecture that the analysis for integrated rank support and for uniform verbs is applicable to APL dialects that have the each operator ¨ , with similar efficiency gains. References
Appendix A. Annotated Examples A.0 Rank Model
rk =. #@$
er =. (0:>.(+rk))`(<.rk) @. (0:<:[)
fr =. -@er }. $@]
cs =. -@er {. $@]
boxr =. ]`(<@$ , [ $: */@[}.])@.(*@#@])
cells =. fr $ cs boxr ,@]
pfx =. <.&rk
agree =. (pfx {. $@[) -: (pfx {. $@])
frame =. [:`($@([^:(>&rk))) @. agree
rag =. frame $ ([: */ rk@]}.$@[) # ,@]
lag =. rag~
mrk =. >./@:(rk&>)@,
crank =. mrk ,:@]^:(-rk)&.> ]
msh =. >./@:( $&>)@,
cshape=. <@msh {.&.> ]
asm =. > @ cshape @ crank
rank =. 2 : 0
'm l r'=.3&$&.|.y.
([: asm [: x.&.> m&cells) : ↵
([: asm l&cells@[ (lag x.&.> rag) r&cells@])
)
A.1 Frames and Cells [ y=. i.2 3 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0 (er;fr;cs) y NB. effective rank; frame; cell shape ┌─┬─────┬┐ │0│2 3 4││ └─┴─────┴┘ 0 cells y NB. rank 0 cells aka 0-cells ┌──┬──┬──┬──┐ │0 │1 │2 │3 │ ├──┼──┼──┼──┤ │4 │5 │6 │7 │ ├──┼──┼──┼──┤ │8 │9 │10│11│ └──┴──┴──┴──┘ ┌──┬──┬──┬──┐ │12│13│14│15│ ├──┼──┼──┼──┤ │16│17│18│19│ ├──┼──┼──┼──┤ │20│21│22│23│ └──┴──┴──┴──┘ 1 (er;fr;cs) y ┌─┬───┬─┐ │1│2 3│4│ └─┴───┴─┘ 1 cells y ┌───────────┬───────────┬───────────┐ │0 1 2 3 │4 5 6 7 │8 9 10 11 │ ├───────────┼───────────┼───────────┤ │12 13 14 15│16 17 18 19│20 21 22 23│ └───────────┴───────────┴───────────┘ 2 (er;fr;cs) y ┌─┬─┬───┐ │2│2│3 4│ └─┴─┴───┘ 2 cells y ┌─────────┬───────────┐ │0 1 2 3│12 13 14 15│ │4 5 6 7│16 17 18 19│ │8 9 10 11│20 21 22 23│ └─────────┴───────────┘ 3 (er;fr;cs) y ┌─┬┬─────┐ │3││2 3 4│ └─┴┴─────┘ 3 cells y ┌───────────┐ │ 0 1 2 3│ │ 4 5 6 7│ │ 8 9 10 11│ │ │ │12 13 14 15│ │16 17 18 19│ │20 21 22 23│ └───────────┘ _1 (er;fr;cs) y ┌─┬─┬───┐ │2│2│3 4│ └─┴─┴───┘ _1 cells y NB. rank-_1 cells aka _1-cells ┌─────────┬───────────┐ NB. aka major cells aka items │0 1 2 3│12 13 14 15│ │4 5 6 7│16 17 18 19│ │8 9 10 11│20 21 22 23│ └─────────┴───────────┘ _1 cells i.3 4 ┌───────┬───────┬─────────┐ │0 1 2 3│4 5 6 7│8 9 10 11│ └───────┴───────┴─────────┘ _1 cells i.4 ┌─┬─┬─┬─┐ │0│1│2│3│ └─┴─┴─┴─┘ _1 cells 3 ┌─┐ │3│ └─┘ _2 cells y ┌───────────┬───────────┬───────────┐ │0 1 2 3 │4 5 6 7 │8 9 10 11 │ ├───────────┼───────────┼───────────┤ │12 13 14 15│16 17 18 19│20 21 22 23│ └───────────┴───────────┴───────────┘ A.2 Rank Monad The computation to be modelled is i."_1 y . y=. 6 4 9 1 (er;fr;cs) y NB. effective rank; frame; cell shape ┌─┬┬─┐ │1││3│ └─┴┴─┘ [yc=. _1 cells y ┌─┬─┬─┐ │6│4│9│ └─┴─┴─┘ [zc=. i.&.>yc NB. apply i. to each cell ┌───────────┬───────┬─────────────────┐ │0 1 2 3 4 5│0 1 2 3│0 1 2 3 4 5 6 7 8│ └───────────┴───────┴─────────────────┘ asm zc NB. permissive assembly 0 1 2 3 4 5 0 0 0 0 1 2 3 0 0 0 0 0 0 1 2 3 4 5 6 7 8 i. rank _1 y 0 1 2 3 4 5 0 0 0 0 1 2 3 0 0 0 0 0 0 1 2 3 4 5 6 7 8 A.3 Agreement I The computation to be modelled is x,"1 y , append vectors to vectors.
[ x=. 'PQ'
PQ
[ y=. 3 4 $'abcdefghijkl'
abcd
efgh
ijkl
1 er x 1 er y NB. effective rank
1 1
1 fr x 1 fr y NB. frame
3
1 cs x 1 cs y NB. cell shape
2 4
NB. argument cells before agreement
[ xc=. 1 cells x [ yc=. 1 cells y
┌──┐ ┌────┬────┬────┐
│PQ│ │abcd│efgh│ijkl│
└──┘ └────┴────┴────┘
NB. argument cells after agreement
[ xa=. xc lag yc [ ya=. xc rag yc
┌──┬──┬──┐ ┌────┬────┬────┐
│PQ│PQ│PQ│ │abcd│efgh│ijkl│
└──┴──┴──┘ └────┴────┴────┘
[ za=. xa,&.>ya NB. apply , to corresponding cells
┌──────┬──────┬──────┐
│PQabcd│PQefgh│PQijkl│
└──────┴──────┴──────┘
asm za NB. assemble to produce the required result
PQabcd
PQefgh
PQijkl
x , rank 1 y
PQabcd
PQefgh
PQijkl
A.4 Agreement II The computation to be modelled is x,"0 1 y , append scalars to vectors.
[ x=. 3 2$'012345'
01
23
45
[ y=. 3 4$'abcdefghij'
abcd
efgh
ijab
0 er x 1 er y NB. effective rank
0 1
0 fr x 1 fr y NB. frame
3 2 3
0 cs x 1 cs y NB. cell shape
4
NB. argument cells before agreement
[ xc=. 0 cells x [ yc=. 1 cells y
┌─┬─┐ ┌────┬────┬────┐
│0│1│ │abcd│efgh│ijkl│
├─┼─┤ └────┴────┴────┘
│2│3│
├─┼─┤
│4│5│
└─┴─┘
NB. argument cells after agreement
[ xa=. xc lag yc [ ya=. xc rag yc
┌─┬─┐ ┌────┬────┐
│0│1│ │abcd│abcd│
├─┼─┤ ├────┼────┤
│2│3│ │efgh│efgh│
├─┼─┤ ├────┼────┤
│4│5│ │ijkl│ijkl│
└─┴─┘ └────┴────┘
[ za=. xa,&.>ya NB. apply , to corresponding cells
┌─────┬─────┐
│0abcd│1abcd│
├─────┼─────┤
│2efgh│3efgh│
├─────┼─────┤
│4ijkl│5ijkl│
└─────┴─────┘
asm za NB. assemble to produce the required result
0abcd
1abcd
2efgh
3efgh
4ijab
5ijab
x , rank 0 1 y
0abcd
1abcd
2efgh
3efgh
4ijab
5ijab
A.5 Agreement III — Outer Product The computation to be modelled is x*"0 _ y , multiply scalars in x by the entire of y .
x=. 1 2 3 4
y=. 8 5 7
0 er x _ er y NB. effective rank
0 1
0 fr x _ fr y NB. frame
4
0 cs x _ cs y NB. cell shape
3
NB. argument cells before agreement
[ xc=. 0 cells x [ yc=. _ cells y
┌─┬─┬─┬─┐ ┌─────┐
│1│2│3│4│ │8 5 7│
└─┴─┴─┴─┘ └─────┘
NB. argument cells after agreement
[ xa=. xc lag yc [ ya=. xc rag yc
┌─┬─┬─┬─┐ ┌─────┬─────┬─────┬─────┐
│1│2│3│4│ │8 5 7│8 5 7│8 5 7│8 5 7│
└─┴─┴─┴─┘ └─────┴─────┴─────┴─────┘
[ za=. xa*&.>ya NB. apply * to corresponding cells
┌─────┬────────┬────────┬────────┐
│8 5 7│16 10 14│24 15 21│32 20 28│
└─────┴────────┴────────┴────────┘
asm za NB. assemble to produce the required result
8 5 7
16 10 14
24 15 21
32 20 28
x * rank 0 _ y
8 5 7
16 10 14
24 15 21
32 20 28
A.6 Permissive Assembly The computation to be modelled is x{."0 1 y .
y
Barlett, Sue
Doe, John
Other, A.N.
$y
3 12
[ x=. y i."1 ',' NB. index of comma in each row
7 3 5
0 (er;fr;cs) x NB. effective rank; frame; cell shape
┌─┬─┬┐
│0│3││
└─┴─┴┘
1 (er;fr;cs) y
┌─┬─┬──┐
│1│3│12│
└─┴─┴──┘
[ xc=. 0 cells x
┌─┬─┬─┐
│7│3│5│
└─┴─┴─┘
[ yc=. 1 cells y
┌────────────┬────────────┬────────────┐
│Barlett, Sue│Doe, John │Other, A.N. │
└────────────┴────────────┴────────────┘
xc -: xa=. xc lag yc
1
yc -: ya=. xc rag yc
1
[ za=. xa{.&.>ya NB. apply {.
┌───────┬───┬─────┐
│Barlett│Doe│Other│
└───────┴───┴─────┘
asm za NB. permissive assembly
Barlett
Doe
Other
$ asm za
3 7
x {."0 1 y
Barlett
Doe
Other
(y i."1 ',') {."0 1 y
Barlett
Doe
Other
surname=. (] i."1 ','"_) {."0 1 ]
surname y
Barlett
Doe
Other
Appendix B. Uniform Functions The primitive verbs in the table on the right are uniform with the indicated rank and shape calculators vrb and vsb , applicable to arguments with rank bounded by the ranks of v . (m , l , and r , respectively, for the monadic, left, and right ranks.) The rank and shape calculators for general arguments are as follows:
fl =. ] - <.
fa =. -@[ }. ]
ca =. ([ -@<. #@]) {. ]
The table entry for + represents the so-called scalar functions, which are:
____________________________________ The following primitive verbs are not uniform; in each case, results with different shapes are produced from the indicated arguments having the same shape.
ic =. 1&{.@(,&1)
ms1 =. >.&# {.!.1&.|.`1:@.(0&=@#@])&> ;
gcat =. ({.@(+/) , }.@(>./)) @ ms1
gstch =. (*@+&# $ >.&(1&{.)) , gcat&}.
ms0 =. >.&# {.!.1&.|.`0:@.(0&=@#@])&> ;
glam =. 2: , >./@ms0`1:@.(0&=@>.&#)
Originally appeared in the APL95 Proceedings, APL Quote Quad, Volume 25, Number 1, 1996-06-04 to -08.
|