Michi’s blog » Blog Archive » 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

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.

Computer, J, Programming
(12) Comments

12 People had this to say...

Jusitn Said...

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

December 10th, 2008 at 19:17

Michi Said...

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.

December 10th, 2008 at 19:25

sergio Said...

Makes you wonder why APL did not flourish

December 10th, 2008 at 20:14

Peter Fork Said...

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

Is this line equivalent?

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

December 10th, 2008 at 20:39

winterkoninkje Said...

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.

December 10th, 2008 at 22:35

Tracy Harms Said...

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

December 10th, 2008 at 23:56

Wayne D. Young Said...

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

December 11th, 2008 at 3:13

Justin Said...

I’ll persevere, it is quite intimidating though

December 11th, 2008 at 9:06

What? Said...

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.

December 11th, 2008 at 12:35

pozorvlak Said...

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.

December 11th, 2008 at 16:05

Michi Said...

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.

December 11th, 2008 at 17:58

Simon Beaumont Said...

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…

December 23rd, 2008 at 15:48

Want your say?

post navigation

about: Michi is a recent PhD working in homological algebra and applied algebraic topology. This blog is his outlet for texts with some manner of thought put into them. Over at his LiveJournal intimate details and streams of consciousness might be found.
Not all here is mathematics. All here, though, are my personal thoughts and opinions. Please read the about page (linked above) for more details.
This blog uses statcounter.com for logging and traffic analysis. In order to identify return visitors, this site will issue a cookie on viewing the blog.

Travel plans

Recent Comments

Tags: MATH198

Categories

Blogroll

Family

Mathematician blogs

Archives