[nolan@nprescott.com] $  cat weblog archive feed

Conway and Klong

2019-06-22

I've been reading Nils Holm's An Introduction to Array Programming in Klong and more generally about array programming in APL and K. While it is a bit mind-bending it is also very fun. As an exercise, I've decided to implement Conway's Game of Life.

Klong

Klong is, briefly, an array programming language in the vein of K or J. The language is terse in the extreme, but is generally very small. The book itself is a brisk tour of the language and a fun read.

Game of Life

        board::[5 7]
[5 7]
        tile::[3 3]
[3 3]
        &*tile^2
[0 0 0 0 0 0 0 0 0]

Here I'm expanding (&) the square (^2) of the head of the tile (*tile). My one concession is the idea that tiles will be square, otherwise I'd want rotate to get a width value to multiply instead of squaring.

        popindex::[1 2 3 4 7]
[1 2 3 4 7]
        (&*tile^2):=1,popindex
[0 1 1 1 1 0 0 1 0]

I then amend (:=) the empty (and still-flat) "tile" with the population indexes. Obviously it isn't the shape of the tile though, it is supposed to be 3x3. So I need to reshape it with :^:

        tile:^(&*tile^2):=1,popindex
 0 1 1
 1 1 0
 0 1 0

I think a good name for this function that takes a population index and returns a matrix might be "cell":

        cell::{tile:^(&*tile^2):=1,x}
:monad
        cell(popindex)
 0 1 1
 1 1 0
 0 1 0

This next part has proved troublesome to me, as a total novice. I have tried to pad out the cell with zeroes up to the given board size, 5x7. Perhaps naively, I have made a dyad that accepts an array and a padding size:

        pad::{x,(#x)_(&y)}

The function will concatenate (,) onto some x the result of dropping (_) the length of x (#x) from a sequence of y-number of zeroes (&y). As an example:

        pad([1 1 1]; 5)
[1 1 1 0 0]
        pad([1 1 1]; 7)
[1 1 1 0 0 0 0]

This allows for the variable width and height, but at the expense of complicating the invocation. Because I don't think you can apply a dyad (function of two arguments) with an "each" operation over a matrix in the way you would over an array of rank-1, I instead create a monad (using the Klong terminology here, it is just a partial application).

What this looks like in practice:

        pad(; 7)
:monad
        pad(; 7)([1 1 1])
[1 1 1 0 0 0 0]

I mention the expense of complicating the invocation because this next bit is a doozy:

        +pad(;*board)'+(pad(;*1:+board)'cell(popindex))
 0 1 1 0 0 0 0
 1 1 0 0 0 0 0
 0 1 0 0 0 0 0
 0 0 0 0 0 0 0
 0 0 0 0 0 0 0

Working right to left:

Now, to center the cell onto the board, I'm first going to define a temporary padded to cut down some of the, uh, noise:

(I've colorized the 1's here to make the changes made more obvious at each step)

        padded::+pad(;*board)'+(pad(;*1:+board)'cell(popindex))
 0 1 1 0 0 0 0
 1 1 0 0 0 0 0
 0 1 0 0 0 0 0
 0 0 0 0 0 0 0
 0 0 0 0 0 0 0

A rotation (:+) is just the thing to shift the entire matrix down. I added 2 rows, so I want to shift 1 down to center vertically:

        1:+padded
 0 0 0 0 0 0 0
 0 1 1 0 0 0 0
 1 1 0 0 0 0 0
 0 1 0 0 0 0 0
 0 0 0 0 0 0 0

In order to shift right a rotation is also just the thing, but because the matrix is a row-major vector of vectors, I first have to transpose the matrix so the rotation is in the right "direction".

        +1:+padded
 0 0 1 0 0
 0 1 1 1 0
 0 1 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 
        2:++1:+padded
 0 0 0 0 0
 0 0 0 0 0
 0 0 1 0 0
 0 1 1 1 0
 0 1 0 0 0
 0 0 0 0 0
 0 0 0 0 0

I'll rotate (:+) by 2 and transpose (+) again to get back to the original layout (5x7):

        +2:++1:+padded
 0 0 0 0 0 0 0
 0 0 0 1 1 0 0
 0 0 1 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 0 0 0 0

In order to drive the rotation amounts directly from the available information rather than hard-coding it; I take the difference of the board and tile arrays and divide by 2 (floor division :%):

        (board-tile):%2
[1 2]

Wrapping this in a function that accepts the initial state:

        center::{[rc]; rc::(board-tile):%2; 
                 +(*|rc):++(*rc):+x}
:monad
        center(padded)
 0 0 0 0 0 0 0
 0 0 0 1 1 0 0
 0 0 1 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 0 0 0 0

With a center function defined, I think I've reach a good starting place for the neighbor search and generation steps. With that, I'll define the population index derived state as "start" and include the centering:

        start::{center(+pad(;*board)'+(pad(;*1:+board)'cell(x)))}
:monad
        start(popindex)
 0 0 0 0 0 0 0
 0 0 0 1 1 0 0
 0 0 1 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 0 0 0 0

The Search for Neighbors

The rules for Conway's Game of Life say that a point is alive in the next generation if it has 3 neighors or 4 neighbors and is currently alive. My first naive attempt was to construct two distinct rotations, left-right and up-down:

        {+x:++start(popindex)}'[-1 0 1]
 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 
 0 0 1 1 0 0 0   0 0 0 1 1 0 0   0 0 0 0 1 1 0 
 0 1 1 0 0 0 0   0 0 1 1 0 0 0   0 0 0 1 1 0 0 
 0 0 1 0 0 0 0   0 0 0 1 0 0 0   0 0 0 0 1 0 0 
 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 
 
        {x:+start(popindex)}'[-1 0 1]
 0 0 0 1 1 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 
 0 0 1 1 0 0 0   0 0 0 1 1 0 0   0 0 0 0 0 0 0 
 0 0 0 1 0 0 0   0 0 1 1 0 0 0   0 0 0 1 1 0 0 
 0 0 0 0 0 0 0   0 0 0 1 0 0 0   0 0 1 1 0 0 0 
 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 1 0 0 0 

The problem with this is that it doesn't account for diagonal neighbors:

                    0 0 0 1 1 0 0 
                    0 0 1 1 0 0 0 
                    0 0 0 1 0 0 0 
                    0 0 0 0 0 0 0 
                    0 0 0 0 0 0 0 
                          ↑
                  ┌───────────────┐
   0 0 0 0 0 0 0  │ 0 0 0 0 0 0 0 │  0 0 0 0 0 0 0 
   0 0 1 1 0 0 0  │ 0 0 0 1 1 0 0 │  0 0 0 0 1 1 0 
   0 1 1 0 0 0 0 ←│ 0 0 1 1 0 0 0 │→ 0 0 0 1 1 0 0 
   0 0 1 0 0 0 0  │ 0 0 0 1 0 0 0 │  0 0 0 0 1 0 0 
   0 0 0 0 0 0 0  │ 0 0 0 0 0 0 0 │  0 0 0 0 0 0 0
                  └───────────────┘
                          ↓
                    0 0 0 0 0 0 0
                    0 0 0 0 0 0 0
                    0 0 0 1 1 0 0
                    0 0 1 1 0 0 0
                    0 0 0 1 0 0 0

The solution I managed to come up with is probably not ideal, and it is certainly a bit gnarly. Recognizing that up-down and left-right need to vary independently to cover the diagonal cases, I made a triad to apply each of the two functions; the first argument is applied to the up-down portion, the second to the left-right, the third is the matrix to shift. With this "move" function of three argument, I partially apply it twice over the array [-1 0 1] to build out 9 distinct functions of one argument, to which a "start" matrix is supplied.

        move::{[a b]; a::x; b::y; {a:+x}({+b:++x}(z))}
:triad
        search::{[a]; a::x; ,/{[f]; f::x; move(f;;a)'[-1 0 1]}'[-1 0 1]}
:monad
        search(start(popindex))
 0 0 1 1 0 0 0  0 0 0 1 1 0 0  0 0 0 0 1 1 0
 0 1 1 0 0 0 0  0 0 1 1 0 0 0  0 0 0 1 1 0 0
 0 0 1 0 0 0 0  0 0 0 1 0 0 0  0 0 0 0 1 0 0
 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0
 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0

 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0
 0 0 1 1 0 0 0  0 0 0 1 1 0 0  0 0 0 0 1 1 0
 0 1 1 0 0 0 0  0 0 1 1 0 0 0  0 0 0 1 1 0 0
 0 0 1 0 0 0 0  0 0 0 1 0 0 0  0 0 0 0 1 0 0
 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0

 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0
 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0
 0 0 1 1 0 0 0  0 0 0 1 1 0 0  0 0 0 0 1 1 0
 0 1 1 0 0 0 0  0 0 1 1 0 0 0  0 0 0 1 1 0 0
 0 0 1 0 0 0 0  0 0 0 1 0 0 0  0 0 0 0 1 0 0

The actual shifts/moves aren't important, instead representing intermediate states of the calculation. I'm looking for the count of neighboring points. Thankfully, this part is simple, it is a sum of the 9 separate matrices. Here is a neat application of array programming, it is using the "add" (+) and "reduce" (/) across 9 matrices. I'll update the "search" function to return the sum, and can rename this summing function "neighbors":

        +/(search(start(popindex)))
 0 0 1 2 2 1 0
 0 1 3 4 3 1 0
 0 1 4 5 4 1 0
 0 1 3 3 2 0 0
 0 0 1 1 1 0 0
 
        neighbors::{[a]; a::x; +/,/{[f]; f::x; move(f;;a)'[-1 0 1]}'[-1 0 1]}
:monad
        neighbors(start(popindex))
 0 0 1 2 2 1 0
 0 1 3 4 3 1 0
 0 1 4 5 4 1 0
 0 1 3 3 2 0 0
 0 0 1 1 1 0 0

Liveness

I was concerned at how the "liveness" check was going to work when I first started on this problem. I was having difficulty imagining the check for "neighbors equal to 4 if point was alive in the last generation" without using loops. It turns out encoding the rules has been the easiest part of the whole thing:

        current::start(popindex)
 0 0 0 0 0 0 0
 0 0 0 1 1 0 0
 0 0 1 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 0 0 0 0
        neighbors(current)=3
 0 0 0 0 0 0 0
 0 0 1 0 1 0 0
 0 0 0 0 0 0 0
 0 0 1 1 0 0 0
 0 0 0 0 0 0 0
        (neighbors(current)=4)&current
 0 0 0 0 0 0 0
 0 0 0 1 0 0 0
 0 0 1 0 0 0 0
 0 0 0 0 0 0 0
 0 0 0 0 0 0 0
 
        nextgen::{(neighbors(x)=3)|((neighbors(x)=4);x)}
:monad

The nextgen function takes a single argument for the current state (a matrix), and then checks if the number of neighbors is equal to 3 (=3) or (|) if the number of neighbors is equal to 4 (=4) and (&) the current state is occupied. Below are 3 subsequent generations of the "current" matrix (starting population index):

        current
 0 0 0 0 0 0 0
 0 0 0 1 1 0 0
 0 0 1 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 0 0 0 0

        nextgen(current)
 0 0 0 0 0 0 0
 0 0 1 1 1 0 0
 0 0 1 0 0 0 0
 0 0 1 1 0 0 0
 0 0 0 0 0 0 0

        nextgen(nextgen(current))
 0 0 0 1 0 0 0
 0 0 1 1 0 0 0
 0 1 0 0 1 0 0
 0 0 1 1 0 0 0
 0 0 0 0 0 0 0

        nextgen(nextgen(nextgen(current)))
 0 0 1 1 0 0 0
 0 0 1 1 1 0 0
 0 1 0 0 1 0 0
 0 0 1 1 0 0 0
 0 0 1 1 0 0 0

As a small quality of life issue, the repeated calls to nextgen are a little annoying. The easiest fix I came up with was to create a small recursive function that takes a generation number and a starting state:

        generation::{:[0=x; y; generation(x-1; nextgen(y))]}

Unfortunately (half-joking), this is the first instance of an if (:[) in the entire program. It tests whether the generation number is 0 (0=x), and if so, returns the current generation, otherwise it recurses with x-1 and the next generation.

Demonstrated below, I invoke generation with the "current" matrix, applied over each (') of the array created by !5, which is [0 1 2 3 4].

        generation(;current)'!5
 0 0 0 0 0 0 0    0 0 0 0 0 0 0    0 0 0 1 0 0 0    0 0 1 1 0 0 0    0 1 0 0 0 0 0
 0 0 0 1 1 0 0    0 0 1 1 1 0 0    0 0 1 1 0 0 0    0 0 1 1 1 0 0    0 1 0 0 1 0 0
 0 0 1 1 0 0 0    0 0 1 0 0 0 0    0 1 0 0 1 0 0    0 1 0 0 1 0 0    0 1 0 0 1 0 0
 0 0 0 1 0 0 0    0 0 1 1 0 0 0    0 0 1 1 0 0 0    0 0 1 1 0 0 0    0 1 0 0 1 0 0
 0 0 0 0 0 0 0    0 0 0 0 0 0 0    0 0 0 0 0 0 0    0 0 1 1 0 0 0    0 1 0 0 1 0 0

Thoughts

Having spent only a few days reading about array programming it is all very alien. The interactive nature of everything is a fun change that feels like it allows quick changes across stages of the problem. Thinking in arrays is difficult and I think I am still carrying around some imperative programming baggage. Surely there are idioms to better handle the kind of unpacking I ended up doing in several places with "head of array", "head of array-drop-one". I can imagine using an array language for something like image manipulation or digital signal processing.

The Complete Program

This was a lot of writing for a 10 line program!

board::[5 7]
tile::[3 3]

cell::{tile:^(&*tile^2):=1,x}
pad::{x,(#x)_(&y)}
center::{[rc]; rc::(board-tile):%2; 
         +(*|rc):++(*rc):+x}
start::{center(+pad(;*board)'+(pad(;*1:+board)'cell(x)))}
move::{[a b]; a::x; b::y; {a:+x}({+b:++x}(z))}
neighbors::{[a]; a::x; +/,/{[b]; b::x; move(b;;a)'[-1 0 1]}'[-1 0 1]}
generation::{:[0=x; y; generation(x-1; {(neighbors(x)=3)|((neighbors(x)=4)&x)}(y))]}

a sequence of twenty generations of the program described