Skip to Content »

Michi’s blog » J, or how I learned to stop worrying and love the matrix

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

  • December 10th, 2008
  • 8:50 am

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 k\cdot 5^n<100, then certainly k\cdot 2^n<100, 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 1×100 matrix containing 0, 1, 2, …, 99.
>:, when applied monadically, increments each element it sees by one. So >: i. 100 is the 1×100 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.

13 People had this to say...

Gravatar
  • Jusitn
  • December 10th, 2008
  • 19:17

Compact to the point of being unreadable, at least for me.

Gravatar
  • Michi
  • December 10th, 2008
  • 19:25

Justin: Which is why I took this particular one apart. The major benefit I see with J is that it has idioms for some truly awesome things. And, just like Matlab, it has the equivalent to map or zipWith in Haskell, Lisp et.c. as a completely natural and obvious thing to do.

It has a choice of signage that’s kinda imposing, but as I said above, it might well be worth getting into.

Gravatar
  • sergio
  • December 10th, 2008
  • 20:14

Makes you wonder why APL did not flourish :-)

Gravatar
  • Peter Fork
  • December 10th, 2008
  • 20:39

So “,” take a m x n matrix and makes it a 1 x mn vector?

Is this line equivalent?

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

Gravatar

Ah sweet sweet APL. The vocabulary is strange to say the least, but it does offer a whole new way of thinking about things. My favorite bit of the language is the generalized matrix multiplication (or tensor multiplication really). It’s obvious why that’d never fly in C-like languages, but I’m surprised that it hasn’t been adopted in the functional community.

Gravatar
  • Tracy Harms
  • December 10th, 2008
  • 23:56

Good reading, this; thanks. Welcome to J! Sounds like you’re ready to have your mind boggled.

One thing you wrote was inaccurate in a way that I think deserves correction.

> , gets us an 1xn matrix with the same entries, read
> row by row, from left to right, as we started with

Ravel (,) results in a simple list, not a one-by-n array. That is, its items are arranged on a single axis, not on two axes.

What I’ve said here is probably what you meant to say, but as it is possible (and different) to have a 1-by-n array that’s a distinction you’ll learn to keep track of as you work with J.

Examples:
fives=: 5=q:>:i.100
$ fives
100 6
$ , fives
600
$ ,: , fives
1 600

Gravatar
  • Wayne D. Young
  • December 11th, 2008
  • 3:13

I made a good living programming APL, a precursor to J, in the early 90s. I always liked programming in it. We were so dorky that we’d have little impromptu competitions to write the shortest program, preferably one or two lines, to accomplish a task. A math background is helpful in my opinion. Pure dorkiness. Nice to see an article on J.

Wayne D. Young

Gravatar
  • Justin
  • December 11th, 2008
  • 9:06

I’ll persevere, it is quite intimidating though

Gravatar
  • What?
  • December 11th, 2008
  • 12:35

This isn’t about a compact code, you can replace the tokens with more verbose terms, and it is still stupid.

“100″.countTrailingZeros()
100.countTralingZeros()

Thanks. I like my code readable, verbose, simplest, most dogged way of coding it with no short cuts, so I can say ‘I know that method works, I know what it does, I don’t need a test for it, I don’t need damn javadoc’.

If I get an exception, if I trace a bug down to the wrong result here, guess what, I’ve saved hours.

Simplest implementation wins over all, all the time.

Gravatar

This post made the front page of programming.reddit, FWIW. Nothing terribly interesting in the comment thread, but there were lots of equivalent one-liners in various languages.

Gravatar
  • Michi
  • December 11th, 2008
  • 17:58

What?: I agree that the compactness alone is not a virtue. However, compact (tokenwise) expressiveness _is_. I’d rewrite, in a ‘legible’ fashion the solution above as:

+/ , 5 = q: >: i. 100
plus.listOperation(flatten(5.equals(primeFactorization(increment(100.firstIntegers())))))

and even so, the real power herewithin lies, to some extent, in having a primitive for prime factorization and – more importantly – in having very smooth transitions between applying functions on atomic elements and on generalized arrays.

This last point is important. Really.

The real power, as I perceive it, isn’t in the notational choices — though the notational choices and the inherently linguistical language of the community certainly are powerful — but rather in this array agnosticism. Any function is automatically a Python/Haskell map. (Or zipWith, as it were). And THIS is an approach that for instance Java simply does not lend itself to easily. At all. And it is also an approach that opens up for the compiler/interpreter to do really interesting things under the hood to your code, knowing what it can expect.

Gravatar
  • Simon Beaumont
  • December 23rd, 2008
  • 15:48

Well j certainly looks interesting – as someone who would like matrices and other mathematical structures handled in a seamless manner, I got all excited – and nearly downloaded it – but then, since there is no 64bit version available for OS X, I looked for the source code kit… aha! so to use Jsoftware’s phrase: “I wont be betting the farm on it…” or even downloading it until they open source it… imagine depending on a language you can’t build for your platform of choice… sounds like another J thing – mind you that didn’t stop it catching on… Live free or die ;-) back to the Haskell…

Gravatar
  • David
  • June 9th, 2012
  • 19:42

In mere seconds, far less time than needed to deconstruct the J code, this calculation can be done in one’s head.  There are 20 multiples of 5 in {1,2,…,100}; add an additional 1 for each of the four of these that are multiples of 5² = 25.  Since 5³ = 125 > 100, we’re done: the exponent of 5 in the prime factorization of 100! is 24.

It is breathtakingly inefficient to make such a calculation by factoring a swath of integers.  As was noted by Legendre in 1783, for $latex n \in \mathbb{N}$, the exponent of the prime $latex p$ in the prime factorization of $latex n!$ is $latex \displaystyle \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor$, where $latex \lfloor\,\rfloor$ is the greatest integer function.  This can be evaluated by summing just $latex \left\lfloor \log_p n \right\rfloor$ iterations, starting with $latex m \leftarrow n$, of the integer division $latex m \leftarrow \left\lfloor \frac{m}{p} \right\rfloor$, stopping when this yields 0.

A poor algorithm, however neatly encoded in a particular programming language, remains a poor algorithm!  My own experience with APL was that it is devilishly easy to be entranced by its wondrously concise notation, and to lose sight of this basic fact.

Want your say?

* Required fields. Your e-mail address will not be published on this site

You can use the following XHTML tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>