I have a love-hate relationship with APLs. On one hand, they’re unbelievably powerful in what they can do. On the other hand, they’re absolutely awful in what they can’t do. I always feel like I’m walking that thin line between brilliant and stupid.
For those you who don’t know APL is one of those array languages, notorious for all its funny characters:
Avg←{(+⌿⍵)÷≢⍵}
It’s also famous for being incredibly concise. This is one of the most famous snippets of APL.
⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵
It’s Conway’s Game of Life, done in under 40 characters, “with no explicit loops and no temporary variables”. By contrast, The corresponding Java code is 22 lines and over 500 characters. This is a really impressive demonstration of APL’s power, how it almost borders on magical.
I don’t know APL, but I know J, one of its spiritual successors.^{1} Last Friday, out of curiosity, I wanted to see if I could write GoL too. I had it within 30 minutes:
((4&=@:*+.3&=@])+/@:((_2]\,,"0/~<:i.3)&|.))
And all the magic drained away.
A quick overview of how the algorithm works. The game of life board is stored as a matrix, where 1 represents a live cell and 0 represents an empty space. We shift the matrix one space in all eight cardinal directions (NW, N, NE, etc), generating eight new matrices, and add all of them elementwise to the original board.^{2}
0 0 0 0 1 0 0 1 0 -> ┌─────┬─────┬─────┐ │1 0 0│0 1 0│0 0 1│ │1 0 0│0 1 0│0 0 1│ │0 0 0│0 0 0│0 0 0│ ├─────┼─────┼─────┤ │0 0 0│0 0 0│0 0 0│ │1 0 0│0 1 0│0 0 1│ │1 0 0│0 1 0│0 0 1│ ├─────┼─────┼─────┤ │1 0 0│0 1 0│0 0 1│ │0 0 0│0 0 0│0 0 0│ │1 0 0│0 1 0│0 0 1│ └─────┴─────┴─────┘ -> 2 2 2 2 2 2 2 2 2
The game of life rules say that existing cells with 2 or 3 neighbors survive, as do empty cells with 3 neighbors. This means if a cell in the sum matrix is 3, or is 4 and the original board has a cell, the cell is alive. We generate one new matrix for each case, and boolean-or them together to get the final board.
That’s a pretty clever way to solve it. But it’s not so much a demonstration of APL’s simplicity and elegance as it is a demonstration on why Game of Life is perfectly suited to solving in APL. The APL implementation uses so many “puns” that tie it to the specifics of GoL:
Just as puns stop working as jokes when you change some words around, the APL solution stops being elegant when you tweak the problem. Consider Brian’s Brain, another cellular automata. In BB we have three states: alive, dead, and dying. It’s pretty trivial to extend the inelegant Java program to model Brian’s Brain. But the APL runs into some serious problems: we can no longer store the board state as 1 or 0, so the entire algorithm falls to pieces. Could you find another solution in APL? Probably. But it’d be a lot messier than the 30 character elegance we had up top.
Now for the kicker. Even if they’re fragile and unstable, the APL and J snippets still elegantly implement GoL. But elegant is not the same as good. Both examples I provided assume a fixed boundary to the board. Either the board wraps at the borders (as I did), or we say the borders are hard limits.^{3} Most Game of Life simulators use an infinite board, though, such as by resizing the grid whenever a cell is born close to the boundary. To save on allocations, we’d want to add a lot of extra space with each resizing, meaning that most GoL boards are “mostly” dead cells.
And herein lies the problem. Our elegant algorithm creates eight copies of the entire board for summation. That’s an O(n²) operation. The algorithm is only “elegant” because it’s brute-forcing the problem. You couldn’t use this to simulate something like the OTCA Metapixel, a 2048x2048 matrix with a period of 35,000 generations.
By contrast, the inferior, inelegant way, with loops and temporary variables, has all sorts of optimizations you can use. One of the simplest: in addition to storing a 2D grid, you can store a list of the coordinates of all the cells. Then you only need to check any cell within one space of an existing cell, so the time complexity of the algorithm only grows with the number of living cells.^{4}
We have the flexibility to do these kinds of optimizations because of the loops and variables. With them we can break the procedure down into steps, then treat each step as a separate problem. The APL solution is a holistic, single step that’s too brittle to tinker with. If you want to get the same optimization you have to throw it out and start over.
As I said before, I have a love-hate relationship with APLs. This is a perfect example of where that hate comes from. Complex problems have simple, elegant solutions which fall apart for slightly different complex problems. The solution for Game of Life is just one line! But that’s only a happy coincidence, a solution that sits in the perfect overlap between the idiosyncrasies of both APL and GoL.
At the same time, I still love them. Because when they do hit those perfect problems, they fly. J is great not because GoL is a one-liner but because I was able to write that one-liner in under half an hour. It’s just so maddening that for every problem that collapses into five keystrokes, there’s another one that should be easy but takes hours. I can sometimes sense when J is the right tool for the job, but I still struggle to know when it’s the wrong tool.
I have this newsletter so I can share thoughts on software without needing to go through the rounds of editing I put into my website posts. But now that there’s like 120 braindumps on here I think it’s time to start turning some into proper blog posts. I know I shared sneak peeks before, but that was “I’m already writing a blogpost and want to share a version with you”, not “some of these newsletters deserve to be expanded and edited.” Are there any old newsletters you’d especially like to see redone? I have a few candidates but am interested in hearing your thoughts. Thanks!
J is the language Kenneth Iverson developed after learning from the mistakes of APL. Whether that learning was successful, or whether they were even mistakes in the first place, is still the subject of much debate. ↩
We actually generate nine boards. We get offsets by taking the Cartesian product of {-1, 0, 1}
, which includes offset (0, 0)
, aka the original board. ↩
I don’t know about the APL, but adjusting the J to do this instead of wrapping is really easy: just replace the first |.
with |.!.0
. ↩
You can actually do a lot better than that by only tracking the cells that changed state. Only those or their neighbors can change in the next generation. To do this optimization you need to track metadata between generations, aka using more “temporary variables”. ↩