Fifty Shades of J/Chapter 04
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- , (ravel/append) ,.(stitch) ,: (laminate) ” (rank conjunction), ` (tie) @. (agenda) ;(raze) scalarisation, rectangularity, fill characters, bit to integer conversion, gerund.
Programming for Parallelism
By ’programming for parallelism’ I mean the process of, having worked something out for simple data, contriving that the relevant verbs also work on data with more complicated list structures, and thus carry out their actions on different sets of data in parallel. In the case of scalar verbs there is often nothing to do, thus 1 2 3 + 4 5 6 carries out additions in parallel, and 2 + 3 4 5 extends 2 to 2 2 2 prior to doing the parallel additions.
It is often desirable to upgrade more complicated verbs so that they behave like scalar verbs. There are several mechanisms available for achieving parallelism in J, and it helps to have clearly in mind the various levers which are available to be pulled. Some readers may relate to the experience of ‘going parallel’ by pulling hopefully at some of these levers, until eventually the desired result emerges (or in some cases, not!) If you have never had this heuristic experience, and always do the right thing first time, then stop reading at this point - J-ottings can be regarded as a confessional for imperfect J programmers!
The first mechanism for parallelism is rank control, one of the outstanding features of J. As an example, start with append which operates at a minimum rank of 1
NB. counter example? by david lambert. "minimum of rank 1" '' , '' 1 2,3 4 5 1 2 3 4 5
Provided that the appending is to take place at equal levels of the arguments, it does not matter what argument is given to the rank conjunction provided that it is a strictly positive integer
1 2,"(17)3 4 5 1 2 3 4 5 NB. counter example by david lambert "it does not matter what argument is given to the rank conjunction provided that it is a strictly positive integer" ,"_1~ i. 3 3 0 1 2 0 1 2 3 4 5 3 4 5 6 7 8 6 7 8
Rank control is about operating at different levels of the left and right arguments, for example ‘scalar to list’ or ‘scalar to list of lists’
1 2,"(0 1)3 4 5 NB. join scalars to list 1 3 4 5 2 3 4 5 1 2,"(1 0)3 4 5 NB. join list to scalars 1 2 3 1 2 4 1 2 5
Sometimes an operation cannot be performed without length equalisation using a fill character as in
4 5 6 7,"(1 2)i.2 2 NB. join list to list of lists 4 5 6 7 0 1 0 0 2 3 0 0 NB. rank conjunction is not required in this instance 4 5 6 7 , i. 2 2 4 5 6 7 0 1 0 0 2 3 0 0
Length equalisation and fill characters are provisions rather than controls, and are present because the language designers wisely judged that they are often greatly preferable to length errors.
Parallelism for append means creating an upgraded verb which
- joins several lists to the same list of scalars;
- joins the same list to several lists of scalars; and
- join matched pairs of lists and scalar lists.
This requires scalarisation, which is the second major control. It is tempting to equate scalarisation with box, but this is not quite accurate since link (;) also performs scalarisation. The results of scalarisation are non-simple scalars, which in general can only take part in structural operations such as appending, shifting, rotating and transposing, which do not involve looking at their content. Any operations on contents require an open, and, in the words of the help file, “opened atoms are brought to a common shape”. To put this in another way, open always forces rectangularity which is sometimes what is wanted, at other times not.
To return to the requirements for extended append, consider requirement (a). 1 2; 1 3 is a list of two boxed scalars which must be opened before the concatenation of each to a simple list such as 7 8 9 . Following the remarks in the previous paragraph, no concatenation can take place until the two boxed lists are opened, whereupon the result is ‘list joined to list’, that is append at rank 1
(>1 2;1 3),"(1)7 8 9 1 2 7 8 9 1 3 7 8 9
There is a snag, though, namely that if the two lists on the left are of unequal length the rectangularity rules will enforce an unwanted fill character between the first pair of joined lists
(>1 2;4 5 6),"(1)7 8 9 1 2 0 7 8 9 4 5 6 7 8 9
The following workaround
(1 2;4 5 6),every<7 8 9 1 2 7 8 9 0 4 5 6 7 8 9
still forces a fill character, and demonstrates further that explicit opens always expose the user to this possibility. If this is not acceptable then lists must be boxed by using under(&.) rather than compose
(1 2;4 5 6),each<7 8 9 ┌─────────┬───────────┐ │1 2 7 8 9│4 5 6 7 8 9│ └─────────┴───────────┘
This example underlines the fact that u&.v is more subtle than ‘do v, apply u, undo v’ (in this instance ‘open, append, box’), because if this were so, there would be an embedded fill character present in the result.
For requirement (b), suppose the list 1 2 has to be joined to the separate lists 4 5 and 7 8 9 . The foregoing discussion suggests
(<1 2),each 4 5;7 8 9 ┌───────┬─────────┐ │1 2 4 5│1 2 7 8 9│ └───────┴─────────┘
Finally requirement (c), which, perhaps surprisingly, turns out to be the simplest of the three because there is no need for scalar expansion to be invoked by an explicit box
(1 2;2 4 6),each 4 5;7 8 9 ┌───────┬───────────┐ │1 2 4 5│2 4 6 7 8 9│ └───────┴───────────┘
Using the verb je=.,each standing for ‘join each’ the three requirements (a), (b) and (c) are dealt with by
(1 2;4 5 6) je <7 8 9 (<1 2) je 4 5;7 8 9 (1 2;2 4 6) je 4 5;7 8 9
respectively, and the basic case, that is using je to join two unscalarised lists, is
1 2 (je&<) 3 4 5 ┌─────────┐ │1 2 3 4 5│ └─────────┘
Thus je can deal with all possible cases, but only if responsibility for boxing unboxed arguments falls on the user. It would be nice if this decision could be automated. The first of the verbs below tests whether an item is boxed, and the second uses a gerund to box it if it is unboxed, otherwise leaves it alone
unboxed=.-:> NB. 0=boxed, 1=unboxed unboxed=: 0 = L. NB. L. is the level of boxing box=.]`< @.unboxed NB. box if unboxed, else do nothing
so, given that all result lists are required to be boxed, the verb
JE=.(,each)&box NB. je having boxed any unboxed arguments
addresses the simple case and cases (a) to (c)
1 2 JE 3 4 5 NB. equivalent to append then box (1 2;4 5 6) JE 7 8 9 NB. cf. 1 2 + 3 1 2 JE 4 5;7 8 9 NB. cf. 1 + 2 3 (1 2;2 4 6) JE 4 5;7 8 9 NB. cf. 1 2 + 3 4
Other possible requirements can be addressed by combining JE with rank control. For example to join each scalar element in the right argument to a list as left argument
1 2 3 JE"(1 0) 4 5 ┌───────┬───────┐ │1 2 3 4│1 2 3 5│ └───────┴───────┘
boxes individual scalars in the right argument so that they behave as two one-item lists, which also happens in the case of multiple lists
1 2 JE"(0 1) 3;4 5 6;7 8 ┌───┬───────┬─────┐ │1 3│1 4 5 6│1 7 8│ ├───┼───────┼─────┤ │2 3│2 4 5 6│2 7 8│ └───┴───────┴─────┘
In the next two cases using ravel on the left gives lists of all possible joins, only in a different order
,(1 2;2 4 6)JE"(1 0) 4 5;7 8 9 ┌───────┬─────────┬─────────┬───────────┐ │1 2 4 5│2 4 6 4 5│1 2 7 8 9│2 4 6 7 8 9│ └───────┴─────────┴─────────┴───────────┘ ,(1 2;2 4 6)JE"(0 1) 4 5;7 8 9 ┌───────┬─────────┬─────────┬───────────┐ │1 2 4 5│1 2 7 8 9│2 4 6 4 5│2 4 6 7 8 9│ └───────┴─────────┴─────────┴───────────┘
The same principle can be applied to a verb such as btoi
btoi=.# i.@# NB. converts bits to integer list btoi&> 0 1;1 0 0 1 0 NB. accept fill characters 1 0 0 3 btoi each 0 1;1 0 0 1 0 NB. returns boxed lists ┌─┬───┐ │1│0 3│ └─┴───┘ NB. 0 1 2 3 0 1 2 3 4 5 6 btoi&> 0 0 0 1 ; 0 0 1 0 0 1 0 3 0 2 5 btoi each 0 0 0 1 ; 0 0 1 0 0 1 0 ┌─┬───┐ │3│2 5│ └─┴───┘ NB. I. at level _1 is a modern I.L:_1 ] 0 0 0 1 ; 0 0 1 0 0 1 0 ┌─┬───┐ │3│2 5│ └─┴───┘
With character strings it is natural to think in terms of suffixing and prefixing in the obvious literary sense. It is instructive to see why some plausible ideas for adding different inflections to the same verb root fail. First
(<'post') ,.'s';'ing';'ed' ┌────┬───┐ │post│s │ ├────┼───┤ │post│ing│ ├────┼───┤ │post│ed │ └────┴───┘
This goes part of the way but there appear to be fill characters present even in the absence of an explicit open. However, the ravel of the above expression
,(<'post') ,.'s';'ing';'ed' ┌────┬─┬────┬───┬────┬──┐ │post│s│post│ing│post│ed│ └────┴─┴────┴───┴────┴──┘
shows that the fill characters are purely for the necessities of display, but loses the division into three separate words. Replacing ravel with raze is even worse
;(<'post'),.'s';'ing';'ed' postspostingposted
An attempt to remove boxes preserves the words as entities but at the expense of introducing fill characters
;"1(<'post') ,"1 0 's';'ing';'ed' posts posting posted
But do not worry – help is at hand through JE
'post' JE 'ing'
┌───────┐
│posting│
└───────┘
'post' JE 's';'ing';'ed'
┌─────┬───────┬──────┐
│posts│posting│posted│
└─────┴───────┴──────┘
('post';'bow')JE 'ing'
┌───────┬──────┐
│posting│bowing│
└───────┴──────┘
('post';'bow')JE 's';'ing'
┌─────┬──────┐
│posts│bowing│
└─────┴──────┘
The third mechanism for parallelism is the join alternatives, namely stitch and laminate. stitch (which used to have the more descriptive name of ‘append items’) provides an alternative for rank control, but has more restrictions than with append due to the constraints of length compatibility
1 2,"(0)3 4 1 2,.3 4 1 3 1 3 2 4 2 4
laminate does its join by introducing a new 2-list which means that it is less easy to find simple direct alternatives to append. Also, unlike stitch, length equalisation and fill characters can be tolerated. Both of these points are illustrated in the example below
>1 2 ,&box 3 4 5 1 2 ,: 3 4 5 1 2 0 1 2 0 3 4 5 3 4 5
The verbs JES and JEL are identical to JE except that append has been replaced by stitch and laminate respectively. It is helpful to see the differences by comparing results side by side. Two informal observations are first, that the boxes now contain lists of lists rather than lists. In loose terminology, stitch adds things on the right, laminate adds them on the bottom
JES=.,.each&box JEL=.,:each&box 1 2 JES 3 4 1 2 JEL 3 4 ┌───┐ ┌───┐ │1 3│ │1 2│ │2 4│ │3 4│ └───┘ └───┘ 1 2 JES 3 4;5 6 1 2 JEL 3 4;5 6 ┌───┬───┐ ┌───┬───┐ │1 3│1 5│ │1 2│1 2│ │2 4│2 6│ │3 4│5 6│ └───┴───┘ └───┴───┘ (1 2;3 4)JES 5 6 (1 2;3 4)JEL 5 6 ┌───┬───┐ ┌───┬───┐ │1 5│3 5│ │1 2│3 4│ │2 6│4 6│ │5 6│5 6│ └───┴───┘ └───┴───┘ (1 2;3 4)JES 5 6;7 8 (1 2;3 4)JEL 5 6;7 8 ┌───┬───┐ ┌───┬───┐ │1 5│3 7│ │1 2│3 4│ │2 6│4 8│ │5 6│7 8│ └───┴───┘ └───┴───┘
In summary, JE uses scalarisation via box and open to achieve fundamental parallelism such as available in primitive scalar verbs. By adding rank control and introducing the variants JES and JEL an even greater variety of parallelism opportunities is possible.
Code Summary
je=.,each NB. join each JE=.(,each)&box NB. append each JES=.,.each&box NB. stitch each JEL=.,:each&box NB. laminate each btoi=.# i.@# NB. converts bits to integer list unboxed=.-:> NB. 0=boxed, 1=unboxed box=.]`< @.unboxed NB. box if unboxed, else do nothing