APL, J, NIAL and Array Theory

When I was in France, I was doing a stage with Jean-Louis Laurière in a company that dealt with payroll software and services. The idea was to express all payroll logic in a rule-based system, and he had enrolled a senior person, very knowledgeable on the subject, to explain some aspect of it over lunch. That person was a very experienced COBOL programmer and, at one point, after he had explained some calculation using nested loops, I tried to summarize:

– So, this is the Min of x and the Max of y and z.

I got a blank stare and later, when we were alone with Jean-Louis, he said he almost burst into laughter at that moment, because it was obvious he did not understand what I was saying. Mind you, he knew perfectly well how to calculate the number in question procedurally, but he lacked the concepts to express it in the succinct way I was using. He was using a lower level of abstraction, and, since there seems to be a limit on the “chunks” we can hold in our heads, the higher the level of abstraction we use, the further away our minds can reach.

Those of you that share my fascination with Functional Programming probably like it for the same reason: you can express so darned more if you use a higher level of abstraction (higher order functions, in this case). All the better, if modern implementations can perform so well that you can use this abstraction for real-life computations. This post is not about Functional Programming. There are zillion sources to read about that. This post is about what higher abstractions might look like on the realm of array programming and, in particular, APL-like languages. In another post, I might write about the three languages that contested for the HPCS.

One thing you should understand while reading about those languages is that the APL branch of languages spawed away from the conventional trunk very early. I have found a copy of “A Programming Language” and I guess that a Fortran programmer reading it at the time must have felt like someone having found the manual for the Flux Capacitor in the Middle Ages. It’s a safe guess, because I can safely imagine a Java programmer of today feeling the same, since the concepts it is based on are as much distant from Java as they are from Fortran. In fact, the Fortran programmer probably has an edge, since Fortran is ultimately concerned with manipulating array data in the first place. I hope I have tickled your fancy enough to spend some time researching APL, but I’m going to propose an easier route: study J instead, which has a free implementation, can be written in ASCII (you must surely be wondering what APL is written in, if not ASCII) and you can find a very good introductory text from the conventional viewpoint: “J for C Programmers” (can be found in the J Books). This book is very important for the outsider, because it appears that all other sources present J like the most natural thing on earth which only your limited brainpower perceives as different. Sorry, no “J for Functional Programmers” exists, but this is no big deal as array programming has no different treatment in functional languages that in conventional ones. Although you will surely have little voices in your mind whispering about higher order functions while you’ll be reading about J adverbs. Curiously, a presentation of array programming that seems more close to the language of the functional programmer can be found in material for NIAL (download Papers.zip and don’t go to the root of the site), which I did not know but read about in the APL F.A.Q. Array Theory seems like a good theoretical underpinning for such languages.

Rule #34 of the internet supposedly says that, if something exists, there’s porn for it. Here’s some J porn for you. I used this as a programming test once believing that, someone who can learn enough J to answer this, can learn anything else needed on the job. I was not let down.

Given a 9×9 array of integers from 1 to 9, forming the supposed solution to a Sudoku puzzle (http://en.wikipedia.org/wiki/Sudoku), write a J verb (program) that computes whether the 9×9 array is, indeed, a solution according the following rules for Sudoku: Every line, every row and every 3×3 tile (3×3 tiles are arranged in a 3×3 arrangement to tile the entire array, see Wikipedia article) should contain every number from 1 to 9 one unique time.

The solution should use verb ranks to partition the array in all the needed ways (cells), and determine uniqueness by applying the same test verb in the appropriate manner.

And this is my own solution to that.

test3 =: monad define
                items =. ,y
                (9=#~.items) *. *./(items>0),(items<10)
)

is_sudoku3 =: monad define
                *./ (test3"_1 y) , (test3"_1 |: y) , (,(3 3 ,: 3 3) test3;._3 y)
)

Update: At the time I devised this exercise I could not find any relevant article, but I just now found a full Sudoku solver in J at the J Wiki.

Advertisements

One thought on “APL, J, NIAL and Array Theory

  1. Pingback: Fwd: HPCS recap | dsouflis

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s