Game of Life

I've made my first implementation of Game of Life using JavaScript. A very rewarding task for a developer aiming to get better. You are free to test my browser version or my node.js version hosted at GitHub.

This is from the browser rendering:

This is from the node-js rendering:

In this post, I will shortly explain the logic related to the implementation, excluding the rendering and state-management of the demos.

Game of Life is a simulation by the late mathematician John Conway (1937 - 2020). It became known to the public 1970 as a 'mathematical puzzle' when it appeared in the Scientific American. Game of Life continues to fascinate new generations.

Conway constructed Game of Life as a project, researching cellular automaton, a field investigating surfaces manifested as grids with a set of cells who each have a finite number of states (true or false, for instance).

A cellular automaton is a 'world' in the sense that given rules, the rules (can) change the state of cells over time from generation to generation.

What is Game of Life? It's called a zero-player game since you only configure an initial 'board' with alive (and implicitly) dead cells. Given a few simple rules amazing patterns can emerge. Game of Life is Turing complete, meaning it's possible to make patterns that can act as a Turing machine and in theory solve any computation. The universality of the rules has been tested and machines have been built using them.

What are the rules?

You can also phrase the rules like so:

Game of Life is played on a rectangular grid of square cells. A cell is neighbour with another cell if it is next to it.

Starting from the north we travel clockwise, allowing vertical, horizontal, and diagonal movements.

const POSSIBLE_DIRECTIONS = {
  north:     [  0, -1 ],
  northEast: [  1, -1 ],
  east:      [  1,  0 ],
  southEast: [  1,  1 ],
  south:     [  0,  1 ],
  southWest: [ -1,  1 ],
  west:      [ -1,  0 ],
  northWest: [ -1, -1 ]
};

However, I have this object only for declarative reasons. What I want are the values.

For each cell, I need to investigate its neighbour relation and their state. Therefore,

const dirs = Object.values(POSSIBLE_DIRECTIONS);

Based on all the possible directions, I ask which neighbours are alive?

function neighboursAlive(world, x, y) {
  return dirs.reduce(
    (aliveNeighbours, [ diffX, diffY ]) => isNeighbourAlive(
        world, 
        x + diffX, 
        y + diffY
      )
        ? aliveNeighbours + 1 
        : aliveNeighbours
    , 0
  );
}

How do we know if a neighbour is alive? In my implementation, the state of a cell - if it is alive or dead - is represented by a boolean value:

const ALIVE = true;
const DEAD = false;

Given a world, a grid, and a position to look at, I investigate this state by first checking if the position is in range of the grid.

At position 0,0 looking west would mean looking outside the grid. This is a design choice, some implement Game of Life so that looking west from position 0,0 would mean a cell positioned to far right on the grid. In my implementation, this is outside the tip of the world - in emptiness, and thus false:

function isInRange(w, h, x, y) {
  return x >= 0 &&
    x < w &&
    y >= 0 &&
    y < h;
}

A cell must be in range and be alive to be 'true'.

function isNeighbourAlive(grid, x, y) {
  return isInRange(
      width(grid), 
      height(grid), 
      x, 
      y
    ) && 
    grid[y][x];
}

The width and height are simple helpers:

const height = (grid) => grid.length;
const width = (grid) => grid[0].length;

The function (quoted again) provide the answer to the question of how many living neighbours a cell has, starting from 0.

function neighboursAlive(world, x, y) {
  return dirs.reduce(
    (aliveNeighbours, [ diffX, diffY ]) => isNeighbourAlive(
        world, 
        x + diffX, 
        y + diffY
      )
        ? aliveNeighbours + 1 
        : aliveNeighbours
    , 0
  );
}

What is important is the transition from a state to the next. If we have a grid, a world, filled with cells (each either alive or dead, true or false) we determine the next state of the 'world' by determining the next state of each cell.

function nextState(grid) {
  return grid.map(
    (row, y) => row.map(
      (cell, x) => nextCellState(cell, neighboursAlive(grid, x, y))
    )
  );
}

I choose to concentrate on next generation living cells. Based on the current state (alive and dead) three possible states leading to life in the next generation emerge:

const SPECIAL_STATES = [
  {
    ssState: DEAD,
    ssNeighboursAlive: 3,
  },
  {
    ssState: ALIVE,
    ssNeighboursAlive: 2,
  },
  {
    ssState: ALIVE,
    ssNeighboursAlive: 3,
  }
];

All other possible states lead to death.

Therefore, given the current state and the number of alive neighbours, I check if one of the three special cases above is true. Otherwise, I conclude, following the rules of Game of Life, the cell at hand will die (if it dies it's status is false).

function nextCellState(state, neighboursAlive) {
  return SPECIAL_STATES.some(
    ({ ssState, ssNeighboursAlive }) => ssState === state && 
      ssNeighboursAlive === neighboursAlive
  );
}

This is my implementation of the logic. I used a functional programming-like approach, as you see. The performance is not the best, but it's good enough given a small grid. My aim has been to solve this problem with readable code, nothing else.

The logic only handles the manipulation of state transition in a cell, given the state of its neighbours, moving from one generation to the next.

In my view, what we do with this - how we iterate numerous generations, the 'game loop' - should not part of the logic.

In my demos, I deliberately slowed down the transition so the 'evolution' would appear pleasant for the eye.

Adhoc. A failure, and a reflection on declarative style

In my implementation, I have a function labeled neighboursAlive that takes a world (a grid with cells) and a position x,y, and returns how many alive neighbours this cell has.

I am not satisfied with my solution as my intention was to write readable code.

My implementation for this particular problem:

function neighboursAlive(world, x, y) {
  return dirs.reduce(
    (aliveNeighbours, [ diffX, diffY ]) => 
      isNeighbourAlive(
        world, 
        x + diffX, 
        y + diffY
      )
        ? aliveNeighbours + 1 
        : aliveNeighbours
    , 0
  );
}

From the outside the label is declarative, but in the situation of solving the problem (or when refactoring) the code itself is not very declarative. The use of reduce to avoid an assignment could be called a Hollywood version of functional programming.

function neighboursAlive(world, x, y) {
  let sum = 0;
  for(const direction of directions) {
    const [ diffX, diffY ] = direction;
    if(isNeighbourAlive(world,  x + diffX, y + diffY)) {
      sum += 1;
    }
  }
  return sum; 
}

This function is just as pure. As someone said, what's important in functional programming are values being 'eventually immutable'.

The label sum can't possibly be mutated in any way by some side-effect. It doesn't matter what other values mutate outside of the function. I was silly to use reduce.

What is declarative programming? Declarative is not concerned about implementation, it is concerned about what we need to act - what we need in terms of 'behavior' to provide an accurate answer to a question.

Instead of asking how to achieve something, the declarative approach, closely affiliated with functional programming, is committed to what needs to be done.

Let's try and see what happens if we speak about the declarative approach not in terms related to the world of programming but through the philosophy of language and the view of late Ludwig Wittgenstein. Sometimes we fail when we shoot from the hip, sometimes we hit the spike but this is only possible when we dare to take risks. And it's not as important if the similarity is real: what's important is if this analogy is productive.

Early Wittgenstein attempted in his seminal treatise Tractatus to package reality and its relation to language in an orderly, hierarchical fashion. In a beautiful but vain attempt, Wittgenstein produced a model that would correlate mind, language, and the world as we perceive it through language and the mind. Wittgenstein himself was later on not very satisfied with the solipsism that followed.

Early Wittgenstein thought of the world as the totality of all facts 'being the case'. The world is built by small atomic units, objects, simple and unanalyzable, only possible to emerge as parts of a state of affair, as part of a composition. Language is a reflection - a mirror - of the world sharing its logical form. Names mirror objects, elementary propositions mirror facts. And so on, building a jigsaw pattern of things - language - and the perceived world.

In this view lots of things we speak about - everything that cannot be depicted as a state of affairs - are meaningless. 'Whereof one cannot speak thereof one must be silent.'

Some claim there is a great rift between the approaches in Tractatus and the Philosophical Investigations and other notes. But I'd rather want to see Wittgenstein's later works as a continuation.

In broad terms, late Wittgenstein asks: why is it that we can use language to describe logic, propositions of science, and have ordinary conversations? The former categories loosely speaking self-contained (or so they seem), while the latter category is vague and at times illusory.

What do we do with words?

Suppose everyone had a box with something in it: we call it a "beetle". No one can look into anyone else's box, and everyone says he knows what a beetle is only by looking at his beetle.—Here it would be quite possible for everyone to have something different in his box. One might even imagine such a thing constantly changing.—But suppose the word "beetle" had a use in these people's language?—If so it would not be used as the name of a thing. The thing in the box has no place in the language-game at all; not even as a something: for the box might even be empty.—No, one can 'divide through' by the thing in the box; it cancels out, whatever it is. That is to say: if we construe the grammar of the expression of sensation on the model of 'object and designation' the object drops out of consideration as irrelevant.

When we use the word 'beetle', we use it to achieve something when speaking to others. If everyone acts and say things as if the beetle is a small bug, would it matter what people had in their boxes? What it even matter if someone lied? Would it matter if someone had a grasshopper in their box? No, not while playing an act in this particular language-game.

Words have meaning when used in actions to produce an assumed effect in communication. Language is not private.

In functional programming, functions are 'black boxes'. We are concerned with this: every input to the box must produce the same output. If this is not true the function is not pure, we say.

What happens inside the box?

It doesn't matter all that much. If the function is pure, we can count on it - this time and the next. And if we give it a label, a name that declares an intent, we can use this label to reason about what we need to act, what we need to achieve an answer to a question. In some respects, it doesn't matter if the function is implemented. We can still reason about what we need to achieve some effect.

The connection to the purity of the function? I think of them as inside and outside, or two sides of the same coin.

const f = (...xs) => xs.reduce(
  (acc, v) => acc + v,
  0
);

f? Obviously, we have written a function that returns the sum of some values. But f is not a label we can reason about. We can write all the tests and produce formal proofs in the world, a function labeled f is still not a function we can use to reason with. Its label is non-declarative. So are the arguments needed, xs. In fact, we would have to read through the (in this case short) function to understand what we can do with it.

const sum = (...numbers) => numbers.reduce(
  (sumOfNumber, number) => sumOfNumber + number, 
  0
);

Or making it more general and taking advantage of the peccularities of JavaScript (adding both numbers and strings):

const add = (...values) => values.reduce(
  (accumulatedValue, value) => accumulatedValue + value
);

What do we need to achieve the sum of some numbers? With declarative labels, it's easier to answer.

A black box? Does it matter if the beetle is inside? Yes, the implementation does matter. On the other hand, it is not as important in the context of business logic. When reasoning about how to solve problems, what needs to be done 'to answer a question'.

Involved in development, we are always in a situation involving boxes, always inside a box dealing with another box or boxes. Declarative development would be, among other things, to make sure not to leave a situation without leaving a declarative label.

Language is not private, therefore a function that sums (or adds) numbers (or values) does not respect this with the label f. Avoiding assignment at the cost of readability is to treat your code as being private. But code is supposed to be communicative.

This is not always easy if we don't have simple examples such as a function that adds values. As a side note, this is why functional programming advocates small functions with a single responsibility. When they have a single responsibility they are easier to implement, to test but also to label, and with a simple label, it's easier to reason about them, combine them with other labels and thus building a composite, more advanced function with greater specificity.