Essays/Rank

Rank

Many calculations can be expressed in J without looping or reshaping. To understand why this is the case, we consider the following question:

A verb is applied to data. To which subsets of the data does it apply, and how are the results assembled?

To see that this is a reasonable question, consider these examples:

verb applied to each element of an array:

   * A           NB. signum

verb applied to each row of an array:

   ". A          NB. do

verb applied to array as a whole:

   , A           NB. ravel

A good understanding of rank involves several key ideas:

frame and cell
verb rank
prefix agreement
assembly
rank operator
item verbs

In the following, arrays are named with letters V, M, A followed by numbers to denote their shape. Thus V5 for a vector of length 5, M34 for a 3-by-4 matrix, A243 for a 2-by-4-by-3 array and so on. Where actual values are required, V5 will be defined as i.5, M34 as i.3 4, etc.

Frame and Cell

The shape of an array can be split up into two parts, a leading part called the frame and the remaining part called the cells. Either frame or cells can be empty. The frame can be thought of as the holding structure for the cells.

The term k cell specifies a cell of rank k. A -k cell is a cell of rank r-k, where r is the rank of the array. An item is a _1 cell.

For example, the shape of the matrix M46 is 4 6, and this can be split up in three different ways, as follows.

`frame ; cell`	description
`; 4 6`	the size of the frame is empty, and size of the cell is 4 by 6. The cell is a 2-cell and is the entire matrix
`4 ; 6`	the size of the frame is 4 and the size of the cells is 6. The cells are 1-cells and are the rows
`4 6 ;`	the size of the frame is 4 by 6, and the size of the cells is empty. The cells are 0-cells and are the scalars

Verb Rank

All J verbs, including user-defined verbs, are assigned a rank as three numbers: the monadic rank, the dyadic left rank, and the dyadic right rank.

A monadic verb of rank k acts on the k-cells, with the following three-step process:

the argument is split up into k-cells
the verb is applied to each k-cell
the individual results are then assembled

A dyadic verb of rank j k acts on the j and k-cells, with the following three-step process:

the left argument is split up into j-cells, and the right argument into k-cells
the verb is applied between each pair of cells
the individual results are then assembled

Note that these steps are only notional; in many cases, the interpreter knows how to evaluate verbs with rank and carries out the evaluation directly.

Prefix Agreement

Suppose we want to multiply two arrays together (or apply any scalar verb to the arrays). What shapes must they have in order for the operation to be successful?

This will certainly work if they have the identical shape, or if one is a scalar, in which case it is reshaped to match the other (this is known as scalar extension).

It will also work if the shape of one of the arrays is a prefix of the shape of the other. For example, you can multiply A3524 by M35, since the shape of the latter, 3 5, is a prefix of the shape of the former. In such cases, the array of lower dimension is extended to match the shape of the other array.

The actual rule is a bit more general: arguments to a dyadic verb agree if the frame of one is a prefix of the frame of the other. Where the verb has dyadic rank 0, e.g. the ordinary arithmetic verbs, then the cells have no size, and this rule then reduces to where the shape of one is a prefix of the shape of the other.

For example:

   $ A3542 * M35
3 5 4 2

Assembly

The next step of applying rank is to assemble the results. This is no problem if the result of the verb that is applied to each cell always has the same rank and shape. However, J can assemble items of different rank and shape as follows.

the items are first brought to a common rank by introducing leading unit axes to any of lower rank
the items are then brought to a common shape by padding with the appropriate fill element

For example:

   >1 2 3;2 2$10 11 12 13
 1  2 3
 0  0 0

10 11 0
12 13 0

Rank Operator

The rank operator " creates a new verb of given rank, and therefore can be used to enforce different argument pairings. Note that this does not change the rank of the verb to which it is applied.

For example, suppose we have verb v with rank r, and create a new verb w from v by specifying rank s:

  w=: v " s

Then w applies verb v to the s cells of its arguments. It is important to understand that when v is applied to each of these cells, it is applied with rank r, i.e. its own rank. Thus the rank conjunction enforces different argument pairings, but does not change the rank of the underlying verb.

Item Verbs

J defines many verbs, such as +/, to apply to the items (or _1 cells) of an array, which are the subarrays consisting of all axes but the first, for example the rows of a matrix.

Thus +/M23 is defined to be:

   0 1 2 + 3 4 5

Similarly, +/A234 is defined to be:

   0  1  2  3     12 13 14 15
   4  5  6  7  +  16 17 18 19
   8  9 10 11     20 21 22 23

It may be seen that by using rank with +/ lets you specify which are the items, and therefore, in effect, let you specify the axes on which to apply the verb. Thus:

   +/"2 A234
12 15 18 21
48 51 54 57

This is +/ applied to each rank-2 array, i.e. to each matrix, and therefore is the two sums:

   0 1 2 3 + 4 5 6 7 + 8 9 10 11
12 15 18 21

  12 13 14 15 + 16 17 18 19 + 20 21 22 23
48 51 54 57

Similarly:

   +/"1 A234
 6 22 38
54 70 86

Examples

1. Multiply each column of matrix M34 by vector V3:

   M34 * V3
 0  0  0  0
 4  5  6  7
16 18 20 22

2. Multiply each row of matrix M34 by vector V4:

3. Multiply each 3-by-4 block of array A342 by matrix M34:

4. Multiply each 3-by-4 block of array A234 by matrix M34:

   A234 *"2 M34
  0   1   4   9
 16  25  36  49
 64  81 100 121

  0  13  28  45
 64  85 108 133
160 189 220 253

In Examples 1 and 3, no rank was specified, therefore the multiplications are carried out with the rank assigned to *, which is 0. This means that the cells are the scalars, and the frames are the entire argument shapes.

Also, in Example 1, the frame of V3 is the first element of the frame of M34, while in Example 3, the frame of M34 is the first two elements of the frame of A342. In both cases, J extends the smaller array to match the larger, using prefix agreement.

In Example 2, the pairing is specified with rank 1. Thus the verb is applied to the rank 1 arrays, which are the rows of M34, and the vector V4 as a whole.

The three-step J process is thus:

1. Break arguments into 1-cells. The 1-cells of M34 are the rows:

  (0 1 2 3) (4 5 6 7) (8 9 10 11)

The 1-cell of V4 is the vector:

   0 1 2 3

2. The verb is then applied between the cell pairs:

   (0 1 2 3 * 0 1 2 3)  (4 5 6 7 * 0 1 2 3)  (8 9 10 11 * 0 1 2 3)

3. The individual results are then assembled into:

0 1  4  9
0 5 12 21
0 9 20 33

In Example 4 the pairing is specified with rank 2. Thus the verb is applied to the rank 2 arrays, which are the matrices of A234, and the matrix M34 as a whole. The three-step J process thus uses the 2-cells, which for A234 are the matrices:

   0 1  2  3    12 13 14 15
   4 5  6  7    16 17 18 19
   8 9 10 11    20 21 22 23

The 2-cell of M34 is the entire matrix:

   0 1  2  3
   4 5  6  7
   8 9 10 11

This cell is multiplied with the 2-cells of A234 and the results assembled as:

  0   1   4   9
 16  25  36  49
 64  81 100 121

  0  13  28  45
 64  85 108 133
160 189 220 253

Contributed by Chris Burke.