Michi's Blog

J, or how I learned to stop worrying and love the matrix

Or actually, I haven't quite yet.

But, out of a whim, I downloaded J and started to play with it while reading this set of neat notes on Functional Programming and J.

And ... well ... my reaction so far is kinda "Buh!? What the *** just happened there?"

The first example I ran across, tried to read, and finally managed to is the following:

+/ , 5 = q: >: i. 100

This snippet is supposed to tell us how many 0s are trailing 100!. To get at this, we first need to figure out what, exactly, is done here. First observation is that 100! is the product of all integers from 1 to 100. The second is that the number of 0s trailing this is the same as the lower of the orders of 2 and 5, respectively, dividing 100!. Which, in turn is the lower of the numbers of 2s and 5s occurring in the totality of all prime decompositions of all the integers from 1 to 100.

Now, if [tex]k\cdot 5^n<100[/tex], then certainly [tex]k\cdot 2^n<100[/tex], so the sum of orders of 2 is guaranteed to be larger than the sum of orders of 5, so it is enough to count the number of 5s dividing any of the numbers along the way. And THIS is what the program above computes.

Next thing to figure out is how it does this. It turns out, after some experimenting, that the best way of reading this is to go through from right to left and figure out what it all does. All the functions we're looking at end up being applied in a monadic fashion - which means something completely different in J than in Haskell - here it means that the function gets applied to a single argument. So, here goes:

i. n lists the first n integers, starting at 0. So i. 100 is
the 1x100 matrix containing 0, 1, 2, ..., 99.
>:, when applied monadically, increments each element it sees by
one. So >: i. 100 is the 1x100 matrix containing 1, 2, 3, ...,
100.
q: yields a prime factorization of the integers it sees. So from
q: >: i. 100 we get a matrix where each row carries the primes
dividing the row number, with 0 padding at the end.
Then we see the one dyadic (as opposed to monadic) application in
this program. 5 = mtx yields a matrix of the same shape as mtx,
but with a 1 whenever the corresponding entry is a 5, and 0 otherwise.
So 5 = q: >: i. 100 picks out the entries in all the prime
factorizations that are equal to 5.
Then ,. This is one of two complementary operators to reshape
matrices. , gets us an 1xn matrix with the same entries, read row
by row, from left to right, as we started with - whereas n m $ mtx
takes the matrix in mtx and builds an nxm matrix out of it. Thus,
, 5 = q: >: i. 100 flattens out the matrix with the 0 and 1 we got
out above.
And finally, +/ is an example of a J adverb being used. + is
a dyadic function corresponding to, as expected, usual addition. /
is a monadic adverb that takes a dyadic function, and inserts it
between all the elements in the following list. This is essentially
identical to the Haskell call foldr. So +/ is more commonly
known as "sum". And thus, +/ , 5 = q: >: i. 100 sums up the 0s and
1s produced by picking out all the entries in the prime factorization
matrix that are equal to 5, after flattening the matrix. Or, in other
words, counts the 1 entries. Which is the same as counting the number
of 5s in the prime factorizations of all the integers between 1 and
100.
Note that if we skipped the flattening step given by , then the
application of +/ would have just summed each column in the
matrix. So, we would have needed to apply it again to get the total
tally.

So far, my impression is essentially that WHOA! That language is compact to the point of insanity. Once you master the vocabulary, it kinda gives the feeling that the system has insane amounts of power - but the vocabulary is kinda imposing, as is the shift in the way I think about programming. I foresee learning J giving me the same kinds of epiphanies and major brain twists as Haskell did - so it might well be an appropriate next challenge.

social