python-lifelib 2.0.7

Algorithms for manipulating and simulating patterns in cellular automata

What is lifelib?
----------------

`lifelib` is a collection of algorithms for simulating and manipulating
patterns in cellular automata. It can be included in your project in
either of two ways:

- **Python package**: `lifelib` can be imported as a Python package,
and is compatible with both Python 2.7 and Python 3.5 (and beyond).

- **C++ header files**: if you have a project written in C++11 or above,
specific components of `lifelib` may be included. This approach is
used by the [apgsearch](https://gitlab.com/apgoucher/apgmera) soup
searcher and the [slmake](https://gitlab.com/apgoucher/slmake) glider
synthesis compiler. Note that `lifelib` is header-only.

How is lifelib structured?
--------------------------

The idea behind `lifelib` is a universal framework in which different
high-level **algorithms** such as Bill Gosper's Hashlife can seamlessly
integrate with different low-level **iterators** for running specific
rules on various architectures. There are currently three algorithms
supported by `lifelib`:

- **Hashlife**: This is the celebrated algorithm by Bill Gosper used
to gain exponential speedups by exploiting repeated structure in both
space and time. It operates directly on a compressed representation
called a _hashed quadtree_. Due to its efficiency, simplicity and
generality, this is recommended as the default algorithm.

- **Streamlife**: This is a new (2018) modification of Hashlife designed
to work efficiently on patterns containing antiparallel streams of
information-carrying gliders, such as certain self-replicating
machines. Streamlife works by disentangling a pattern into provably
non-interacting parts which can be run in separate 'universes'. This
algorithm is inspired by China Mieville's novel, _The City and The
City_, and borrows much of its terminology.

- **Tile-based**: Whereas the other algorithms are best for patterns
exhibiting regular behaviour, this is well-suited for running random
patterns. It is only available in the C++ version of `lifelib` and
is aimed at [apgsearch](https://gitlab.com/apgoucher/apgmera), which
runs random soups in a Monte Carlo fashion and logs their eventual
decay products. The tile-based algorithm optimises for areas of the
universe that do not change, excluding them from future calculations
until necessary.

Whereas the Streamlife implementation is only suited to Conway's Game of
Life and close variants thereof, the other two algorithms (Hashlife and
tile-based) are fully compatible with every `lifelib` iterator.

In `lifelib`, an **iterator** is an efficient low-level implementation of
a cellular automaton, which runs on a $`32 \times 32`$ grid and returns
the central $`16 \times 16`$ subgrid after one or more generations. The
philosophy behind `lifelib` is that any of these iterators can seamlessly
plug into either the Hashlife or tile-based algorithm, 'upgrading' it
from a small $`32 \times 32`$ universe to an unbounded universe.

The iterators themselves are written mostly in C and inline assembly
language, specifically tailored to your machine's instruction set and to
the cellular automaton being simulated. Iterators are generated by Python
modules called **genera** (singular: genus), each one of which targets a
specific family of related rules. At the moment, `lifelib` contains eight
different genera, but there is nothing to prevent you from adding more
of your own:

- **b3s23life**: This genus supports only one rule, namely Conway's Game
of Life, and produces iterators with remarkably low instruction counts
(and concomitantly high speed!). It can yield iterators compatible with
either AVX-512, AVX2, AVX, or SSE, and chooses the most advanced
instruction set supported by your processor.

- **lifelike**: This genus is more general, and supports any 2-state
outer-totalistic cellular automaton on the Moore neighbourhood. It can
produce optimised code for either AVX2, AVX, or SSE. As with b3s23life,
this genus uses bitwise parallelism and vectorisation to compute many
cells simultaneously.

- **isotropic**: This is again more general, supporting any isotropic
2-state Moore-neighbourhood cellular automaton. It is not as fast as
the lifelike genus, as it is not vectorised and instead computes 8 cells
at a time using a lookup table.

- **ltl**: A SSSE3-based byte-parallel implementation of Kellie Evans'
_Larger than Life_ cellular automata. It supports square neighbourhoods
with a radius up to 7 (i.e. $`15 \times 15`$).

- **generations**: A multistate generalisation of lifelike. Internally, it
uses the vectorised lifelike iterator as a subroutine.

- **isogeny**: A multistate generalisation of isotropic.

- **gltl**: A multistate generalisation of Larger than Life.

- **bsfkl**: Brian Prentice's 3-state BSFKL rules generalise both 3-state
Generations rules and outer-totalistic cellular automata.

The design of `lifelib` restricts iterators to have a maximum neighbourhood
radius of 8 and a maximum of $`2^{64}`$ states. (Note that this is a proper
superset of the custom rules supported by Golly's RuleLoader, which are
restricted to a radius of 1 and a maximum of 256 states.)

System requirements
-------------------

For `lifelib` to work, you need a computer with an **x86-64 processor**.
This includes most personal computers, but not smartphones, tablets, or the
Raspberry Pi.

It runs easily in a POSIX environment, such as:

- Linux / Unix;
- Mac OS X;
- Windows (using Cygwin);
- Windows 10 (using WSL);

and requires a C++ compiler (gcc or clang) and Python (ideally with numpy).

The Python version of `lifelib` can actually run in Windows' native Python
(e.g. Anaconda). A suitable Cygwin installation still needs to exist on the
machine and be locatable by `lifelib`.

Installation
------------

If you are including `lifelib` as part of a project, it does not necessarily
need 'installing' _per se_. Instead, you can clone `lifelib` into your
project's directory:

cd path/containing/your/project
git clone https://gitlab.com/apgoucher/lifelib.git

It can be accessed from with a Python script using:

import lifelib

or from within a C++11 program using (for example):

#include "lifelib/pattern2.h"

Example usage (Python)
----------------------

This is essentially the 'Hello World' of `lifelib`, and takes a small chaotic
pattern (called Lidka) and runs it 30000 generations in Conway's Game of Life.
It prints both the initial and final populations.

import lifelib
sess = lifelib.load_rules("b3s23")
lt = sess.lifetree()
lidka = lt.pattern("bo7b$obo6b$bo7b8$8bo$6bobo$5b2obo2$4b3o!")
print("Initial population: %d" % lidka.population)
lidka_30k = lidka[30000]
print("Final population: %d" % lidka_30k.population)

This should print 13 as the initial population and 1623 as the final
population.

Now, let us walk through what happens in the code.

- The first line imports the Python package. This is a lightweight operation
so does not take a perceptible amount of time.

- The second line is by far the most subtle. It takes in one or more rules
(in this case, "b3s23" is the systematic name for Conway's Game of Life:
birth on three neighbours and survival on two or three neighbours) and
creates a lifelib 'session' capable of running those rules. This is a
healthy abstraction designed to obscure what `load_rules()` _really_ does,
which is the following:

- Checks to see whether there is already a compiled `lifelib` shared
library with the desired ruleset. If so, it checks its version against
the Python package's version to ensure that it's current, and otherwise
ignores it and proceeds:

- Finds the highest-priority genus which supports the rule. In this case,
it is the **b3s23life** genus, which can generate optimised C and
assembly code to take advantage of instruction sets up to AVX-512. The
genus is then invoked to create the rule. (If multiple rules have been
specified, this step is repeated for each rule.)

- Generates some extra 'glue code' to include all of the rule iterators
into the `lifelib` source code.

- Compiles the file `lifelib.cpp` using a C++ compiler (g++ or clang)
into a shared library called `lifelib_b3s23.so` (even though if this
is Windows, it's actually a DLL masquerading under the extension .so).
This step is the most time-consuming, because the C++ compiler must
compile tens of thousands of lines of code (C++11, C, and assembly)
and optimise it for your machine. Typically this will take 10 or 20
seconds to complete.

- Dynamically loads the `lifelib_b3s23.so` shared library into the
running process. (If you are on Windows and running outside Cygwin,
this is loaded into a Cygwin subprocess instead, with interprocess
communication pipes used to bridge the rift. Fortunately, this
indirection is invisible to you, provided everything is configured
correctly.)

- The third line now creates a **lifetree** (hashed quadtree) in the
session, allowed to use up to 1000 megabytes of memory before garbage
collecting. All of our patterns reside in this lifetree, and they
automatically take advantage of mutual compression. This means that
if a structure occurs many times in many patterns, it will only be
stored once in the compressed container.

- The fourth line creates a pattern (finitely-supported configuration of
cells inside an unbounded plane universe) called Lidka, which has 13
live cells. The pattern is specified in a format called Run Length
Encoded (or RLE), which is the standard for sharing patterns in cellular
automata.

- The fifth line reports the population of Lidka, and should print 13. The
.population property calls lifelib code to compute the population of the
pattern by recursively walking the quadtree.

- The sixth line runs Lidka 30000 generations in Bill Gosper's Hashlife
algorithm. On a modern machine, this should take less than 100 milliseconds
owing to the speed of the b3s23life iterator. This is not done in-place,
so a new object `lidka_30k` is returned without modifying the original
`lidka` object.

- The seventh line reports the population of the pattern `lidka_30k`. This
should be exactly 1623.

That's it! You've now simulated your very first pattern in Hashlife!

Editing features
----------------

In addition to running patterns, `lifelib` has extensive support for editing
patterns. In particular, the following operations are included:

- Shifting, rotating, and reflecting patterns.
- Boolean set operations such as union, intersection, difference, symmetric
difference.
- Slicing rectangular subregions.
- Convolutions (either using inclusive or exclusive disjunction).
- Getting and setting individual cells or arrays thereof.
- Pattern-matching capabilities such as find and replace.
- Kronecker products.

The Python interface allows arbitrarily large integers to be used for shifts
and getting/setting coordinates of individual cells. Manipulating arrays of
cells is restricted to 64-bit integers, and requires `numpy` to be installed,
but is much faster.

Both the Python and C++ versions of `lifelib` use operator overloading for
editing patterns, and are consistent with each other:

- Two patterns can be added (elementwise bitwise OR) by using `|` or `+`.
The in-place assignment operators `|=` and `+=` also work. For two-state
patterns viewed as sets of cells, this coincides with union / disjunction.

- Patterns can be subtracted (elementwise bitwise AND-NOT) by using `-` or
its in-place form `-=`.

- The intersection / conjunction (elementwise bitwise AND) is exposed
through the operator `&` and its in-place form `&=`.

- Exclusive disjunction can be performed using the caret operator `^` and
its in-place form `^=`.

- The Kronecker product of two patterns can be perfomred using `*`.

- A pattern may be shifted using either `pattern.shift(30, -20)` or the
more concise `pattern(30, -20)`. The latter syntax can have a third
parameter prepended to allow transformations, such as counter-clockwise
rotation using `pattern("rccw", 0, 0)`.

- The square brackets operator advances a pattern in the current rule for
the specified number of generations.

In Python, a pattern can also be viewed as an associative array mapping
coordinate pairs to the state, and manipulated as such. The `__getitem__`
and `__setitem__` methods (square brackets operator as an rvalue and lvalue
respectively) support the following:

lidka[-3:5, 8:20] # for specifying an 8-by-12 rectangular region
lidka[7893, -462] # for specifying an individual cell
lidka[np.array([[3, 4], [2, 1], [69, -42]])] = np.array([1, 0, 1])

The first of these returns a pattern and supports assignment from either a
pattern or an int (in which case it block-fills the rectangle with that
state). The second returns an int and supports assignment from an int. The
third returns and supports assignment from a numpy array of the same length.
The numpy array syntax can only specify 64-bit signed coordinates (each
coordinate is limited to the interval $`\pm 9 \times 10^{18}`$ ), whereas
the other two syntaxes allow pairs of arbitrarily large ints to be used.

Loading/saving files
--------------------

Both the macrocell and RLE file formats from Golly are supported by `lifelib`
for both reading and writing files; moreover, they have been generalised to
support up to $`2^{64}`$ states. The Python version of `lifelib` also allows
the reading and writing of compressed files (.rle.gz and .mc.gz). The easiest
way to use this is:

lidka.save('lidka.rle')
lidka_reloaded = lt.load('lidka.rle')

Unless otherwise specified, file format is inferred from the extension.

Jupyter notebook support and LifeViewer integration
---------------------------------------------------

If you are running `lifelib` in Python from a Jupyter notebook, you can view
a pattern in Chris Rowett's LifeViewer by calling the pattern's `.viewer()`
method:

lidka.viewer()

In Internet Explorer, the lack of support for data URIs means that you need
to use the antiquated option:

lidka.viewer(base64=False)

which is worse because 'downloading' the notebook as HTML does not preserve
the embedded LifeViewers in the latter case.

Note that you need internet access for this to work, because the LifeViewer
JavaScript code is sourced from `conwaylife.com`.

Future directions
-----------------

- Currently lifelib is specific to 64-bit x86 architecture; ideally
support for other architectures will be introduced.