indexpost archiveatom 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}
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]
[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)
[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:

• take the cell of the population index `cell(popindex)`
• the pad function is partially applied with the first element (`*`) of the rotated board (`1:+board`). The rotation is used to take the column portion of the row-column array
• to "each" (`'`) row I apply the partially applied pad function, `pad(;*1:+board)'`. At this point the columns have been extended to 7 elements
• the entire board is transposed (`+`)
• a second partial application of the pad function is created, this time with the row portion of the row-column array, `pad(;*board)`
• this is applied to each of the arrays of the transposed board. This achieves an extension of the rows through the same means as the columns by changing the data rather than the function
• a final transposition is applied to set aright the board, back to the original layout

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

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}
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)))}
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))}
search::{[a]; a::x; ,/{[f]; f::x; move(f;;a)'[-1 0 1]}'[-1 0 1]}
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]}
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)}
```

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}