# Essays/Rank

## Contents

## 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`:

M34 *"1 V4 0 1 4 9 0 5 12 21 0 9 20 33

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

A342 * M34 0 0 2 3 8 10 18 21 32 36 50 55 72 78 98 105 128 136 162 171 200 210 242 253

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.