Help / JforC / Loopless Code IV: Irregular Operations
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers
16. Loopless Code IV: Irregular Operations
In our quest to write loopless code, we first learned about J's implicit looping, which we can use to replace loops in which the same function is performed on each cell; then we learned monad / which lets us accumulate an operation across all the items of a noun, and \ and \. which apply verbs to certain regular subsets of a noun. We now examine cases in which the operations on the cells are different, but where there is no sharing of information between cells.
A Few J Tricks
In these irregular cases, the J solution is to create an array that contains control information describing the difference between the cells, and then create a dyadic operation that produces the desired result when given a cell of control information and a cell of data. Writing code this way can seem ingeniously clever or awkwardly roundabout, depending on your point of view; we will simply accept it as a necessary part of coding in J, and we will learn to be effective with it. What follows is a hodgepodge of tricks to treat cells individually. If we were writing in C, we would use if statements, but since if by necessity involves a scalar comparison we will avoid it in J.
To add one to the elements of y whose values are even:
y + 0 = 2 | y
To double all the elements of y whose values are even:
y * 1 + 0 = 2 | y
To create an array whose even-numbered elements come from y and whose odd-numbered elements come from x :
(x * -.sv) + y * sv =. (#y) $ 1 0
which, homely as it is, is a standard idiom in J. This expression works only for numeric operands; for general operands we can select using a selection vector sv with
sv {"_1 x ,. y
To replace lowercase 'a' through 'f' with uppercase 'A' through 'F' in a string that contains only 'a' through 'f':
('abcdef' i. y) { 'ABCDEF'
Extending the previous example: to replace lowercase 'a' through 'f' with uppercase 'A' through 'F' leaving other characters unchanged:
(('abcdef' , a.) i. y) { 'ABCDEF' , a.
To understand this you need to know the special noun a. which is the character string containing all the ASCII characters in order. Work through a simple example until you understand how this works--it's a good example of how J thinking differs from C thinking.
A similar problem: given a list of keys y and a list of data z, with each item of y corresponding to an item of z; and another list of search keys x; and a default element d : return the item in z corresponding to the item of y that matches the item of x, or d if the item of x didn't match anything in y :
(y i. x) { z , d
To evaluate the polynomial defined by x, so that if for example x is 2 1 5 the result is 5y2+y+1:
+/ x * y ^ i. # x
(and now you can see why 0^0 is 1).
To evaluate the polynomial defined by x going the other direction, so that if for example x is 2 1 5 the result is 2y2+y+5:
y #. x
The last example, due to Roger Hui, has a power and economy that amount to sorcery. Suppose you had a list, and you wanted to know, for each item in the list, how many identical items appeared earlier in the list. You could find out this way:
y =. 2 2 2 1 2 1 4 6 4 2
t - (i.~ y) { t =. /: /: y
0 1 2 0 3 1 0 0 1 4
Take a little time--maybe a long time--to see how this works. The /: /: y is an idiom we discussed earlier--did you figure it out? It gives the ordinal of each item of y, in other words the rank of the item among the items of y . If there are equal items, they will occupy a block of successive ordinals. In this example you can see that t does indeed hold the ordinals:
t 2 3 4 0 5 1 7 9 8 6
(i.~ y) takes the index of each item of y within y itself, in other words, for each item, the index of the first item with the same value:
(i.~ y) 0 0 0 3 0 3 6 7 6 0
Since the identical items of y are a block of successive ordinals, and (i.~ y) comprises indexes of first items in blocks, we can find relative positions in blocks by subtracting the ordinal of the first item with a value from the ordinals of all the other items with the same value. That is what this expression does. Lovely!
We could use the hook to avoid creating the temporary variable t, by writing the line as
(i.~ y) (] - {) /: /: y
and we could even avoid naming y twice by writing
(i.~ (] - {) /:@/:) y
In addition to the foregoing ad hoc means of varying the operation cell-by-cell J has some language features expressly designed for that purpose:
Power/If/DoWhile Conjunction u^:n and u^:v
Applying u Repeatedly (Power)
u^:n y has infinite rank. It applies the verb u to y, then applies u to that result, and so on, for a total of n applications of u,
- in other words u u u...(n times) y,
>: 5 6 >:^:2 (5) 7 >:^:3 (5) 8
fndisplay gives a picture of what is happening:
defverbs 'incr"0' incr^:3 (5) +----------------+ |incr incr incr 5| +----------------+
x u^:n y also has infinite rank. It evaluates x u x u...(n times) y . A simpler way to say this is to say that it is equivalent to x&u^:n y, since x&u y is equivalent to x u y .
2 * 2 * 2 * 2 * 5 80 2 *^:4 (5) 80
u^:v y and x u^:v y are defined similarly: first v is evaluated (monadically or dyadically as appropriate), and then result is used as n . Formally, u^:v y is u^:(v y) y and x u^:v y is x u^:(x v y) y . With dyad u^:v, it will be rare that x and y both make sense as an operand into both u and v, and you will usually use @:[ and @:] to cause u or v to operate on only one operand. For example, to coalesce the x+1 leading axes of y into one axis, you could use x ,/@:]^:[ y :
1 ,/@:]^:[ i. 2 2 3 0 1 2 3 4 5 6 7 8 9 10 11 2 ,/@:]^:[ i. 2 2 3 0 1 2 3 4 5 6 7 8 9 10 11
This is hardly a commonplace usage, but let's analyze it, since conjunctions are still new to us. The verb is executed as if parenthesized ((,/)@:])^:[, so the first thing executed is u^:v where u is (,/)@:] and v is [ . x [ y is just x, so x is going to tell us how many times to apply x&((,/)@:]) . Now, x&((,/)@:]) y is just the same as ,/ y, because the purpose of the @:] is to ignore the left argument that was put on by x& . We remember monad ,/ from our discussion of monad u/ : it combines the 2 leading axes of y . So, x ,/@:]^:[ y will combine the 2 leading axes of y, x times; in other words, combine the x+1 leading axes of y .
Applying u Optionally (If)
The importance of u^:n is not in applying a verb several times--usually we could just write the instances out if we needed to--but rather in 4 special values of n : _1, 0, 1, and _ (infinity). u^:0, meaning apply u 0 times, is simple: it does nothing, with the result y in both dyadic and monadic forms. u^:1 means apply u once. Thinking about that, we see that if n is restricted to the values 0 or 1, ^:n means 'If n' : u^:n y is y, but modified by application of u if n is 1; in C terms, it is n ? u(y) : y . If we want to apply the verb u only on the items of y for which x is 1, we can write x u@:]^:["_1 y :
1 0 0 1 0 >:@]^:["_1 (1 2 3 4 5) 2 2 3 5 5
Applying u Forever (Converge)
When n is _, u^:_ means 'apply u repeatedly until the result stops changing'; in C, it resembles while(u(y)!=y)y = u(y); . You could use this to perform a numerical calculation that converges on a result; for example if you take ...cos(cos(cos(cos(y)))) until the result stops changing, you get the solution of the equation y=cos(y):
2 o.^:_ (0) 0.739085
You can think of u^:_ as applying an improvement u to y repeatedly until no further improvement is possible. The best-known example of this is Newton's Method for evaluating zeros of f(x): start with an initial guess y, and then replace the guess with y-(f(y)/f'(y)); repeat till there is no change in y. For example, to find the zeros of 3x3+2x2-10 (the derivative of which is 9x2+4x), we create a verb to apply the Newton's-Method step, and then execute it repeatedly with a well-chosen initial value:
3 : 'y - ((3*y^3)+(2*y^2)-10) % (9*y^2)+4*y' ^:_ (3) 1.30142
A robust implementation of Newton's Method must be able to find multiple roots and handle pathological functions, but a simple implementation such as the one above is an efficient way to polish up a root that has been approximated by other methods.
Applying u Iteratively (DoWhile)
The most important use of ^:_ is in the special form u^:v^:_ . Consider this form (either monad or dyad), with the understanding that v always produces a Boolean result of 0 or 1 . It is parenthesized (u^:v)^:_, i. e. u^:v repeated until its result is the same as its right operand. Now, if v evaluates to 0, the result of u^:v will certainly be the same as its right operand because u will not be executed; if v is 1, u^:v causes u to be executed once. So this construct is like C's while(v(y))y = u(y); (except that the J version also stops if the result of u y is the same as y, so the complete definition is while(v(y)&&(u(y)!=y))y = u(y); ). The great thing about having a verb to do this loop rather than a statement is that we can give the verb a rank and apply it to cells, with independent loop control on each cell:
2 *^:(100&>@:])^:_"0 (1 3 5 7 9 11) 128 192 160 112 144 176
Read this as 'for each atom of y, double it as long as the value is less than 100'.
u^:_1 is also of great interest but we will discuss it later.
One last point:
>:^:1 2 4 (5) 6 7 9
As you can see, n may be an array, in which case u^:n1 y is repeatedly evaluated, with n1 assuming the value of each atom of n, and the results are assembled using the shape of n as the frame and with framing fills added as needed. Pop quiz: express the preceding English sentence in J.
Solution: u^:n y is equivalent to n u@:]^:["0 _ y, and x u^:n y is equivalent to n x&u@:]^:["0 _ y . If you can make sense of the answer, you should be content with your progress. If you came up with either half on your own, you are entitled to claim Apprentice Guru status.
Tie and Agenda (switch)
The Tie Conjunction u`v u`n m`v m`n
The backquote character ` is the conjunction named Tie. ` is one of the few conjunctions that produce a noun, so it is neither monadic or dyadic. If an operand of ` is a verb, it is converted to its atomic representation which is a noun form from which the verb can be recovered; then the two operands m and n (both nouns now since any verb was converted to a noun) are joined by executing m,n . So, the result of ` applied between the members of a sequence of verbs is a list of special nouns, each of which is the atomic representation of a verb. We are not concerned with the format of the atomic representation, nor will we create or modify an atomic representation (that's Advanced-Guru work); we will be content to use the values produced by ` . An example is:
+`-`*`%`(+/) +-+-+-+-+-------+ |+|-|*|%|+-+---+| | | | | ||/|+-+|| | | | | || ||+||| | | | | || |+-+|| | | | | |+-+---+| +-+-+-+-+-------+
What makes the result of ` special is not the boxing, but the fact that what's in the boxes is not just any old data, but data in the format that can be used to recover the original verbs. Once created, the result of ` can be operated on like any other noun:
a =. +:`-`*`%`(+/)
3 { a
+-+
|%|
+-+
0 0 1 0 1 # a
+-+-------+
|*|+-+---+|
| ||/|+-+||
| || ||+|||
| || |+-+||
| |+-+---+|
+-+-------+
In English grammar, a gerund is a form of a verb that is used as a noun, for example the word cooking in Cooking is fun. The result of ` in J is also called a gerund, and we can see that the name is apt: a gerund in J is a set of J verbs put into a form that can be used as a J noun. It has the latent power of the verbs put into a portable form, like nitroglycerine that has been stabilized by kieselguhr to become dynamite. The blasting cap that sets it off is
The Agenda (switch) conjunction m@.v
m@.v (either monad or dyad) uses the result of v to select a verb from the list of verbs m, and then executes that verb.
m@.v requires that m be a valid gerund. It produces a verb which can be used monadically or dyadically and whose ranks are the ranks of v . The operation of this verb is as follows: v y (if monadic) or x v y (if dyadic) is evaluated; it must produce a scalar result r that is a valid index into m; i. e. (-#m) <: r and r < #m . Then, item r{m is selected--it is the atomic representation of one of the verbs that went into m--and that atomic representation is converted to a verb u . Finally, u y (if monadic) or x u y (if dyadic) is executed, and its result is the result of the execution of m@.v .
So, verb0`verb1`verb2 @. v y evaluates v y, resulting in r, and then executes verbr y . The dyadic case x verb0`verb1`verb2 @. v y evaluates x v y, resulting in r, and then executes x verbr y . The verbs may be any valid verb: a primitive, a compound verb, or a named verb.
Examples:
(1&+)`(-&2)@.(2&|) "0 i. 6 1 _1 3 1 5 3
This added 1 to each even number and subtracted 2 from each odd number. Note that we had to assign rank 0 to the overall combined verb, because otherwise the rank of (1&+)`(-&2)@.(2&|) would have been the rank of 2&| which is infinite because m&v has infinite rank.
_5 _3 _1 1 3 5 +`-@.(0&>@:["0) 2 _7 _5 _3 3 5 7
Subtract 2 from elements of x that are negative, add 2 to elements that are nonnegative. Here we assigned the rank to the selector verb in m@.v; that rank was then inherited by m@.v .
5 uname`+`] @. (*@:]"0) _5 0 5
(Remember that monad * is the signum function returning _1 for negative, 0 for zero, and 1 for positive operands) For each atom of y, execute 5 uname y if y is zero, 5 + y if y is positive, and pass y through unchanged (5 ] y) if y is negative. uname must be defined elsewhere. This expression makes use of negative indexing: if * y is negative, verb number _1 (the last item) is taken from the gerund.
m@.v obviously can be used with a small rank to afford great control over what operation is performed cell-by-cell, but if you do that it will have to apply J verbs on small operands, which is inefficient. After all we've been through, I feel confident that I can trust you not to use m@.v with small rank unless it's absolutely necessary.
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers