The Jame of Life

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.¹ 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.²

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:

• In APL, 1 is true and 0 is false. The value of "is this state alive" is a number we can add to other numbers, which is why we can count the number of neighbors by summing up the displaced boards.
• APL and J have "shift array" as a top-level primitive and elementwise matrix addition as a fundamental operation. GoL doesn't need anything that APLs are bad at, like string manipulation or conditional iteration.
• APLs have multidimensional arrays as their primary data structure, and it so happens that GoL is conventionally done on a 2D grid. Other choices of grid, like a hexagonal tiling, would create a lot more impedance.
• The only property we care about is the number of adjacent neighbors, meaning we can calculate alive/dead rules with simple arithmetic and comparisons.
• The birth number is also a survivor number, which simplifies our comparison logic. In something like HighLife, which has independent birth and survival rules, the computations you need to do get a lot harder.

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.³ 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.⁴

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.

Blogifying the Newsletter

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!

If you're reading this on the web, you can subscribe here. Updates are once a week. My main website is here.

My new book, Logic for Programmers, is now in early access! Get it here.