Fifty Shades of J/Chapter 18

From J Wiki
Jump to: navigation, search

Table of Contents ... Glossary ... Previous Chapter ... Next Chapter

The problem with J is …

Principal Topics

] (right) /. (infix) \. (suffix) /: (grade up) ` (gerund) list constructor, statement separator, zigzag matrix.

The problem with J is…

… identifying instantly the various parts of speech. Even in the second or so it took you to read this sentence you subconsciously identified its form and shape because you recognised ‘problem’, ‘part’, ‘speech’ as nouns, ‘is’ as a verb, ‘instantly’ as an adverb and so on. In linguistic terms you sorted out the syntax with scarcely a thought, deferring for the moment whether or not you were going to bother working out the semantics.

By contrast, in J the parts of speech to which the various symbols belong are not immediately obvious. Take for example a discussion on the J programming forum concerning how to rearrange the square matrix i.n n in zig-zag format, so

   zigzag=.($ /:@:;@:(|.&.>`]/.)@:(</.)@:i.)@:(2&#)
   zigzag 4
0  1  5  6
2  4  7 12
3  8 11 13
9 10 14 15

The above one-line solution submitted by Henry Rich states the solution admirably, but its structure and meaning is clear only to the super-expert.

J is best understood in terms of processing lists, which is what goes on behind the scenes anyway. Verbs like transpose which operate at the surface level on objects of higher dimensions than lists are more accurately conceived as list constructors, in other words the verb transpose is not so much ‘switch matrix rows and columns’ as ‘construct a new list of lists from a given list of equal length lists’. There is no problem in extending this idea to dyadic transpose, that is to lists of lists of lists … ad infinitum.

Adverbs such as / and /. make ‘straightforward’ verbs like < and +/ into list constructors. For example

   </.i.4 4
┌─┬───┬─────┬────────┬───────┬─────┬──┐
│0│1 4│2 5 8│3 6 9 12│7 10 13│11 14│15│
└─┴───┴─────┴────────┴───────┴─────┴──┘

constructs a 7-list systematically from the elements of four 4-lists, sometimes with dimensionality (rank) being reduced in the process

   +//.i.4 4            NB. one 7-list from four 4-lists
0 5 15 30 30 25 15
   (<0 1)|:i.4 4        NB. one 4-list from four 4-lists
0 5 10 15

An interesting verb which can bring about list construction is ] (right) which it is easy to dismiss trivially as a ‘do-nothing’ sort of verb, or at least ‘deliver the right argument and do nothing with it’.

   2]i.3 3
0 1 2
3 4 5
6 7 8

However, if qualified with the prefix adverb

   ]\i.3
0 0 0
0 1 0
0 1 2

it gives successive sublists (with fill) constructed either forwards from a simple numeric, or backwards :

   (]\.)i.3
0 1 2
1 2 0
2 0 0

or as boxed lists suppressing the fill items :

   (<@:]\)i.3
┌─┬───┬─────┐
│0│0 1│0 1 2│
└─┴───┴─────┘

The same effects could be achieved by replacing ] with > or + or many other verbs.

Ken Iverson used J to suggest that the numeracy functions of the brain are more closely allied to the literacy ones than is popularly believed, the first step being to overcome the syntax barrier. Part of the problem is that whereas statement separators tend to stand out in other languages, @: meaning ‘after’ acts in J like a statement separator as in this@:that@:thenext, but is often harder to pick out in a blitz of non=alphabetic characters. In the light of this look again at :

   zigzag=.($ /:@:;@:(|.&.>`]/.)@:(</.)@:i.)@:(2&#)

in which it is difficult at a glance to pick out the all-important @: symbols. As a first step in understanding construct lists of the leading diagonals of i.n n and consolidate the procedure as

   diagilist=.monad : '</.i.y,y'
   diagilist 4
┌─┬───┬─────┬────────┬───────┬─────┬──┐
│0│1 4│2 5 8│3 6 9 12│7 10 13│11 14│15│
└─┴───┴─────┴────────┴───────┴─────┴──┘

Another important indicator which is easy not to spot is the gerund marker, that is the dash in the middle. The adverb /. activates the gerund as in

   (+`-/.)4 5 6 7
 4
_5
 6
_7

and so a fuller parenthesising is ((|.&.>)`(])/.), that is the two parts of the gerund are |.&. and ] and not |.&. and ]/. , so define

   reversealt=.|.each`]
   zz=.(reversealt/.)@:diagilist
   ,zz 4
┌─┬───┬─────┬────────┬───────┬─────┬──┐
│0│1 4│8 5 2│3 6 9 12│13 10 7│11 14│15│
└─┴───┴─────┴────────┴───────┴─────┴──┘

or, removing the boxes

   ;zz 4
0 1 4 8 5 2 3 6 9 12 13 10 7 11 14 15

Alternate diagonals have been reversed, and the problem now is to reverse the diagonalisation. Here is where an ingenious and insightful verb comes in. For any permutation p of i.n the following applies :

   p=.16?16
   (/:p){p
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

that is grade-up restores i.n from any of its permutations. Now ;zz 4 as shown above is a permutation of i.16 whose grade-up, just like any other permutation, puts the numbers of i.16 back into natural order, which is exactly what is required in order to display the zigzag matrix in its conventional 4 by 4 format. Thus define a verb :

   gradeupraze=./:@;
   zz=.gradeupraze@:(reversealt/.)@:diagilist
   zz 4
0 1 5 6 2 4 7 12 3 8 11 13 9 10 14 15

and finally reshape this as n by n :

   zigzag=.(2&#)$gradeupraze@:(reversealt/.)@:diagilist
   zigzag 4
0  1  5  6
2  4  7 12
3  8 11 13
9 10 14 15

The sophistication of the J involved cannot be disguised, but using pseudo-English to break up the primitive symbols greatly helps comprehensibility. It also helps distinguish the more subtle thinking about permutations and grade-up from the otherwise relatively mundane data structuring operations.

Solving programming exercises of this sort often lead to further generalisations. For example consider how restructuring of the 4 by 4 matrix might be achieved :

0 7  8 15
1 6  9 14
2 5 10 13
3 4 11 12

udilist standing for ‘up and down integer-list’ is a list constructor analogous to diagilist :

   udilist=.monad : '<"1 |:i.y,y'
   udilist 4
┌────────┬────────┬─────────┬─────────┐
│0 4 8 12│1 5 9 13│2 6 10 14│3 7 11 15│
└────────┴────────┴─────────┴─────────┘

Now instead of the first, third, and so on list being reversed it is now the second, fourth …, so define the gerund

   revalt=.]`(|.each)

and finally retread the ground of zigzag :

   updown=.(2&#)$gradeupraze@:(revalt/.)@udilist
   updown 4
0 7  8 15
1 6  9 14
2 5 10 13
3 4 11 12

If the start point is required to be in the south-west corner, replace revalt with reversealt.

Code Summary

diagilist=: monad : '</.i.y,y'
reversealt=: |.each`]
gradupraze=: /:@;
zigzag=: (2&#)$gradupraze@:(reversealt/.)@:diagilist
udilist=: monad : '<"1 |:i.y,y'
revalt=: ]`(|.each)
updown=: (2&#)$gradupraze@:(revalt/.)@udilist

Script

File:Fsojc18.ijs