J-ottings 40: Parallel Joins
Vector 20:4, page 32
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 32
J programming for data parallelism (as opposed to processor parallelism) might well be recognised in other languages as a design pattern. To put this in another way, upgrading verbs developed for simple data so that they also work parallel-wise on data with more complicated list structures is a generic problem. In the case of scalar verbs there is often nothing to do, for example 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 three mechanisms available for achieving such parallelism in J, explicit acknowledgement of which may help avert the untidiness of experimenting more or less at random, until eventually the desired result emerges (or in some cases, not!). Those who have never had this heuristic experience in J are probably highly skilled programmers who have no need to read any further!
The first mechanism for parallelism is rank control. Start with append as an example, which has a minimum operating rank of 1:
Provided that the appending is to take place at equal rank levels of the arguments, it does not matter what argument is given to an explicit rank conjunction provided that it is a strictly positive integer:
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 a list
1 3 4 5
2 3 4 5
1 2,"(1 0)3 4 5 NB. join a 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
Length equalisation and fill characters are provisions rather than controls, and are present because the language designers wisely judged that they are greatly preferable to length errors.
Parallelism for joining requires adjusting append so that the upgraded version automatically
(a) joins several lists to the same list of scalars;
(b) joins the same list to several lists of scalars; and
(c) joins matched pairs of boxed lists.
Achieving 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 cannot take part in, for example, basic arithmetic operations, even although their contents can. Thus 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. The only operations in which non-simple scalars can take part in are structural ones such as joining, shifting, rotating and transposing.
To return to the requirements above, consider (a). 1 2;1 3 is a list of two boxed non-simple scalars which must be opened before each is joined to a simple list such as 7 8 9. Following the remarks in the previous paragraph, no joining can take place until the two boxed lists are opened, whereupon the result is ‘list joined to list’, that is append at rank 1:
There is a snag, though, namely that if the two lists on the left are of unequal length the rectangularity rules will enforce an irrelevant fill character sitting astride the join:
The fill character can be pushed to the right by scalarising the right hand side, and bonding the append with open:
The success of the above ‘append each’ operation depends on scalar expansion of the right argument, following which the compound verb ,&> behaves like a scalar verb such as + or * only with a fill character. If the latter is not acceptable then use compose (&.) rather than bond and work with boxed lists:
(1 2;4 5 6),&.><7 8 9 NB. join each of two lists to a list
+---------+-----------+
|1 2 7 8 9|4 5 6 7 8 9|
+---------+-----------+
This underlines the fact that u&.v (compose) 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 leads to
(<1 2),&.>4 5;7 8 9 NB.join one list to each of two lists
+-------+---------+
|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),&.>4 5;7 8 9 NB. two lists joined pair-wise
+-------+-----------+
|1 2 4 5|2 4 6 7 8 9|
+-------+-----------+
So to start the quest for a parallel joining verb, define
so that the three requirements (a), (b) and (c) are dealt with by
(1 2;4 5 6) je<7 8 9 NB. join many to one
(<1 2) je 4 5;7 8 9 NB. join one to many
(1 2;2 4 6) je 4 5;7 8 9 NB. join lists pair-wise
respectively, and the basic case, that is using je to append and box two unscalarised lists, is:
Thus je can deal with all possible cases, but only if the responsibility for boxing unboxed arguments is borne by the user. To automate this decision use:
so given
cases (a) to (c) and the simple case are given by
1 2 JE 3 4 5 NB. two lists, append and 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
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 try stitching:
(<'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 exigencies of display, although the division into three separate words has been lost. Replacing ravel with raze is even worse:
Using rank control removes boxes and preserves the words as entities but at the expense of introducing genuine fill characters:
But do not worry – help is at hand through JE:
'post' JE 'ing'
+-------+
|posting|
+-------+
'post' JE 's';'ing';'ed'
+-----+-------+------+
|posts|posting|posted|
+-----+-------+------+
('post';'eat';'flower')JE 'ing'
+-------+------+---------+
|posting|eating|flowering|
+-------+------+---------+
What happens if JE is applied with explicit rank control? First, qualification with zero rank, that is JE"(0), makes no difference since the items in the left and right arguments are treated either as scalars or as lists of scalars anyway.
The interesting cases are therefore:
,(1 2;2 4 6)JE"(1 0) 4 5;7 8 9 NB. all join combinations
+-------+---------+---------+-----------+
|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 NB. all join combinations
+-------+---------+---------+-----------+
|1 2 4 5|1 2 7 8 9|2 4 6 4 5|2 4 6 7 8 9|
+-------+---------+---------+-----------+
which, using a ravel on the left in both cases, give lists of all possible joins, but in different orders.
Also the effect of
,1 2 JE"(0 1) 4 5;7 8 9 NB. all join combinations
+-----+-------+-----+-------+
|1 4 5|1 7 8 9|2 4 5|2 7 8 9|
+-----+-------+-----+-------+
is to scalarise the individual items of the left argument which now behave as two one-item lists.
The third mechanism for parallelism is that of 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 due to constraints of length compatability.
Laminate joins 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, as illustrated in the example below:
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 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.
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 6 7;8 9 (1 2;3 4)JEL 6 7;8 9
+---+---+ +---+---+
|1 6|3 8| |1 2|3 4|
|2 7|4 9| |5 6|7 8|
+---+---+ +---+---+
In summary, rank control, scalarisation and stitch/laminate are means of attaining parallel joins, and in combination give a considerable range of possibilities. Of course the value of such techniques is in the interesting things which can be done with them – but that must wait until later!