Most J programs contain no loops equivalent to while and for in C. J does contain while. and for. constructs, but they carry a performance penalty and are a wise choice only when the body of the loop is a time-consuming operation. You are just going to have to learn to learn to code without loops.
I think this is the most intimidating thing about learning J--more intimidating even than programs that look like a three-year-old with a particular fondness for periods and colons was set before the keyboard. You have developed a solid understanding of loops, and can hardly think of programming without using them. But J is a revolutionary language, and all that is solid melts into air: you will find that most of your loops disappear altogether, and the rest are replaced by small gestures to the interpreter indicating your intentions.
Come, let us see how it can be done. I promise, if you code in J for 6 months, you will no longer think in loops, and if you stay with it for 2 years, you will see that looping code was an artifact of early programming languages, ready to be displayed in museums along with vacuum tubes, delay lines, and punched cards. Remember, in the 1960s programmers laughed at the idea of programming without gotos!
You are not used to classifying loops according to their function, but I am going to do so as a way of introducting J's primitives. We will treat the subject of loopless iteration in 7 scattered chapters, showing how to replace different variants of loops:
Loops where each iteration of the loop performs the same operation on different data;
Loops that apply an operation between all the items of an array, for example finding the largest item;
Loops where the operation to be performed on each cell is different;
Loops that are applied to regularly-defined subsets of the data;
Loops that are applied to subsets of the data defined irregularly;
Loops that accumulate information between iterations of the loop;
Loops that implement finite-state machines.
The simplest case is the most important, and we start with a few experiments.
2 + 3 4 5
5 6 7
The verb dyad + is addition, and we have our first example of an implicit loop: the left argument 2 was added to each atom in the right argument.
1 2 3 + 4 5 6
5 7 9
And look! If each operand is a list, the respective items are added. We wonder if the behavior of 2 + 3 4 5 was because items of the shorter operand are repeated cyclically:
1 2 + 4 5 6
|length error
| 1 2 +4 5 6
Evidently not. A 'length error' means that the operands to + did not 'agree' (and you get an error if you try to add them). We will shortly understand exactly what this means.
i. 2 3
0 1 2
3 4 5
A reminder of what monad i. does.
0 100 + i. 2 3
0 1 2
103 104 105
Whoa! The atoms of the left operand were applied to rows of the right operand. Interesting. This seems to be some kind of nested implicit loop.
Let's learn a couple of more verbs, monad #. and monad #: . Monad #: creates the binary representation of an integer (i. e. a list of 0s and 1s), and monad #. is its inverse, creating the integer from the binary representation. For the longest time I couldn't remember which was which, but at last I saw the mnemonic: the verb with the single dot (#.) creates an atom from a list; the verb with multiple dots (#:) creates a list from an atom:
#: 5
1 0 1
#. 1 0 1
5
Yes, they seem to perform as advertised. They can be applied to arrays:
]a =. #: 5 9
0 1 0 1
1 0 0 1
Look: the result is not a rank-1 list, but rather a rank-2 array, where each item has the binary representation of one operand value (and notice, an extra leading zero was added to the representation of 5). The little trick with ]a =. will be explained later, but for now just think of ]a =. as 'assign to a and display the result'. With a assigned, we have:
#. a
5 9
This seems to be the desired result, but on reflection we are puzzled: how did the interpreter know to apply #. to each 1-cell rather than to each 0-cell? Contrast this result with the result of the verb monad +:, which means 'multiply by 2':
+: a
0 2 0 2
2 0 0 2
Evidently the verbs themselves have some attribute that affects the rank of cell they are applied to. It's time for us to stop experimenting and learn what that attribute is.
Every verb has a rank--the rank of the cells to which it is applied. If the rank of the verb's operand is smaller than the rank of the verb, the verb is applied to the entire operand and it is up to the author of the verb to ensure that it produces a meaningful result in that case.
Dyads have a rank for each operand, not necessarily the same.
A verb's rank can be infinite (_), in which case the verb is always applied to the operand in its entirety. In other words, if a verb has infinite rank for an operand, that operand is always processed as a single cell (having the rank of the operand).
If you don't know the rank of a verb, you don't know the verb. Using a verb of unknown rank is like wiring in a power-supply of unknown voltage--it will do something when you plug it in; it might even work; but if the voltage is wrong it will destroy what it's connected to. Avoid embarrassment! Know the rank of the verbs you use.
The definition page of each J verb gives the ranks of the verbs defined on the page, right at the top of the page after the name of the verb. Since most pages define both a monad and a dyad, you will usually find 3 numbers: the first is the rank of the monad, the other two are the left and right rank of the dyad. For example, click up the page for #: and you will see
#: _ 1 0
which means that monad #: has infinite rank, while dyad #: has left rank 1 and right rank 0. For any verb, including user-written verbs, you can ask the interpreter the rank by typing verbname b. 0 :
#: b. 0
_ 1 0
Verb Execution--How Rank Is Used (Monads)
The implicit looping in J results from the interplay of verb rank and noun rank. For monads, it goes like this:
1. Figure out the rank r of the cells that will be operated on; this will be the smaller of the rank of the verb and the rank of the operand. For the important case of a verb infinite rank, according to this rule r will be the rank of the operand, which is another way of saying that the verb applies to the operand in its entirety.
Find the frame f of the operand with respect to cells of rank r.
Think of the operand as an array with shape f made up of cells of rank r. Apply the verb to each r-cell, replacing each cell with the result of the verb. Obviously, this will yield an array of shape f whose items have the shape of the result of applying the verb to an r-cell.
Let's look at some simple examples:
i. 2 2
0 1
2 3
This will be the right operand.
+: i. 2 2
0 2
4 6
The steps to get this result are:
|
The verb rank is 0 and the noun rank is 2, so we will be applying the verb to 0-cells. The frame f is 2 2 |
|||||
|
Think of the operand as a 2x2 array of 0-cells: |
|
||||
|
The verb is applied to each cell: |
|
||||
|
Since each result is an atom, i. e. a 0-cell, the result is a 2x2 array of 0-cells, i. e. an array of shape 2 2 |
0 2 4 6 |
||||
|
Figure 1. Execution of +: i. 2 2 |
Another example:
]a =. 2 2 4 $ 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0
0 0 1 1
0 0 0 1
0 1 0 0
0 0 1 0
This is a rank-3 array.
#. a
3 1
4 2
|
The verb rank is 1 and the noun rank is 3, so we will be applying the verb to 1-cells. The frame f is 2 2 |
|||||
|
Think of the operand as a 2x2 array of 1-cells: |
|
||||
|
The verb is applied to each cell: |
|
||||
|
Since each result is an atom, i. e. a 0-cell, the result is a 2x2 array of 0-cells, i. e. an array of shape 2 2 |
3 1 4 2 |
||||
|
Figure 2. Execution of #. 2 2 4 $ 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 |
Controlling Verb Execution By Specifying a Rank
The implicit loops we have used so far are interesting, but they are not powerful enough for our mission of replacing all explicit loops. To understand the deficiency and its remedy, consider the new verb monad +/, which creates the total of the items of its operand (just think of it as 'monad SumItems'). Monad +/ has infinite rank: its rank is _ (infinity), which means, if you work through the description above, that it always works on its entire operand as a single cell. Its action is to take the total of the items, which are the _1-cells of the operand:
+/ 1 2 3
6
The result was 1 + 2 + 3, as expected.
i. 2 3
0 1 2
3 4 5
+/ i. 2 3
3 5 7
The result was 0 1 2 + 3 4 5, as expected (remember that the items are added, and the items of i. 2 3 are 1-cells). Adding together a pair of 1-cells adds the respective atoms, as we will soon learn in detail.
This application of monad +/ to a rank-2 array corresponds to the C code fragment:
for(j = 0;j<3;++j)sum[j] = 0;
for(i = 0;i<2;++i)
for(j = 0;j<3;++j)sum[j] += array[i][j];
Suppose we wanted to add up the items of each row, as in the C code fragment
for(i = 0;i<2;++i) {
sum[i] = 0;
for(j = 0;j<3;++j)sum[i] += array[i][j];
}
to produce the result 3 12? How can we do it in J? What we have learned so far is not enough, but if we had a way to make monad +/ apply to 1-cells--if we could make monad +/ have rank 1 rather than rank _--our problem would be solved: the implicit looping would cause each row to be summed and the results collected.
You will not be surprised to learn that J does indeed provide a way to apply monad +/ on 1-cells. That way is the rank conjunction " . (Remember that in J, " is not a paired quote character, but just a single primitive with a defined function).
We will learn all about conjunctions later on--the syntax is a little different than for verbs--but for now, we'll try to understand this " . It's used like this:
u"n
to produce a new verb that is u applied to n-cells individually. This is a simple idea, but its ramifications spread wide. As a first example:
+/"1 i. 2 3
3 12
This is what we were looking for. It happened this way:
|
The verb rank is 1 and the noun rank is 2, so we will be applying the verb to 1-cells. The frame f is 2 |
|||
|
Think of the operand as a list of 2 1-cells: |
|
||
|
The verb monad +/ is applied to each cell: |
|
||
|
Since each result is an atom, i. e. a 0-cell, the result is a list of 2 0-cells, i. e. an array of shape 2 |
3 12 |
||
|
Figure 3. Execution of +/"1 i. 2 3 |
Here are some more examples using a rank-3 array as data:
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
+/"1 i. 2 3 4
6 22 38
54 70 86
|
The verb rank is 1 and the noun rank is 3, so we will be applying the verb to 1-cells. The frame f is 2 3 |
|||||||
|
Think of the operand as a 2x3 array of 1-cells: |
|
||||||
|
The verb monad +/ is applied to each cell: |
|
||||||
|
Since each result is an atom, i. e. a 0-cell, the result is a 2x3 array of 0-cells, i. e. an array of shape 2 3 |
6 22 38 54 70 86 |
||||||
|
Figure 4. Execution of +/"1 i. 2 3 4 |
+/"2 i. 2 3 4
12 15 18 21
48 51 54 57
|
The verb rank is 2 and the noun rank is 3, so we will be applying the verb to 2-cells. The frame f is 2 |
|||
|
Think of the operand as a list of 2 2-cells: |
|
||
|
The verb monad +/ is applied to each cell. As we have learned, this sums the items, making each result a rank-1 list |
|
||
|
Since each result is a rank-1 list, i. e. a 1-cell, the result is a list of 2 1-cells, i. e. an array of shape 2 4 |
12 15 18 21 48 51 54 57 |
||
|
Figure 5. Execution of +/"2 i. 2 3 4 |
+/"3 i. 2 3 4
12 14 16 18
20 22 24 26
28 30 32 34
The verb is applied to the single 3-cell. Its items, which are 2-cells, are added, leaving a single 2-cell as the result.
How about i."0 (2 2 2)--can you figure out what that will produce? (Notice I put parentheses around the numeric list 2 2 2 so that the rank 0 wouldn't be treated as part of the list)
|
The verb rank is 0 and the noun rank is 1, so we will be applying the verb to 0-cells. The frame f is 3 |
||||
|
Think of the operand as a list of 3 0-cells (i. e. atoms): |
|
|||
|
The verb monad i. is applied to each cell: |
|
|||
|
Since each result is a list, i. e. a 1-cell, the result is a list of 3 1-cells each with shape 2, i. e. an array of shape 3 2 |
0 1 0 1 0 1 |
|||
|
Figure 6. Execution of i."0 (2 2 2) |
i."0 (2 2 2)
0 1
0 1
0 1
If you worked through that last example i."0 (2 2 2), it might have occurred to you that the shape of each result cell depended on the value of the operand cell, and that if those cells had not been identical, there would be some rough edges showing when it came time at the end to join the dissimilar result cells together. If so, full marks to you! That can indeed happen. If it does, then just before the cells are joined together to make the final result, the interpreter will bulk up the smaller results to bring them up to the shape of the largest. First, if the ranks of the results are not identical, each result will have leading axes of length 1 added as needed to bring all the results up to the same rank (e. g. if one result has shape 2 5 and another has shape 5, the second will be converted to shape 1 5, leaving the data unchanged). Then, if the lengths of the axes are not identical, the interpreter will extend each axis to the maximum length found at that axis in any result: this requires adding atoms, called fills, which are always 0 for numeric results and ' ' for literal results. Example:
i."0 (0 1 2 3)
0 0 0 NB. original result was empty list; 3 fills added
0 0 0 NB. original result was 0; 2 fills added
0 1 0 NB. original result was 0 1; 1 fill added
0 1 2 NB. this was the longest result, no fill added
fndisplay--A Utility for Understanding Evaluation
J contains a script that we will use to expose the workings of evaluation. You define verbs which, instead of operating on their operands, accumulate character strings indicating what operations were being performed. This gives you a way of seeing the operations at different cells rather than just the results.
Start by loading the script:
load 'system/packages/misc/fndisplay.ijs'
Then, select the type of display you want. We will be using
setfnform 'J'
Then, give the names of the verbs you want to use. If you want to assign a rank, you may do so by appending "r to the name:
defverbs 'SumItems plus"0'
Optionally, define any names you want to use as nouns. The value assigned to the noun is the noun's name:
defnouns 'x y'
You are free to use other nouns in expressions, but they will be replaced by their values.
With these definitions, you can explore J's evaluations:
x (plus) y
+--------+
|x plus y|
+--------+
The result of the evaluation is a description of the evaluation that was performed. The result is displayed in a box so that a sentence with multiple evaluations shows each in its proper place:
SumItems"1 i. 2 3
+--------------+--------------+
|SumItems 0 1 2|SumItems 3 4 5|
+--------------+--------------+
Here we see that SumItems was applied twice, once on each 1-cell.
fndisplay cannot produce a valid result in cases where the rank of a verb is smaller than the rank of the result-cells of the preceding verb, because then the operation would be performed on part of a result cell, and the result cell is just a descriptive string which cannot be meaningfully subdivided.
In this book, if we give an example that starts with defverbs it is implied that load fndisplay and setfnform 'J' have been executed.
If you prefer to see the order of evaluation expressed in functional form like that used in C, you may issue setfnform 'math' before you execute your sentences:
setfnform 'math'
1 plus 2 plus y
+-----------------+
|plus(1,plus(2,y))|
+-----------------+
Recall that we defined the _1-cell of a noun n to be the cells with rank one less than the rank of n, and similarly for other negative ranks. If a verb is defined with negative rank r, it means as usual that the verb will apply to r-cells if possible; but with r negative the rank of those r-cells will depend on the rank of the operand. After the interpreter decides what rank of cell the verb will be applied to, verbs with negative rank are processed just like verbs of positive rank.
+/ "_1 i. 3
0 1 2
The operand has rank 1, so the _1-cells are atoms. Applying monad SumItems on each one has no effect. The sentence is equivalent to +/ "0 i. 2 3 .
+/ "_1 i. 2 3
3 12
The operand has rank 2, so this expression totals the items in each 1-cell. The sentence is equivalent to +/ "1 i. 2 3 .
+/ "_2 i. 2 2 3
3 12
21 30
The operand has rank 3, so this totals the items in each 1-cell, leaving a 2x2 array of totals. The sentence is equivalent to +/ "1 i. 2 2 3 .
Rank Makes Verbs Automatically Extensible
We have been focusing so closely on shapes, cells, and frames that we haven't paid attention to one of the great benefits of assigning a rank to a verb: extensibility. When you give a verb the rank r, you only have to write the verb to perform correctly on cells of rank ≤r. Your verb will also automatically work on operands with rank >r: J will apply the verb on all the r-cells and collect the results using the frame.
If you write a verb to find the length of a vector, and give that verb the rank 1:
len =: verb : '%: +/ *: y' "1 NB. %: sqrt *: square
you can use it to take the length of a single vector:
len 3 4 5
7.07107
or two vectors:
len i. 4 3
2.23607 7.07107 12.2066 17.3781
or a 2x4 array of vectors:
len i. 2 4 3
2.23607 7.07107 12.2066 17.3781
22.561 27.7489 32.9393 38.1314
All is grist that comes to this mill!
Verb Execution--How Rank Is Used (Dyads)
We are at last ready to understand the implicit looping that is performed when J processes a dyadic verb. Because a dyadic verb has two ranks (one for each operand), and these two verb ranks interact with each other as well as with the ranks of the operands themselves, you should not read further until you thoroughly understand what we have covered already.
We have learned that the rank conjunction u"n is used to specify the rank of a verb. Since each verb has the potential of being invoked monadically or dyadically, the rank conjunction must specify the ranks for both valences. This requires 3 ranks, since the monad has a single rank and the dyad a left and a right rank. The ranks n may comprise from 1 to 3 items: if 3 ranks are given they are, in order, the monad's rank, the dyad's left rank, and the dyad's right rank. If two ranks are given, the first is the dyad's left rank and the second is used for the dyad's right rank and the rank of the monad. If there is only one item in the list, it is used for all ranks. So, v"0 1 has monad rank 1, dyad left rank 0, and dyad right rank 1 . As usual, J primitives themselves have the ranks shown in the Dictionary.
Processing of a dyad follows the same overall plan as for monads, except that with two operands there are two cell-sizes (call them lr and rr) and two frames (call them lf and rf). If the left and right frames are identical, the operation can be simply described: the lr-cells of the left operand match one-to-one with the rr-cells of the right operand; the dyad is applied to those matched pairs of cells, producing a result for each pair; those results are collected as an array with frame lf. We illustrate this case with an example:
(i. 2 2) + i. 2 2
0 2
4 6
|
The verb has left rank 0, and the left operand has rank 2, so the operation will be applied to 0-cells of the left operand. The verb has right rank 0, and the right operand has rank 2, so the operation will be applied to 0-cells of the right operand. The left frame is 2 2, the right frame is 2 2 . |
||