HashLife. On Node.
View the Project on GitHub recursiveuniverse/recursiveuniverse.github.com
Café au Life is an implementation of John Conway's Game of Life cellular automata written in CoffeeScript. Café au Life runs on Node.js, it is not designed to run as an interactive program in a browser window.
The annotated source code is the best way to explore the algorithm.
Café au Life implements Bill Gosper's HashLife algorithm. HashLife exploits regularity, so for certain life patterns, it runs at super-linear speed. It's a beautiful algorithm!
If you set up a Glider Gun when the Earth was first formed 4.5 billion years ago, and ran one generation per second, in the 143.4 quadrillion seconds that have elapsed since then, the pattern would grow to 23,900,000,000,000,036 live cells.
Café au Life takes just under two seconds to boot up, and another second to calculate the state of the pattern after 143.4 quadrillion generations. If you haven't seen how the algorithm works, you owe it to yourself to read the annotated source code.
You can try Cafe au Life: Install CoffeeScript and node.js, clone the repository, then use the REPL from the command line:
$ coffee
coffee> Life = require('./lib/cafeaulife').set_universe_rules()
coffee> gun = require('./lib/menagerie').gospers_glider_gun
coffee> gun.future_at_time(143400000000000000).population
23900000000000036
coffee>
You can also play with a browser-based version at raganwald.com/hashlife.
Have fun!
Yes.
Williams, Master of the "Come From" is a short work of fiction that introduces the idea of aggressively separating concerns into separate modules. Café au Life was written in part to explore the "Williams Style" and see how it would play out when writing a non-trivial program.
Implementing Garbage Collection in CS/JS with Aspect-Oriented Programming is an experience report describing the refactoring and programming necessary to add garbage collection to Café au Life.
One of the most important questions we ask ourselves is whether a non-trivial machine can be constructed that reproduces itself. If the answer is "no," then we can reason that for any machine, there must be a factory or creator outside of the machine. That goes for humans and all life. If the answer is "yes," then we can reason that it is not necessary for there to be a factory or creator for every machine, including ourselves.
Cellular automata patterns are a kind of machine, with properties close enough to physical machines that it is very easy to reason by correspondence: If such-and-such is possible for a cellular automaton, it must be possible for a physical machine, therefore research into the capabilities of cellular automata is an important part of research into the capabilities of machines, including our bodies and our brains.
Life theorists have proven all sorts of things about what ought to be possible with Life patterns. Life experimenters have taken it to the next level and have built Universal Turing Machines, self-replicating machines, and all sorts of things that demonstrate the universality of Conway's Game of Life. Implementations that can handle very large and/or very long-running Life patterns are an important tool for experimentation.
If you'd like to read more, the most approachable book on the subject is William Poundstone's brilliant The Recursive Universe. Beg, borrow, or steal a copy, new or used. Get it in hardcover while you still can.
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 a popular programming blog, as well as the books CoffeeScript Ristretto, JavaScript Allongé, and others on programming and programming languages.
(c) 2012 Reg Braithwaite (@raganwald)
Café 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.