Array programming, part 3

In this post, I want to show you some examples of code I’ve written in J, which is one of the canonical array programming languages.

J was Ken Iverson’s final version of APL, into which he poured all the experience he’d gained with array programming over his career. Roger Hui did most of the implementation work, apparently starting from a one-page fragment dashed off by Arthur Whitney. Sadly, Ken and Roger are no longer with us, but J is still being maintained and extended by Eric Iverson (Ken’s son) and Henry Rich. Thanks to both of them for all their hard work and design expertise!

Array languages can be difficult to get into. With other languages, there is often a typical use case that can be your first exposure to the language. For instance, when I started learning Python, I used it to write small scripts to be run at the command line. (Come to think of it, that’s still what I use Python for.) With functional languages like OCaml and Haskell, I started out by writing little language interpreters and puzzle solvers. But what’s a good first project for array languages?

It turns out that the Advent of Code problems are ideal practice problems for learning array programming. I’ll show some examples from the 2021 AOC problems. I will ignore the story part of the problems and just describe the problems themselves, along with my solutions in J. I’ll walk through them in painstaking detail so that you can understand every part of them, because I want to demystify the language and the development process as much as I can.

In this post, I’ll do problem 1. Like all AOC problems, it has two parts.

Part A

Inputs

The input to the first part of this problem is a series of integers, one per line. You need to count the number of times an integer increases over the previous integer. The first integer is not considered an increase. The sample input is as follows:

199
200  (increase)
208  (increase)
210  (increase)
200
207  (increase)
240  (increase)
269  (increase)
260
263  (increase)

In this case, the “increase count” will be 7.

Python solution

This is trivially solved in e.g. Python:

nums = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]
count = 0
for i in range(1, len(nums)):
   if nums[i] > nums[i-1]:
       count += 1
print(count)

However, that seems like quite a lot of code for such a simple problem. (You can undoubtedly do better in Python, but let’s press on.)

J solution

For J we’ll define an array containing these numbers:

nums =: 199 200 208 210 200 207 240 269 260 263

Recall that the =: operator (not a typo) is the J assignment operator.

J also has various explicit looping constructs, but we won’t be using them here because they don’t take advantage of the array programming paradigm.

Maybe it would interest you to see that my final solution for part A of problem 1 is this:

f =: [: +/ 2 </\ ]

Toto, I don’t think we’re in Kansas any more.

The whitespace is not essential; I could have written it as:

f=:[:+/2</\]

and it would still work. I’ll often add spaces to make the code clearer. It’s how I roll.

Here’s an interactive session:

   nums =: 199 200 208 210 200 207 240 269 260 263
   f =: [: +/ 2 </\ ]
   f nums
7

What’s going on here? I’ll tell you. (Strap yourself in.)

Walkthrough of the part A solution

This solution (the function f) is what is called a tacit definition, which means it’s a function (verb) which is created by composing other functions (verbs) together using the “trains” feature I talked about in the previous post. Tacit definitions thus don’t represent the input argument(s) explicitly; they are like “point-free” definitions in functional languages like Haskell. They are very elegant and short, but they aren’t easy to understand. We can make this clearer by writing it as an anonymous function with an explicit argument. J uses the name x for the left argument and y as the right argument of an anonymous function. (Here, we just have a right argument.) The contents of the function are written inside double curly braces, like this:

   f =: {{ +/ 2 </\ y }}

You might wonder what happened to the [: symbol. I’ll get to that. As for the ] primitive, that means “right argument”, which is the same as y in this context. I’ll put all the pieces together below once we understand what this function is actually doing.

We can write the contents of the function applied to the data directly:

   +/ 2 </\ nums
7

In fact, the usual way of developing code in array languages is to start from a special case like this and extract a function.

This is still pretty obscure, so let’s break it up:

   nums
199 200 208 210 200 207 240 269 260 263
   2 </\ nums
1 1 1 0 1 1 1 0 1
   +/ 2 </\ nums
7

Again, this is typical of the way you develop a function in J. You start with your data, apply some transformations to it, and keep doing it until you get the answer you want. Then (if you need to) you extract a function.

Let’s look at the first four lines:

   nums
199 200 208 210 200 207 240 269 260 263
   2 </\ nums
1 1 1 0 1 1 1 0 1

What this code is doing is applying the </ function to adjacent array elements. This is the same as computing elem1 < elem2 for adjacent array elements elem1 and elem2. (Booleans in J are represented by 0s and 1s.) Notice that it does this correctly; the input array nums has 10 elements while the difference array has only 9.

To understand how this is actually computed, I’m going to show you a different computation:

   nums
199 200 208 210 200 207 240 269 260 263
   2<\nums
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
|199 200|200 208|208 210|210 200|200 207|207 240|240 269|269 260|260 263|
+-------+-------+-------+-------+-------+-------+-------+-------+-------+

This is an array of 9 boxes. It is not a multidimensional array of integers. Boxes can contain any J value; all these boxes happen to contain one-dimensional arrays of length 2. So the <\ verb groups the input numbers into groups of a specified size (here, 2). We can do this with groups of 3 or more too:

   nums
199 200 208 210 200 207 240 269 260 263
   3<\nums
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
|199 200 208|200 208 210|208 210 200|210 200 207|200 207 240|207 240 269|240 269 260|269 260 263|
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+

The \ (backslash) primitive is the infix adverb. It modifies the verb to its left. In the case of <\, the left verb is the box constructor verb <, which converts an array into a box.

For instance:

   1 2 3
1 2 3
   < 1 2 3
+-----+
|1 2 3|
+-----+

Now the array 1 2 3 (with 3 items) is “boxed” into a single item.

OK, so if we do e.g. 2 <\ nums, we are saying “make an array of boxes of 2 consecutive items from the array nums”. As we’ve seen, this gives us:

   2<\nums
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
|199 200|200 208|208 210|210 200|200 207|207 240|240 269|269 260|260 263|
+-------+-------+-------+-------+-------+-------+-------+-------+-------+

So the infix adverb \ converts its left verb (here, <) into a new verb which takes a scalar value (call it n) as its left argument and an array as its right argument, and groups the array in groups of n (here, 2), and then applies the modified function (here, <) to the groups. This generates an array of boxes of length-2 arrays.

   _2<\nums
+-------+-------+-------+-------+-------+
|199 200|208 210|200 207|240 269|260 263|
+-------+-------+-------+-------+-------+

But wait, it gets weirder! What if the left argument wasn’t a single number?

  2 3<\nums
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-------+
|199 200    |200 208    |208 210    |210 200    |200 207    |207 240    |240 269    |269 260    |260 263|
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-------+
|199 200 208|200 208 210|208 210 200|210 200 207|200 207 240|207 240 269|240 269 260|269 260 263|       |
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-------+

And that is rank polymorphism in action. The <\ verb expected a number as the left argument, got an array, and so automatically mapped the function over all elements of the array (here, 2 and 3), and accumulated the results into a larger array, padding where needed. (The pad here is the “empty box” i.e. a box with no contents.) This is cool, but we won’t need it here.

As an aside, it’s kind of staggering how much computation can be distilled into a measly few characters in array languages. (Thanks Ken!)

Getting back to our example, we had:

   2<\nums
+-------+-------+-------+-------+-------+-------+-------+-------+-------+
|199 200|200 208|208 210|210 200|200 207|207 240|240 269|269 260|260 263|
+-------+-------+-------+-------+-------+-------+-------+-------+-------+

but what we really used was this:

   2 </\ nums
1 1 1 0 1 1 1 0 1

Instead of the < verb, we used the </ verb. Just one little character change! What does that do?

Recall from my previous posts that / is the “fold right” or “reduce” operator (J calls it insert). It’s an adverb that inserts its left (verb) argument into the spaces between array elements. The inserted verb therefore has to be dyadic (two-argument).

   </ 10 20
1
   </ 20 10
0
   </ 1 2 3   NB. parses as 1 < (2 < 3)
0
   1 < 2 < 3
0

Since 2 < 3 yields 1, 1 < 2 < 3 yields 1 < 1, or 0. So if you apply </ to a two element array, you get the less-than operator applied to the two elements (first < last). When we apply that to each group of 2 we created above, we get an array of boolean 1s and 0s:

   2 </\ nums
1 1 1 0 1 1 1 0 1

Each 1 represents an increase over the previous element. Now we just have to count the 1s. Use the +/ verb to sum them up:

   +/ 2 </\ nums
7

And that’s the answer.

Treating booleans as 0s and 1s is often useful computationally. It seems “wrong” to me, typed functional programming zealot that I am, but being able to do arithmetic with boolean values has lots of applications.

Converting the J solution to a (tacit) function

OK, we now can get our answer like this:

   +/ 2 </\ nums
7

However, to solve the AOC problem we have to be able to apply this to a much larger array. Let’s assume we’ve loaded that up as nums2. We can of course just compute this:

   +/ 2 </\ nums2
1557

but it would be nicer if we could extract the solution code into a function. J does allow you to bind a name to a function, but we can’t just do this:

   f =: +/ 2 </\
|syntax error
|   f=:+/    2</\

This isn’t a valid function definition. We need to represent the right argument explicitly. The easiest way is (as we saw above) to write an anonymous function with an explicit right argument, called y:

   f =: {{ +/ 2 </\ y }}
   f nums2
1557

This is often good enough, but it’s interesting to see if we can push it further. To do that, we can break up the function as we did before.

   f1 =: {{ 2 </\ y }}
   f =: {{ +/ f1 y }}
   f1 nums
1 1 1 0 1 1 1 0 1
   f nums
7

OK, everything checks out so far. Let’s see if we can make these into tacit definitions. For f1 there’s only one verb: </\. We could define that as a separate verb; call it g:

   g =: </\
   2 g nums
1 1 1 0 1 1 1 0 1
   f1 nums
1 1 1 0 1 1 1 0 1

We need a way to bind the 2 left argument into the verb g. One way in J is to use the & (bond) conjunction:

   h =: 2&(</\)
   h nums
1 1 1 0 1 1 1 0 1

Unfortunately, we can’t omit the parentheses:

   h2 =: 2&</\
   h2 nums
199 0 0 0 0 0 0 0 0 0

But there’s another, spiffier way to write this. We can use a “fork”, which is a train of three verbs. There is a (somewhat obscure) J primitive called 2: which always returns 2 given any input:

   2: 10 54 _101
2

We can then write f1 as:

   f1 =: 2: </\ ]
   f1 nums

The ] primitive simply returns the right argument unchanged; it’s basically the identity function. (There is also a [ primitive that returns the left argument.) The fork rule for trains of three consecutive verbs says:

  (f g h) x --> (f x) g (h x)

(This is for a fork with only a right argument, which is what we have here.) In our case, we have:

  (2: </\ ]) nums
  --> (2: nums) (</\) (] nums)
  --> 2 (</\) nums
  --> 2 </\ nums

as desired. So we can write

  f1 =: 2: </\ ]

without parentheses.

It’s actually better than that. When the leftmost argument in a fork is a noun, it’s automatically “promoted” to a function which returns that noun on all arguments. So if we used 2 instead of 2:, it would be promoted to the equivalent of 2:, leading to this even shorter definition:

  f1 =: 2 </\ ]

To recap, we now have:

   f1 =: 2 </\ ]
   f =: {{ +/ f1 y }}

Now we are in a tight spot. We would like to write f as +/ f1, but this won’t work. It’s completely natural to expect that putting two functions side-by-side like this (+/ and f1) would give the composition of the two functions (which is what we want) but J doesn’t do this; instead, it makes them into a “hook”. This uses the rule:

  (f g) x --> (f x) g x

which is not what we want.

What we do want is simple function composition. There are multiple ways to achieve this in J. One way is to use the @: (“at”) conjunction:

   f1 =: 2 </\ ]
   f =: +/ @: f1
   f nums
7

This works, but it seems out of place; you have to add a composition operator between two functions, but not when you are making a fork of three functions. So there is another way:

   f1 =: 2 </\ ]
   f =: [: +/ f1
   f nums
7

The [: symbol is called “cap” and we saw it above. It’s what I call a “pseudo-operation” since it has no syntactic class. (Put differently, it’s “pure syntax”.) It’s used in the leftmost position of a 3-verb train to convert it into a 2-verb function composition. The rule is:

   ([: f g) x --> f (g x)

In many cases this is cleaner than using the @: composition operator.

Now we can combine everything together. The trick here is that if you have multiple verbs in a row, they combine into forks on the right in groups of 3:

   V1 V2 V3 V4 V5  --> V1 V2 (V3 V4 V5)

and this is exactly what we need:

   f1 =: 2 </\ ]
   f  =: [: +/ f1
   f nums
7
   f =: [: +/ (2 </\ ])
   f nums
7
   f =: [: +/ 2 </\ ]
   f nums
7

We don’t even need any parentheses! And that’s our tacit definition.

Computing a tacit definition from an explicit definition

By now, you probably think that there is no way I could possibly have more to say about this function:

   f =: [: +/ 2 </\ ]

You’d be wrong.

Even though I showed you how to derive this tacit function, that derivation was kind of painstaking. It turns out that J has the ability to derive a tacit definition for you given an explicit definition. Recall the explicit definition:

   f =: {{ +/ 2 </\ y }}

Take the contents of the function inside the {{ }} anonymous function brackets, and turn it into a string:

   fs =: '+/ 2 </\ y'

Now pass that to the mysterious 13 : primitive:

   fs =: '+/ 2 </\ y'
   13 : fs
[: +/ 2 </\ ]

And hey presto! J figured out the tacit version of the definition in an instant! I usually write it like this:

  13 : '+/ 2 </\ y'
[: +/ 2 </\ ]

and then just copy the tacit definition:

  f =: [: +/ 2 </\ ]

This makes you look like a high-level J wizard when all you’re doing is letting J come up with the clever definition given your boring definition. 😁 (If you can just write this out directly, you are a J wizard!)

Other solutions

There are many other possible solutions. One (suggested by my friend Darius Bacon) looks like this:

   f =: [: +/ }: < }. 
   f nums
7

This is just as concise, and uses fewer tokens. It compares the array (without the leading item) with the array (without the trailing item) using the < operator (pointwise i.e. item-by-item), then adds up all the results. (The }. or “behead” primitive copies an array, leaving out the first item. The }: or “curtail” primitive copies an array, leaving out the last item.) This is also a great illustration of the power of trains.

That’s enough for this part of the problem. All Advent of Code problems have two parts, so let’s look at the next part.

Part B

The second part of the problem is like the first, except that instead of comparing successive array elements, we need to compute the sums of three adjacent elements and compare these sums. Given what we’ve already done, this is going to be easy.

   nums =: 199 200 208 210 200 207 240 269 260 263
   3 <\ nums
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
|199 200 208|200 208 210|208 210 200|210 200 207|200 207 240|207 240 269|240 269 260|269 260 263|
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
   3 +/\ nums
607 618 618 617 647 716 769 792

OK, so we’ve computed the sums of 3-element windows of the input array. We can see that this sum increases 5 times. We could show this using our previous strategy:

   3 +/\ nums
607 618 618 617 647 716 769 792
   2 </\ 3 +/\ nums
1 0 0 1 1 1 1
   +/ 2 </\ 3 +/\ nums
5

This would lead to the definition:

   f =: [: +/ 2 </\ 3 +/\ ]

But we can also adapt Darius’ version:

   3 +/\ nums
607 618 618 617 647 716 769 792
   (}: < }.) 3 +/\ nums
1 0 0 1 1 1 1
   +/ (}: < }.) 3 +/\ nums
5
   ([: +/ [: (}: < }.) 3 +/\ ]) nums
5
   f =: [: +/ [: (}: < }.) 3 +/\ ]
   f nums
5

The new definition is slightly longer than the previous definition because it’s a composition of three functions: 3 +/\ ], }: < }., and +/. Notice we needed two caps ([:) to avoid inadvertently creating trains. We can also use the @: composition operator, though the results are no better:

   f =: +/ @: (}: < }.) @: (3 +/\ ])
   f nums
5

So the most concise definition (of the ones we’ve seen) is still:

   f =: [: +/ 2 </\ 3 +/\ ]

Putting it all together

Our complete solution for problem 1 would then be:

   f1 =: [: +/ 2 </\ ]
   f2 =: [: +/ 2 </\ 3 +/\ ]

Not too shabby.

We could factor out the repeated parts. That would give us a higher-order function acting on a single function argument i.e. an adverb:

   a =: {{ [: +/ 2 </\ u }}
   f1 =: ]a
   f2 =: (3 +/\ ])a

Notice how the a adverb modifies the verb to its left.

This factoring doesn’t make the code significantly shorter, so it’s not really worth it. (Also, I don’t know how to come up with a tacit definition for a!)

Coming up

Stay tuned for more J code walkthroughs!