Vocabulary/Loopless
Loopless Programming
Looping - performing a computation repeatedly - is what programs do. In most computer languages, all loops are expressed by one of two statements:
- Do While - repeat a code block until a condition is met
- For - repeat a code block, with a loop index indicating how many times the block has been repeated.
Many modern languages have iterators, which slightly streamline the For loop, but without addressing its fundamental deficiencies.
Programmers trained on scalar languages have spent many years internalizing the Do-While and For paradigms. Discarding these paradigms is the biggest re-think they need to make when they learn J.
But re-think they must. J's approach to iteration is vastly better than other languages'. Consider this example problem: add each number in a list x to each number in the corresponding row of a two-dimensional array y. A J programmer would write
x + y
A C programmer would write
for(i = 0;i<sizeof(x)/sizeof(x[0]);++i)
for(j = 0;j<sizeof(y)/sizeof(y[0]);++j)
z = x[i] + y[i][j];
}
}
Why is J's way better?
- Shorter is easier to understand, once you know the language.
- (x + y) is an expression rather than a statement. The J programmer can embed (x + y) in a larger expression, perhaps a matrix multiplication (w +/ . * (x + y)) which adds the equivalent of three more nested loops, but is still a single expression. Expressions can be combined; statements cannot.
- The C code requires the programmer to get down to the level of individual array elements. A J programmer thinks in terms of entire arrays, combining them using array-savvy primitives.
To think like a J programmer, you need to know the following tricks behind loopless programming.
Types Of Loops
Why is J so effective? Because almost all the loops you ever need fall into one of a few categories.
J has modifiers for each category. By connecting different modifiers together, you can create almost any looping structure you need.
J Primitives For Looping Category What You Want To Do How To Do It Searching See whether a value appears in a list of values Use Element Of (x e. y) See exactly where a value appears in a list of values Use Index Of (x i. y) See where a value fits in a sorted list of values Use Interval Index (x I. y) Operate on regular subarrays Apply a verb on each cell, where the cell has the same rank as the verb Just use the verb. The looping is done automatically. Apply a verb on cells of a given rank r Use verb"r (See rank conjunction). Apply a verb with two arguments, controlling how the argument cells match up Use verb"r, perhaps multiple times (See rank conjunction and agreement). Apply a verb on other-than-trailing axes, where the units to be operated on are not cells Apply Rearrange Axes (x |: y) to make the desired units cells, then apply your verb. Operate on a single subarray Extract a single subarray of a noun and operate on it Use Subarray (x u;.0 y) Apply a verb on a single subarray of a noun, in place Use Subarray operate on the subarray, then update the original array: y =. (x u;.0 y) m} y Accumulation: operate on each item sequentially, rolling the output from one item to be an input to the next item Apply a verb between items of an array, producing a summary value for the array.
Examples: add up the items; find the largest item; perform set-intersection of the items
Use Insert (u/ y) Apply a verb between each item of an array and the result from application to previous items, remembering the result at each stage.
Examples: create a running total; keep track of the largest value found up to each position.
Use Suffix (u/\. y) or, if you know what you're doing, Prefix (u/\ y) Split an array into subarrays of sequential items and operate on each Apply a verb on each consecutive set of x items of y.
Sets may be overlapping or not
Use Infix (x u\ y) or Subarrays (x u;.3 y) Apply a verb on sets of consecutive items of y
where each set starts/ends at a specific value of the item
Use SelfIntervals (u;.1 y etc.) Apply a verb on sets of consecutive items of y
where the starting/ending point of each set is suppliedUse Intervals (x u;.1 y etc.) Split an array into subarrays of scattered items and operate on each Apply a verb on scattered sets of items of y Use Key (x u/. y) Apply a verb repeatedly A fixed number of times Use Power ([x] u^:n y) A calculated number of times Use Dynamic Power ([x] u^:v y) Optionally, cell by cell (If) Use Power ([x] u^:v"r y) Until a condition is met (DoWhile) Use Power ([x] u^:v^:_ y) On boxed structures Apply a verb inside a boxed structure Use ([x] u&.> y) if the boxing level is 1, otherwise Level At ([x] u L:n y) Apply a verb inside a boxed structure, but assemble the results unboxed Use ([x] u&> y) if the boxing level is 1, otherwise Spread ([x] u S:n y) Ordering Sort Items Use Sort (/:~ y) (ascending) or (\:~ y) (descending) Sort Items on their associated keys Use Sort Using (x /: y) (ascending) or (x \: y) (descending). y contains one key for each item of x.
Example: (x \: {:"1 x) creates an array containing the items of x sorted on the last column in descending order.Calculate grading permutation Use Grade Up (/: y) or Grade Down (\: y) Discard duplicate items Use Nub (~. y) and Nub Sieve (~: y) Self-Classify (calculate equivalence classes) For each item of y, give the index in y of the first matching item Use i.~ (i.~ y)
Boolean Lists
Behind many loops is the idea of testing each item of an array z and then taking some action, or not, depending on whether the test passed or not.
You might:
- count the values that pass the test
- add up all the values that pass the test
- delete all the values that don't pass the test
- create a series of totals, resetting the total at each item that passes the test
In J we do this by creating a Boolean list, one value (0 or 1) per item of z
Instead of individually testing each item of the array, we do all the tests at once, getting the results back as a single Boolean list. Then we compute what we're looking for.
Create this Boolean list by applying a logic primitive (verb) to the target array: z . Most primitive verbs are array-savvy, so this automatically applies the verb to each item of z .
z =. 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 z > 5 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1
An important fact about a Boolean list is that the Boolean values are ordinary numbers 0 or 1. You can do arithmetic with them.
Examples
1. How many numbers are greater than 5?
+/ z>5 6
+/y adds up the numbers in y - the number of 1s in the Boolean: z>5 .
2. What is the smallest number greater than 5?
Get a list of numbers greater than 5, then extract the smallest of that list.
No need to find the indexes of the numbers greater than 5. Just use a Boolean list to select (#) the numbers from z
<./ (z > 5) # z 6 (z > 5) # z NB. (These are the numbers greater than 5 in z) 9 6 8 9 7 9
3. What is the average value of the numbers that come after a 5?
Get a Boolean list of the position of each 5, shift this list right one position so it points to the numbers after each 5; select those numbers; find their average.
] after5 =. (|.!.0 list = 5) # list NB. the numbers after each 5 9 3 8 (+/ after5) % # after5 6.66667
4. How many occurrences of the letter 'e' are not followed by another 'e'?
Use methods similar to the previous problem; or you could combine two Boolean lists: get a list telling where there is an 'e', and another telling where there is 'ee', and combine them:
word =. 'eleemosynary'
'e' = word NB. locations of 'e'
1 0 1 1 0 0 0 0 0 0 0 0
'ee' E. word NB. locations of 'ee'
0 0 1 0 0 0 0 0 0 0 0 0
('e' = word) > ('ee' E. word) NB. 'e' but not 'ee'
1 0 0 1 0 0 0 0 0 0 0 0
+/ ('e' = word) > ('ee' E. word) NB. how many of them?
2