(The code of this blog post is available on GitHub)

Last year, I participated in the Global Day of Code Retreat. On this day, developers all over the world take implement Conway’s Game of Life under various constraints (such as “TDD as if you meant it”, pair programming without talking, can’t use functions that return values, etc) in order to practice the craft of software development.

The most fascinating constraint, to me, was to use no conditionals in the code. So no if statements, no while loops, no ternaries. But the code still has to be able to make decisions! The usual solution to this would be to use a lookup table. However, I wanted to try something a bit more ambitious: let’s implement the Game of Life using nothing but functions and function calls! In fact, let’s implement the GoL in the Lambda Calculus!

Because I don’t actually have a compiler for lambda expressions, I’m going to be using JavaScript as my implementation language.

Encoding the rules

The most important operation in the Game of Life is to determine the next cell state from the current one. The rules are as follows:

A cell lives in the next generation if either:

• It is currently alive and has 2 or 3 live neighbours
• It is currently dead and has 3 live neighbours

We need to implement some sort of counting mechanism to be able to make this distinction for cells. I’m going to use a stack of nested functions, that get progressively “peeled off” for every live neighbour, until the outermost function can be invoked to indicate whether the next state should be alive or dead.

Every function needs to be able to do two things: either return the next function in the chain (when we’re peeling) or return the current truth value that it represents (in a way similar to Church booleans). We do this by making each object a function, that will accept a function, which will be invoked with both the next function in the chain and the liveness state that the current function represents. The function we pass in will be used to select between the two cell operations.

We define the following functions:

var dies = function(next) { 
    return function(f, alive, dead) {
        return f(next, dead);
    }
};

var lives = function(next) {
    return function(f, alive, dead) {
        return f(next, alive);
    }
};

var nope = function(f, alive, dead) {
    return f(nope, dead);
};

dies indicates that the cell would die in the next generation, lives indicates that the cell would live in the generation, and nope also indicates that the cell would die in the next generation, while also indefinitely returning itself. nope will be used to terminate the table of possible living counts. Note that nope recursively refers to itself, which is not strictly speaking legal in the Lambda Calculus, but I’m going to be hand-wavy and say that’s ok. You could implement this using the U or Y combinator if you wanted to. However, JavaScripts supports the recursive call directly so why not use it: it’ll be easier to read. If this bothers you: fair warning, I’m going to be cheating a lot more down the line :).

We can now define the two cell states, alive and dead as follows:

//            # of live neighbours
//            0    1     2      3      4+
var alive = dies( dies( lives( lives( nope ))));
var dead  = dies( dies( dies ( lives( nope ))));

As you can see, the Game’s liveness rules are quite neatly encoded here. We still need a helper function to “peel off” the outer functions and a helper function to inspect the outermust function on our stack:

var advance = function(cell) {
    return cell(function(next, val) {
        return next;
    }, null, null);
}

var get = function(cell, alive, dead) {
    return cell(function(next, val) { 
        return val;
    }, alive, dead);
}

We can now use these functions to operate on cell states:

get(alive, 'lives', 'dies')                    // 0 neighbours: 'dies'
get(advance(advance(alive, 'lives', 'dies')))  // 2 neighbours: 'lives'
get(advance(advance(dead, 'lives', 'dies')))   // 2 neighbours: 'dies'

Determining the current cell state

A cell actually needs one more operation. We not only need to be able to determine the next cell state, we also need to know the current cell state, for two reasons:

• To be able to invoke advance on a cell for every live neighbour, we need to be able to tell if the neighbour is alive.
• To be able to draw the current state of the board on the screen, we need to know a cell’s liveness.

We actually already have a perfectly good way to do that: we can use the chainable Church Booleans that we already have for the “next state” calculation, and stick an additional one at the front of the chain to encode this extra piece of information!

We then establish the convention that the “head” function of a cell indicates its current state, and once we peel that off, what remains is the rule table for determining the next state based on the amount of live neighbours.

Although our operators are going to be the same, I’m going to define some aliases so their distinct purposes are made clear:

var yes   = lives;
var no    = dies;
var rules = advance;

And we redefine alive and dead with the new yes and no functions at the head:

//                   # of live neighbours
//                   0    1     2      3      4+
var alive = yes ( dies (dies (lives (lives (nope)))));
var dead  = no  ( dies (dies (dies  (lives (nope)))));

Now we can go on to implement the functions that, given a board composed of cells, will produce the next state of the board.

Calculating next states

Here, I’m starting to cheat a little more. I have no intention of reimplementing arrays and numerals in the lambda calculus, so I’m just going to borrow them from JavaScript. I think this is defensible, as the meat of the Game of Life logic is definitely implemented in nothing but the Lambda Calculus. And, most importantly: no conditionals!

First, we define a function to find the neighbours of a given cell. This is fairly straightforward, given that there are always 8 neighbours (with wrap-around at the edges). To keep the amount of JavaScript arrays used to a minimum, the list of neighbours will also be a nested set of functions, which when applied to a function will perform a fold (or reduce) operation using that function:

var L = function(y, next) {
    return function(x, f) {
        return next(f(y, x), f);
    }
}

var neighbours = function(x, y, board, N) {
    var cell = function(x, y) { return board[y * N + x]; };

    var x0 = (x + N - 1) % N,
        x1 = x,
        x2 = (x + 1) % N,
        y0 = (y + N - 1) % N,
        y1 = y,
        y2 = (y + 1) % N;

    return L(cell(x0, y0),
        L(cell(x1, y0),
        L(cell(x2, y0),
        L(cell(x0, y1),
        L(cell(x2, y1),
        L(cell(x0, y2),
        L(cell(x1, y2),
        L(cell(x2, y2), 
            I))))))));
}

We can now write the nextCell operation: given a cell and a list of neighbours, return the state of the cell in the next generation. Using the get operation to inspect the state of a cell, we retrieve either the advance function to advance in the rule table of the current cell, or the I (identity) function to keep our position in the rule table of the current cell. Finally, we use get to return either alive or dead based on our position in the rule table:

var I = function(x) { return x; }

var nextCell = function(cell, neighbours) {
    return get(neighbours(rules(cell), function(current, acc) {
        return get(current, advance, I)(acc);
    }), alive, dead);
}

Finally, the function to advance the state of an entire board is fairly straightforward and not very Lambda-y at all (since it mostly iterates over an array to call nextCell on it. To make it feel at least a little functional, I’m going to use Underscore.js’s map() function.

var nextBoard = function(board, N) {
    return _.map(board, function(cell, i) {
        var x = i % N;
        var y = Math.floor(i / N);

        var n = neighbours(x, y, board, N);
        return nextCell(board[i], n);
    });
}

And that’s it! We implemented Conway’s Game of Life, with not an if condition in sight, using (almost) nothing but function defintions and function calls!

Check out the complete source code on GitHub or view the online demo.