During my vacations, I’ve been playing with my array language of choice, k, and I find that this article captures my feelings about the Iversonian family of languages perfectly well. On the one hand, they are so cool, it’s like alien technology—a solution to a problem can be written in fewer characters than the function declaration in C or Rust. On the other hand, there are problems that I just don’t know how to solve efficiently without loops.

For example, here’s a k function to find the prime numbers up to a given integer:

    primes: { 2+&1=+/0=r!\:r:2_!x }

    primes 10
2 3 5 7
    primes 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

To read this function, we go from right to left:

• !x: enumerate the numbers from 0 to x (exclusive); x is the name of the first argument to a lambda.
• 2_: drop the first two elements
• r:: assign the list 2, 3, …, x-1 to the variable r
• r!\:r: do the modulo of all numbers in r with all numbers in r. This gives the following matrix when x=10.

(0 1 0 1 0 1 0 1
 2 0 1 2 0 1 2 0
 2 3 0 1 2 3 0 1
 2 3 4 0 1 2 3 4
 2 3 4 5 0 1 2 3
 2 3 4 5 6 0 1 2
 2 3 4 5 6 7 0 1
 2 3 4 5 6 7 8 0)

• 0=: transform the matrix of modulos into a boolean matrix where 1 means “evenly divisible” and 0 means “not evenly divisible”

(1 0 1 0 1 0 1 0
 0 1 0 0 1 0 0 1
 0 0 1 0 0 0 1 0
 0 0 0 1 0 0 0 0
 0 0 0 0 1 0 0 0
 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 1)

(E.g., the first row, 1 0 1 0 1 0 1 0, says that 2 is evenly divisible by 2, 3 isn’t evenly divisible by 2, 4 is evenly divisible by 2, etc.; the next row, 0 1 0 0 1 0 0 1 is the “is evenly divisible by 3”, etc.)

• +/: add all the rows together; this tells us how many factors each column has.

1 1 2 1 3 1 3 2

• 1=: a prime number only has two factors, 1 and itself, but since we dropped 0 and 1 earlier, this means that primes in our solution have a 1 for the number of factors.

1 1 0 1 0 1 0 0

• &: find the position of the 1s in the boolean vector above.

0 1 3 5

• 2+: add 2 to all numbers, because we dropped 0 and 1 earlier.

2 3 5 7

I apologize for the wall of text, but I didn’t want to give a solution that looks like swearing in a comic book and not explain it.

This solution is short, simple, quite fun to write, and O(x²). The r!\:r operation performs x² modulos and if we call prime with 10,000, it takes a 2–3 seconds to obtains the answer and 100,000 takes too long.

On the other hand, this very simple sieve or Eratosthenes in C (not sure what the big-Oh complexity is) can find primes up to 100,000,000 in 2 seconds.

void sieve(u64 *a, u64 n) {
    for (u64 i = 0; i < n; ++i) a[i] = i;
    a[1] = 0;
    for (u64 i = 2; i < n; ++i) {
        if (a[i] != 0) {
            for (u64 j = 2*i; j < n; j += i) a[j] = 0;
        }
    }
}

(NB: void sieve(u64 *a, u64 n) is 25 characters; {2+&1=+/0=r!\:r:2_!x} is 20 characters.)

And herein lies my difficulty with Iversonian languages: they are simple, they are very powerful and expressive, but for certain algorithms, I feel like I’m working against the grain of the language. I don’t know how I would implement the sieve algorithm above or an algorithm like quicksort. And it makes me a bit sad: because these languages feel like alien technology, I think they might have a lot to teach us, and it’s unfortunate that they seem to have a low ceiling in what algorithms they can implement without sacrificing their unique nature.

The post makes it seem that either you write terse array expressions in APL, or you switch to a different language like Java and write imperative code. The first paragraph says that APL is absolutely awful for what it can’t do, then the rest of the essay implies that you can’t write imperative code in it.

I’ll note that Dyalog APL (the most popular APL dialect, and the only one I’m familiar with) has for loops, while loops, if statements, assignment statements, etc. There’s even a goto statement, inherited from the original 1960’s dialect. So you can write a mixture of terse array expressions and imperative code.

The essay Thinking in an array language uses ngn-K, a K dialect, another array language that looks quite different from APL or J. But it shows how you can start by writing a verbose imperative program in K using nested for loops, then iteratively simplify it, by introducing progressively more array idioms, until it is one line of code.

I think it is fine to write imperative code in APL. As you gain experience, you’ll naturally start using array idioms more and more, which increases your productivity, as you are writing a lot less code for the same functionality.

I appreciate this article, but I think it slightly (but importantly) misses the point.

Array languages have a capacity for incredibly terse code, and one of the ways to attain that level of terseness is by exploiting the puns and constraints covered here.

At the same time, the truly valuable thing about array languages is not really their concision, or at least not that you can write a program of that size in that few characters. There are more fundamental design choices—like arrays and conforming operations, or verb trains—that produce code that is concise, if not as concise as the famous Game of Life snippet, but still flexible and fast to boot.

In other words: what we should be reckoning with is not that actually APL is rubbish for writing real programs, but that we have allowed the most extreme and unrealistic depictions of its expressive power and utility to completely dominate how it’s marketed and discussed. There is, in fact, a version of Game of Life to be written in J that’s just as flexible and performant as the naive Java version that Hillel cites, and still rather simpler and more concise, because—for instance—there are no stinkin’ loops, and maybe because there are some natural opportunities for hooks and trains. It just isn’t in an absurdly impressive and unrealistically few number of characters.