Cafe au Life

What

Cafe au Life is an implementation of John Conway's Game of Life cellular automata written in CoffeeScript. Cafe au Life runs on Node.js, it is not designed to run as an interactive program in a browser window.

Cafe au Life's Github project is here.

This file, cafeaulife.coffee contains the core engine for computing the future of any life universe of size 2^n | n > 1. The algorithm is optimized for computing very large numbers of generations of very large and complex life patterns with a high degree of regularity such as implementing Turing machines.

As such, it is particularly poorly suited for animating displays a generation at a time. But it is still a beautiful algorithm that touches on the soul of life’s “physics."

(A period 24 Glider Gun. Gliders of different periods are useful for synchronizing signals in complex Life machines.)

Conway's Life and other two-dimensional cellular automata

The Life Universe is an infinite two-dimensional matrix of cells. Cells are indivisible and are in either of two states, commonly called "alive" and "dead." Time is represented as discrete quanta called either "ticks" or "generations." With each generation, a rule is applied to decide the state the cell will assume. The rules are decided simultaneously, and there are only two considerations: The current state of the cell, and the states of the cells in its Moore Neighbourhood, the eight cells adjacent horizontally, vertically, or diagonally.

Cafe au Life implements Conway's Game of Life, as well as other "life-like" games in the same family.

Why

Cafe au Life is based on Bill Gosper's brilliant HashLife algorithm. HashLife is usually implemented in C and optimized to run very long simulations with very large 'boards' stinking fast. The HashLife algorithm is, in a word, a beautiful design, one that is "in the book." To read its description is to feel the desire to explore it on a computer.

Broadly speaking, HashLife has two major components. The first is a high level algorithm that is implementation independent. This algorithm exploits repetition and redundancy, aggressively 'caching' previously computed results for regions of the board. The second component is the cache itself, which is normally implemented cleverly in C to exploit memory and CPU efficiency in looking up precomputed results.

Cafe au Life is an exercise in exploring the beauty of HashLife's recursive caching or results, while accepting that the performance in a JavaScript application will not be anything to write home about relative to hard core implementations. It's still incredible relative to brute force, which is a testimony of the importance of algorithms over implementations.

Cafe au Life is divided into modules:

• The Universe Module introduces the Cell and Square classes that implement the Quadtree.
• The Future Module provides methods for computing the future of a square in the Quadtree, making full use of recursion.
• The Canonicalization Module implements a very naive hash-table for canoncial representations of squares. HashLife uses extensive canonicalization to optimize the storage of very large patterns with repetitive components. Without the cache, the space required to store a pattern would be larger in HashLife than in a naïve matrix.
• The Memoization Module stores the results of computing the future of squares. Just as the Canonicalization Module compresses HashLife's space requirements through looking up precomputed squares, the Memoization Module compresses HashLife's execution time requirements by looking up precomputed results.
• The Garbage Collection Module implements a simple reference-counting garbage collector for the cache. For more information, read Implementing Garbage Collection in CS/JS with Aspect-Oriented Programming
• The API Module provides methods for grabbing json or strings of patterns and resizing them to fit expectations.
• The Menagerie Module provides a few well-know life objects predefined for you to play with. It is entirely optional.

The modules will build up the functionality of our Cell and Square classes.

The first time through

If this is your first time through the code, start with the universe module, and then read the future module to understand the core algorithm for computing the future of a pattern. You can look at the canonicalization and memoization modules next to understand how Cafe au Life runs so quickly. Review the garbage collection, menagerie, and API modules at your leisure, they are incidental to the core idea.

Todo List

TODO: Extract futures module so that it can run in naïve brute force mode without it. This means finding a way to generalize '.succ'. With the future module removed, it should still use a Quadtree, but not cache results and notlook more than one generation into the future. The Quadtree is then simply a space-saving measure.

TODO: Support changing the rules during a run. The Canonicalization Module will have to clear the cache.

TODO: Decouple canonicalization so that it can work with or without the Canonicalization Module. If the Canonicalization Module is removed, it should work VERY slowly.

Who

When he's not shipping Ruby, Javascript and Java applications scaling out to millions of users, Reg "Raganwald" Braithwaite has authored libraries for Javascript and Ruby programming such as Katy, JQuery Combinators, YouAreDaChef, andand, and more you can find on Github.

He has written three books:

• Kestrels, Quirky Birds, and Hopeless Egocentricity: Raganwald's collected adventures in Combinatory Logic and Ruby Meta-Programming
• What I've Learned From Failure: A quarter-century of experience shipping software, distilled into fixnum bittersweet essays
• How to Do What You Love & Earn What You’re Worth as a Programmer

His hands-on coding blog Homoiconic frequently lights up the Hackerverse, and he also writes about project management and other subjects.

(c) 2012 Reg Braithwaite (@raganwald)

Cafe au Life is freely distributable under the terms of the MIT license.

The annotated source code was generated directly from the original source using Docco.