Sample code for this post is available to download.
Preamble (OK, more of a ramble really!)
Many decades ago, I read an article about some obscure and esoteric programming languages, and amongst them was mentioned APL. The article was a little sarcastic about it, pointing out that the name was an abbreviation for the rather unimaginative “A Programming Language.” It also pointed out that the only way to write APL programs was with a special keyboard (no longer the case by the way), which cost around $80. Whilst that’s not cheap for a keyboard nowadays, it was extremely expensive back then. Not surprisingly, it never hit the big time, and I assumed it had joined the many other obscure and esoteric languages that had been created over the years.
I was somewhat surprised to discover quite recently that not only was APL not dead and buried, but was very much alive, with an active community of quite passionate programmers. I was even more surprised when I saw this short video, in which Conway’s game of Life was written with a single line of (admittedly rather obscure) code…
It’s worth watching the video, even if you don’t understand the language.
If you’re not familiar with the game of Life, I recommend you read this Wikipedia page about it, as the rest of this post will make more sense. I warn you though, Life is very addictive, and once you start, it’s hard to stop! Most programmers of a Certain Age will remember wasting many hours writing their own implementation of Life, and/or running other people’s code.
If you want to see Life in action, there are plenty of free resources where you can download the game, or run it online.
I was intrigued enough to watch that video a few times, and to check out the web site of the people who made the APL implementation that was used in the video. After a few times, I started to get the feel of what the language was doing, and realised that it has the ability to manipulate sets of data, without having to write the boilerplate code to enumerate them. Hmm, that sounds a lot like Linq.
You can probably guess what came next.
Implementing Life in Linq
I fired up LinqPad and started tinkering. It didn’t take too long before I had a basic implementation of Life – that didn’t work! At the time, I didn’t have the time to investigate further, and so left it. I picked it up again recently, and decided that one of the problems was that I hadn’t tested the helper functions I was writing. So, I started again with Visual Studio, and wrote unit tests as I went along.
In all fairness to me (sort of), I later realised that one of the reasons my original code didn’t work was that I had the Life rules wrong. I was working from memory, and hadn’t remembered correctly. I didn’t bother checking if my original code would have worked with the correct rules.
I’d like to say that I learned a lesson from this, but given my past record on this issue, and my failure to learn from that, I doubt anything will change!
Starting again gave me the chance to think about what I was doing, rather than just diving in and coding.
Although my original LinqPad version had used an integer array (so I could sum the neighbours and see how many were live) I decided to model the Life board as a 2D array of Booleans, where true meant the cell was live.
As I mentioned above, Linq is very much a set-based language, meaning you operate on sets of data (usually sequences such a a List<T> or similar) rather than iterating over individual elements of the set. As Life runs on a (theoretically) infinite 2D board, I was hoping to be able to manipulate 2D arrays with ease. Sadly, Linq does not have support for multi-dimensional arrays, mainly because most Linq methods are based around that handles variations or derivatives of IEnumerable<T>:, meaning that I was going to have to write some code to convert a 2D array to a 1D array and back again.
It turned out that converting a 2D array into a 1D was was easy. Assuming I have a 2D array called board (which is what the Life board will be called in this post and the accompanying code), then all I needed was…
bool[] board1d = board.Cast<bool>().ToArray();
Once we have the board as a 1D array, we need a way of converting a position in the array (which we will have when we enumerate through it) to a co-ordinate pair. This was pretty straightforward…
public static (int row, int col) PosToCoords(bool[,] board, int pos) =>
(pos / board.GetLength(1), pos % board.GetLength(1));
Converting the other way was a little harder, but not so complex. With the aid of a bit of searching, I ended up with this…
public static T[,] To2D<T>(this T[] source, int dim) {
int dim2 = source.Length / dim;
T[,] result = new T[dim, dim2];
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim2; j++) {
result[i, j] = source[i * dim2 + j];
}
}
return result;
}
In order to implement Life, I needed to consider each cell in the array, and then count the number of live neighbours.
So, next we need a function to count the live neighbours. For any cell on the board, there are eight neighbours to consider. I needed to start with an array of eight offsets, which would each point to one neighbour. To make this clearer, consider the Life board shown below…
The Life form shown in the image is the Gosper glider gun, the first Life form discovered that grows indefinitely.
If we’re currently working out the neighbours for the cell marked in red, then to get the co-ordinates of the cell marked in green, we need to add the offset (-1, -1). Similarly, to get the co-ordinates of the cell marked in yellow, we need the offset (0, 1). Once we have the eight offsets, we can then apply these to our current co-ordinates to get the co-ordinates of the neighbour, and then check if that cell is live.
I wanted to write as much code as I could as expressions, so I started with a collection of these offset pairs, and summed over the live neighbours. Once you add the checks to see if we have gone out of the bounds of our board, the method looked like this..
public static int Count(bool[,] board, int x, int y) =>
new List<(int, int)> { (-1, 1), (0, 1), (1, 1), (-1, 0), (1, 0), (-1, -1), (0, -1), (1, -1) }
.Sum(o => (x + o.Item1 >= 0) && (x + o.Item1 < board.GetLength(0)) && (y + o.Item2 >= 0) &&
(y + o.Item2 < board.GetLength(1) && board[x + o.Item1, y + o.Item2])
? 1
: 0);
In theory, Life runs on an infinite board, but given the finite limitations of a computer, we have to find ways around this. There are various approaches to this, including wrapping the edges around (effectively playing the game on a torus), extending the board as the live cells reach the edges, or the simplest approach, which is to assume anything out of the bounds of the array is a dead cell. That is the approach I took here, hence the checks on the array bounds above.
With that in place, implementing a Next() method that takes a board and returns the next generation was quite straightforward…
public static bool[,] Next(this bool[,] board) =>
board.Cast<bool>().ToArray()
.Select((cell, pos) => {
(int row, int col) = PosToCoords(board, pos);
int count = Count(board, row, col);
int[] born = [3];
int[] survives = [2, 3];
return cell switch {
true when survives.Contains(count) => true,
false when born.Contains(count) => true,
_ => false
};
})
.ToArray()
.To2D(board.GetLength(0));
This hard-codes the two rules for when cells are born and when they survive. An obvious thought (implemented later) was to pass these rules in, allowing the method to handle any rules.
This allowed me to run the game of Life…
The animation uses the Gosper glider gun shown earlier.
What about the speed?
As I have mentioned many times in these Linq experiments, my aim is to experiment with writing elegant Linq expressions. Whilst this generally leads to clean, maintainable code, it does not always lead to performant code. I generally don’t worry about this unless and until it becomes a problem, as Donald Knuth famously said “Premature optimisation is the root of all evil”
However, I am often curious to see how the Linq version of an algorithm compares for speed with an imperative implementation. I decided to run some speed trials on my Life code, and realised that this was a perfect example of where speed just doesn’t matter. In order to be able to make sense of the animated Life runs, I needed to add a delay in the loop, meaning that improving the speed of execution would only result in me needing a longer delay!
Yes, but its not really much of an expression is it?
As usual, my original intention was to produce a single expression that computed the next generation. The code shown above is only partway towards that aim.
However, as much of the supporting code is done with expressions, it wasn’t hard to glue it all together and come up with a single (if a bit messy) expression that uses a series of Select calls to do the job…
public static bool[,] NextSelect(this bool[,] board, int[] born, int[] survives) =>
board.Cast<bool>().ToArray()
.Select((cell, pos) => new { cell, coord = (pos / board.GetLength(1), pos % board.GetLength(1)) })
.Select(data => new { data.cell, data.coord.Item1, data.coord.Item2 })
.Select(data => new {
data.cell,
data.Item1,
data.Item2,
count = new List<(int, int)> {
(-1, 1), (0, 1), (1, 1), (-1, 0), (1, 0), (-1, -1), (0, -1), (1, -1)
}
.Sum(o => (data.Item1 + o.Item1 >= 0) && (data.Item1 + o.Item1 < board.GetLength(0)) &&
(data.Item2 + o.Item2 >= 0) &&
(data.Item2 + o.Item2 < board.GetLength(1) && board[data.Item1 + o.Item1, data.Item2 + o.Item2])
? 1
: 0)
})
.Select(data => data.cell switch {
true when survives.Contains(data.count) => true,
false when born.Contains(data.count) => true,
_ => false
})
.ToArray()
.To2D(board.GetLength(0));
This combines all the helper code into a series of Linq calls, and is, erm, messy! Compared to the previous version, it’s not very readable, and compared to the one line of APL that motivated this whole experiment, it’s positively awful! However, it is a single expression 😁.
One thing this did teach me is that choosing the right tool for the job can make a huge difference to how well and how quickly you can do the job. I’ve added APL to my list of languages that I’d love to learn, but will probably never have time. It’s #3 behind Lisp and Prolog respectively.
In conclusion
Phew, I think this has been one of my longest rambles ever! All I really did here was implement the engine that generates the Life generations. I used a very basic method of animation, and an obvious next step would be to write a decent front end to the engine. However, I’ve spent far too much time on this already, so I’ll leave that as an exercise for the reader.
Please feel free to download the sample code, and have a look at the helper methods, and the Life shapes I defined. If you have any comments, please leave them below.
Be First to Comment