Ch 7: Ranks

| # Chapter 7: Ranks Recall that the rank of an array is its number of dimensions. A scalar is of rank 0, a list of numbers is of rank 1, a table of rank 2, and so on. The subject of this chapter is how the ranks of arguments are taken into account when verbs are applied. ## 7.1 The Rank Conjunction First, some terminology. An array can be regarded as being divided into "cells" in several different ways. Thus, a table such as
       M =: 2 3 $ 'abcdef'
       M
    abc
    def
may be regarded as being divided into 6 cells each of rank 0, or divided into 2 cells each of rank 1, or as being a single cell of rank 2. A cell of rank `k` will be called a `k`-cell. ### 7.1.1 Monadic Verbs The box verb (monadic `<`) applies just once to the whole of the argument, to yield a single box, whatever the rank of the argument.
`L =: 2 3 4` | `< L` | `M` | `< M`
    2 3 4
    +-----+
    |2 3 4|
    +-----+
    abc
    def
    +---+
    |abc|
    |def|
    +---+
However, we may choose to box each cell separately. There is a conjunction `"` (double-quote, called "Rank"), we write `(< " 0)` to box each scalar, that is, each 0-cell.
`M` | `< " 0 M` | `< " 1 M` | `< " 2 M`
    abc
    def
    +-+-+-+
    |a|b|c|
    +-+-+-+
    |d|e|f|
    +-+-+-+
    +---+---+
    |abc|def|
    +---+---+
    +---+
    |abc|
    |def|
    +---+
The general scheme is that in the expression `(u " k y)`, the monadic verb `u` is applied separately to each `k`-cell of `y`. We can define a verb to exhibit the k-cells of an array, each cell in its own box::
       cells  =: 4 : '< " x. y.'
`M` | `0 cells M` | `1 cells M`
    abc
    def
    +-+-+-+
    |a|b|c|
    +-+-+-+
    |d|e|f|
    +-+-+-+
    +---+---+
    |abc|def|
    +---+---+
### 7.1.2 Dyadic Verbs Given a table, how do we multiply each row by a separate number? We multiply with the verb `(* " 1 0)` which can be understood as "multiply 1-cells by 0-cells", For example,
`x =: 2 2 $ 0 1 2 3` | `y =: 2 3` | `x (* " 1 0) y`
    0 1
    2 3
    2 3
    0 2
    6 9
The general scheme is that the expression
                x (u " (L,R)) y
means: apply dyad `u` separately to each pair consisting of an L-cell from `x` and the corresponding R-cell from `y`. To multiply each column by a separate number, we combine each 1-cell of `x` with the solitary 1-cell of `y`
`x` | `y` | `x (* " 1 1) y`
    0 1
    2 3
    2 3
    0 3
    4 9
## 7.2 Intrinsic Ranks In J, every verb has what might be called a natural, or intrinsic, rank for its argument(s). Here are some examples to illustrate. For the first example, consider:
`*: 2` | `*: 2 3 4`
    4
    4 9 16
Here, the arithmetic function "square" naturally applies to a single number(a 0-cell). When a rank-1 array (a list) is supplied as argument, the function is applied separately to each 0-cell of the argument. In other words, the natural rank of (monadic) `*:` is 0. For another example, there is a built-in verb `#.` (hash dot called "Base Two"). Its argument is a bit-string (a list) representing a number in binary notation, and it computes the value of that number. For example, `1 0 1` in binary is `5`
       #. 1 0 1
    5
The verb `#.` applies naturally to a list of bits, that is, to a 1-cell. When a rank-2 array (a table) is supplied as argument, the verb is applied separately to each 1-cell, that is, to each row of the table.
`t =: 3 3 $ 1 0 1 0 0 1 0 1 1` | `#. t`
    1 0 1
    0 0 1
    0 1 1
    5 1 3
Thus the natural rank of monadic `#.` is `1`. For a third example, as we have already seen, the monadic case of `<` applies just once to the whole of its argument, whatever the rank of its argument. The natural rank of `<` is thus an indefinitely large number, that is, infinity, denoted by _ . These examples showed monadic verbs. In the same way every dyadic verb will have two natural ranks, one for each argument. For example, the natural ranks of dyadic `+` are `0 0` since `+` takes a number (rank-0) on left and right. In general, a verb has both a monadic and a dyadic case, and hence altogether 3 ranks, called its "intrinsic ranks". The intrinsic ranks of a verb are shown with the aid of a built-in adverb `b.` (lowercase b dot, called "Basic Characteristics"). For any verb `u`, the expression `u b. 0` gives the ranks in the order monadic, left, right.
`*: b. 0` | `#. b. 0` | `< b. 0`
    0 0 0
    1 1 1
    _ 0 0
For convenience, the rank conjunction `"` can accept a right argument consisting of a single rank (for a monad) or two ranks (for a dyad) or three ranks (for an ambivalent verb). One rank or two are automatically expanded to three as shown by:
`(<"1) b. 0` | `(<"1 2) b. 0` | `(<"1 2 3) b. 0`
    1 1 1
    2 1 2
    1 2 3
## 7.3 Frames Suppose `u` is to be a verb which sums all the numbers in a table, by summing the columns and then summing the column-sums. We specify that `u` is to have monadic rank 2.
       u =: (+/) @: (+/) " 2
`w =: 4 5 $ 1` | `u w` | `u b. 0`
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    20
    2 2 2
Suppose a four-dimensional array `A` has shape `2 3 4 5`.
       A =: 2 3 4 5 $  1
We can regard `A` as a 2-by-3 array of 2-cells, each cell being 4-by-5. Now consider computing `(u A)`. The verb `u`, being of rank 2, applies separately to each 2-cell, giving us a 2-by-3 array of results. Each result is a scalar (because `u` produces scalars), and hence the overall result will be 2 by 3 scalars.
`u A` | `$ u A`
    20 20 20
    20 20 20
    2 3
The shape `2 3` is called the "frame" of `A` with respect to its 2-cells, or its 2-frame for short. The k-frame of `A` is given by dropping the last `k` dimensions from the shape of `A`, or equivalently, as the shape of the array of k-cells of `A`.
       frame =: 4 : '$ x. cells y.'
`$ A` | `2 frame A`
    2 3 4 5
    2 3
In general, suppose that verb `u` has rank `k`, and from each k-cell it computes a cell of shape `s`. (The same `s`, we are supposing, for each cell). Then the shape of the overall result `(u A)`is: the k-frame of `A` followed by the shape `s`. To demonstrate that this is the case, we can find `k` from `u`, as the first (monadic) rank of `u`:
       k =: 0 { u b. 0
We can find the shape `s` by applying `u` to a typical k-cell of `A`, say the first.
       s =: $ u  0 { > (, k cells A)
In this example, the shape `s` is an empty list, because `u` produces scalars.
`k` | `s` | `kfr =: k frame A` | `kfr, s` | `$ u A`
    2
    2 3
    2 3
    2 3
Here we supposed that verb `u` gives the same-shaped result for each cell in its argument. This is not necessarily the case - see the section on "Reassembly of Results" below. ### 7.3.1 Agreement A dyad has two intrinsic ranks, one for the left argument, one for the right. Suppose these ranks are `L` and `R` for a verb `u`. When `u` is applied to arguments `x` and `y`, `u` is applied separately to each pair consisting of an L-cell from `x` and the corresponding R-cell from `y`. For example, suppose dyad `u` has ranks `(0 1)`. It combines a 0-cell from `x` and a 1-cell from `y`.
       u =: < @ ,  " 0 1
       x =: 2  $ 'ab'
       y =: 2 3 $ 'ABCDEF'
`x` | `y` | `x u y`
    ab
    ABC
    DEF
    +----+----+
    |aABC|bDEF|
    +----+----+
Notice that here the 0-frame of `x` is the same as the 1-frame of `y`. These two frames are said to agree.
`x` | `y` | `$x` | `$y` | `0 frame x` | `1 frame y`
    ab
    ABC
    DEF
    2
    2 3
    2
    2
What if these two frames are not the same? They can still agree if one is a prefix of the other. That is, if one frame is the vector `f`, and the other frame can be written as `(f,g)` for some vector `g`. Here is an example. With
       x =: 2 3 2 $ i. 12
       y =: 2     $ 0 1
and a dyad such as `+`, with ranks `(0 0)`, we are interested in the 0-frame of `x` and the 0-frame of `y`.
`x` | `y` | `0 frame x` | `0 frame y` | `x+y`
     0  1
     2  3
     4  5

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

     7  8
     9 10
    11 12
We see that the two frames are `2` and `2 3 2` and their difference `g` is therefore `3 2`. Here `y` has the shorter frame. Then each cell of `y` corresponds to, not just a single cell of `x`, but rather a `3 2`-shaped array of cells. In such a case, a cell of `y` is automatically replicated to form a `3 2`-shaped array of identical cells. In effect the shorter frame is made up to length, so as to agree with the longer. Here is an example. The expression `(3 2 & $) " 0 y` means " a 3 by 2 replication of each 0-cell of `y`".
`x` | `y` | `yyy =: (3 2&$)"0 y` | `x + yyy` | `x + y`
     0  1
     2  3
     4  5

     6  7
     8  9
    10 11
    0 1
    0 0
    0 0
    0 0

    1 1
    1 1
    1 1
     0  1
     2  3
     4  5

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

     7  8
     9 10
    11 12
What we have seen is the way in which a low-rank argument is automatically replicated to agree with a high-rank argument, which is possible provided one frame is a prefix of the other. Otherwise there will be a length error. The frames in question are determined by the intrinsic dyadic ranks of the verb. The general scheme for automatically replicating one argument is: for arguments `x` and `y`, if `u` is a dyad with ranks `L` and `R`, and the L-frame of x is `f,g` and the R-frame of `y` is `f` (supposing `y` to have the shorter frame) then `(x u y)` is computed as `(x u (g& $)"R y)` ## 7.4 Reassembly of Results We now look briefly at how the results of the computations on the separate cells are reassembled into the overall result. Suppose that the frame of application of a verb to its argument(s) is `f`, say. Then we can visualise each individual result as being stuffed into its place in the `f`-shaped framework of results. If each individual result-cell has the same shape, `s` say, then the shape of the overall result will be `(f,s)`. However, it is not necessarily the case that all the individual results are the same shape. For example, consider the following verb `R`, which takes a scalar `y` and produces a rank-`y` result.
       R =: (3 : '(y. $ y.) $ y.') " 0
`R 1` | `R 2`
    1
    2 2
    2 2
When `R` is applied to an array, the overall result may be explained by envisaging each separate result being stufffed into its appropriate box in an `f`-shaped array of boxes. Then everything is unboxed all together. Note that it is the unboxing which supplies padding and extra dimensions if necessary to bring all cells to the same shape.
`(R 1); (R 2)` | `> (R 1) ; (R 2)` | `R 1 2`
    +-+---+
    |1|2 2|
    | |2 2|
    +-+---+
    1 0
    0 0

    2 2
    2 2
    1 0
    0 0

    2 2
    2 2
Consequently the shape of the overall result is given by `(f, m`) where `m` is the shape of the largest of the individual results. ## 7.5 More on the Rank Conjunction ### 7.5.1 Relative Cell Rank The rank conjunction will accept a negative number for a rank. Thus the expression `(u " _1 y)` means that u is to be applied to cells of rank 1 less than the rank of `y`, that is, to the items of `y`.
`x` | `$x` | `< " _1 x` | `< " _2 x`
     0  1
     2  3
     4  5

     6  7
     8  9
    10 11
    2 3 2
    +---+-----+
    |0 1| 6  7|
    |2 3| 8  9|
    |4 5|10 11|
    +---+-----+
    +---+---+-----+
    |0 1|2 3|4 5  |
    +---+---+-----+
    |6 7|8 9|10 11|
    +---+---+-----+
### 7.5.2 User-Defined Verbs The rank conjunction `"` has a special significance for user-defined verbs. The significance is that it allows us to define a verb considering only its "natural" rank: we ignore the possibility that it may be applied to higher-rank arguments. In other words, we can write a definition assuming the verb will be applied only to arguments of the natural rank. Afterwards, we can then put the finishing touch to our definition with the rank conjunction. Here are two examples. The factorial of a number `n` is the product of the numbers from `1` to `n`. Hence (disregarding for the moment J's built-in verb `!`) we could define factorial straightforwardly as
          f =: */ @: >: @: i.
because `i. n` gives the numbers `0 1 ... (n-1)`, and `>: i. n` gives `1 2 ... n`. We see:
`f 2` | `f 3` | `f 4` | `f 5`
    2
    6
    24
    120
Will `f` work as expected with a vector argument?
       f 2 3
    4 10 18
Evidently not. The reason is that `(f 2 3)` begins by computing `(i. 2 3)`, and `(i. 2 3)` does NOT mean `(i. 2)` followed by `(i. 3)`. The remedy is to specify that `f` applies separately to each scalar (rank-0 cell) in its argument:
       f  =: (*/ @: (>: @: i.)) " 0

       f 2 3 4 5
    2 6 24 120
For a second example of the significance of the rank-conjunction we look at explicitly defined verbs. The point being made here is, to repeat, that it is useful to be able to write a definition on the assumption that the argument is a certain rank say, a scalar, and only later deal with extending to arguments of any rank. Note that for any explicit verb, its intrinsic ranks are always assumed to be infinite. This is because the J system does not look at the definition until the verb is executed. Since the rank is infinite, the whole argument of an explicit verb is always treated as a single cell (or pair of cells for a dyad) and there is no automatic extension to deal with multiple cells. For example, the absolute value of a number can be computed by the verb:
       abs =: 3 : 'if. y. < 0 do. - y. else. y. end.'
`abs 3` | `abs _3`
    3
    3
Since `abs` is explicitly defined, we see that its monadic (first) rank is infinite:
       abs b. 0
    _ _ _
This means that if `abs` is applied to an array `y`, of any rank, it will be applied just once, and we can see from the definition that the result will be `y` or `-y`. There are no other possibilities. It is indeed the case that if `y` is a vector then `(y. < 0)` yields a vector result, but the expression `(if. y. < 0)` makes ONE decision. (This decision will in fact be based, not on the whole of `y > 0` but only on its leading item. See Chapter 12 for more details). Hence if the argument contains both positives and negatives, this decision must be wrong for some parts of the argument.
       abs 3 _3
    3 _3
Hence with `abs` defined as above, it is important to say that it applies separately to each scalar in its argument. Thus a better definition for `abs` would be:
       abs =:(3 : 'if. y. < 0 do. -y. else. y. end.')"0

       abs 3 _3
    3 3
This brings us to the end of Chapter 7.

NEXT
Table of Contents
Index

Copyright © Roger Stokes 2004. This material may be freely reproduced, provided that this copyright notice is also reproduced.

last updated 6 Nov 2004