-
Notifications
You must be signed in to change notification settings - Fork 35
MM2 tutorial: Hexlife
Hexlife is a variant of Conway’s Game of Life played on a hexagonal grid rather than a square one. The rules are the following:
- A living cell with 0 or 1 living neighbors dies of loneliness.
- A living cell with 3 or more living neighbors dies of overpopulation.
- A dead cell with exactly 2 living neighbors becomes alive.
In short: if a cell has two neighbors it lives or revives, otherwise it dies or remains dead.
To get more intuition, check out this visual implementation of hexlife.
To model the hexagonal grid, we use cube coordinates, where each cell is represented as a triple (q r s). These coordinates obey a simple constraint: q + r + s = constant for all cells. Moving to a neighboring cell keeps one of the coordinates fixed, adds 1 to another, and distracts one from the third. The six neigbors of a cell with coordinates (q r s) are:
- (q+1, r, s-1)
- (q+1, r-1, s)
- (q, r-1, s+1)
- (q-1, r, s+1)
- (q-1, r+1, s)
- (q, r+1, s-1)
For a more elaborate explanation and helpful visualisations, check out this article on hexagonal coordinate systems.
In our MM2 implementation, we will use Peano numbers instead of integers. This structure allows us to express arithmetic through pattern matching rather than explicit addition and subtraction, which fits naturally with MM2’s rule‑rewriting model. Peano numbers encode natural numbers as repeated applications of a successor operator S to zero Z:
(peano 0 Z)
(peano 1 (S Z))
(peano 2 (S (S Z)))
(peano 3 (S (S (S Z))))
Note that it is also possible to implement hexlife using integers and integer operations.
As an example, consider a hexagonal grid in which cells (2 1 1), (1, 2, 1) and (1, 3, 0) are alive. We can express this in MM2 as follows:
(alive ((S (S Z)) (S Z) (S Z)))
(alive ((S Z) (S (S Z)) (S Z)))
(alive ((S Z) (S (S (S Z))) Z))
Note that we don't specify the dead cells. Every cell that is not marked as alive is considered dead.
We express the six cube-coordinate neighbor relations using MM2 rewrite rules:
(neighbors ($q $r (S $s)) ($q (S $r) $s))
(neighbors ($q $r (S $s)) ((S $q) $r $s))
(neighbors ($q (S $r) $s) ((S $q) $r $s))
(neighbors ($q (S $r) $s) ($q $r (S $s)))
(neighbors ((S $q) $r $s) ($q (S $r) $s))
(neighbors ((S $q) $r $s) ($q $r (S $s)))
The key rule of Hexlife, that a cell lives when it has exactly two neighbors, is encoded as:
(cell lives 2)
To take one step in the game of life, we start by counting all the alive neighbors of alive cells. We also count neighbors for dead cells adjacent to living ones, since dead cells can become alive.
These two steps can be executed at the same time.
(exec 0 (, (alive $co) (neighbors $co $nco) (alive $nco))
(O (count (anbs $co $k) $k $nco)))
(exec 0 (, (alive $co) (neighbors $co $nco) (neighbors $nco $nnco) (alive $nnco))
(O (count (anbs $nco $k) $k $nnco)))
The number of alive neighbors of the alive cells, and the neighbors of the alive cells will be added to the space.
Now we update the grid based on neighbor counts. We start by removing all alive cells in exec 1.
Next, we mark all cells that have two neighbors as alive in exec2.
(exec 1 (, (alive $co)) (O (- (alive $co))))
(exec 2 (, (anbs $co $c) (cell lives $c)) (O (+ (alive $co))))
Before the next iteration, we remove all neighbor-counting statements.
(exec 3 (, (anbs $co $c)) (O (- (anbs $co $c))))
We begin with the initial alive cells and neighbor rules:
(alive ((S (S Z)) (S Z) (S Z)))
(alive ((S Z) (S (S Z)) (S Z)))
(alive ((S Z) (S (S (S Z))) Z))
(neighbors ($q $r (S $s)) ($q (S $r) $s))
(neighbors ($q $r (S $s)) ((S $q) $r $s))
(neighbors ($q (S $r) $s) ((S $q) $r $s))
(neighbors ($q (S $r) $s) ($q $r (S $s)))
(neighbors ((S $q) $r $s) ($q (S $r) $s))
(neighbors ((S $q) $r $s) ($q $r (S $s)))
(cell lives 2)
(exec 0 (, (alive $co) (neighbors $co $nco) (alive $nco))
(O (count (anbs $co $k) $k $nco)))
(exec 0 (, (alive $co) (neighbors $co $nco) (neighbors $nco $nnco) (alive $nnco))
(O (count (anbs $nco $k) $k $nnco)))
(exec 1 (, (alive $co)) (O (- (alive $co))))
(exec 2 (, (anbs $co $c) (cell lives $c)) (O (+ (alive $co))))
(exec 3 (, (anbs $co $c)) (O (- (anbs $co $c))))
After the first two execution statements, all neighbor counts of alive cells, and the neighbor counts of their neighbors will be added.
(alive ((S (S Z)) (S Z) (S Z))) ; (2, 1, 1)
(alive ((S Z) (S (S (S Z))) Z)) ; (1, 3, 0)
(alive ((S Z) (S (S Z)) (S Z))) ; (1, 2, 1)
(anbs ((S (S (S Z))) (S Z) Z) 1)
(anbs ((S (S (S Z))) Z (S Z)) 1)
(anbs ((S (S Z)) (S (S Z)) Z) 3)
(anbs ((S (S Z)) (S Z) (S Z)) 1)
(anbs ((S (S Z)) Z (S (S Z))) 1)
(anbs ((S Z) (S (S (S Z))) Z) 1)
(anbs ((S Z) (S (S Z)) (S Z)) 2)
(anbs ((S Z) (S Z) (S (S Z))) 2)
(anbs (Z (S (S (S (S Z)))) Z) 1)
(anbs (Z (S (S (S Z))) (S Z)) 2)
(anbs (Z (S (S Z)) (S (S Z))) 1)
(cell lives 2)
(neighbors ((S $a) $b $c) ($a (S $b) $c))
(neighbors ((S $a) $b $c) ($a $b (S $c)))
(neighbors ($a (S $b) $c) ((S $a) $b $c))
(neighbors ($a (S $b) $c) ($a $b (S $c)))
(neighbors ($a $b (S $c)) ((S $a) $b $c))
(neighbors ($a $b (S $c)) ($a (S $b) $c))
(exec 1 (, (alive $co)) (O (- (alive $co))))
(exec 2 (, (anbs $co $c) (cell lives $c)) (O (+ (alive $co))))
(exec 3 (, (anbs $co $c)) (O (- (anbs $co $c))))
After execution statements one and two, the alive cells will be updated.
(alive ((S Z) (S (S Z)) (S Z))) ; (1, 2, 1)
(alive ((S Z) (S Z) (S (S Z)))) ; (1, 1, 2)
(alive (Z (S (S (S Z))) (S Z))) ; (0, 3, 1)
(anbs ((S (S (S Z))) (S Z) Z) 1)
(anbs ((S (S (S Z))) Z (S Z)) 1)
(anbs ((S (S Z)) (S (S Z)) Z) 3)
(anbs ((S (S Z)) (S Z) (S Z)) 1)
(anbs ((S (S Z)) Z (S (S Z))) 1)
(anbs ((S Z) (S (S (S Z))) Z) 1)
(anbs ((S Z) (S (S Z)) (S Z)) 2)
(anbs ((S Z) (S Z) (S (S Z))) 2)
(anbs (Z (S (S (S (S Z)))) Z) 1)
(anbs (Z (S (S (S Z))) (S Z)) 2)
(anbs (Z (S (S Z)) (S (S Z))) 1)
(cell lives 2)
(neighbors ((S $a) $b $c) ($a (S $b) $c))
(neighbors ((S $a) $b $c) ($a $b (S $c)))
(neighbors ($a (S $b) $c) ((S $a) $b $c))
(neighbors ($a (S $b) $c) ($a $b (S $c)))
(neighbors ($a $b (S $c)) ((S $a) $b $c))
(neighbors ($a $b (S $c)) ($a (S $b) $c))
(exec 3 (, (anbs $co $c)) (O (- (anbs $co $c))))
The last execution statement then removes all neighbor counts, preparing the space for a next iteration.
(alive ((S Z) (S (S Z)) (S Z))) ; (1, 2, 1)
(alive ((S Z) (S Z) (S (S Z)))) ; (1, 1, 2)
(alive (Z (S (S (S Z))) (S Z))) ; (0, 3, 1)
(cell lives 2)
(neighbors ((S $a) $b $c) ($a (S $b) $c))
(neighbors ((S $a) $b $c) ($a $b (S $c)))
(neighbors ($a (S $b) $c) ((S $a) $b $c))
(neighbors ($a (S $b) $c) ($a $b (S $c)))
(neighbors ($a $b (S $c)) ((S $a) $b $c))
(neighbors ($a $b (S $c)) ($a (S $b) $c))
- Add statements to the neighborhood definition to work with negative numbers. HINT:
(P $x), Z, (S $x) - Use the
(peano $n $pn)definition to import and export from and to human-readable coordinates. - Rewrite with the Axial coordinate system and integer coordinates.
- Add a loop that generates these rules for N steps. HINT: recursive exec OR metaprogramming