Cellular Automata in F#
Tags: fsharp, dotnet
Published: 2020-12-03 00:50:25

![Rule 90](https://dev-to-uploads.s3.amazonaws.com/i/h08rmsaxwmrg3f3lnqxw.png)

_Rule 90_

Simple rules can generate complex behaviour. I'm reading _A New Kind of Science_ by Stephen Wolfram. A key idea of the book is that a simple rule, applied iteratively, can generate complex behaviour. The difference between Rules 222, 90, and 30 are trivial, yet they generate vastly different results.

In this post we explore the principles and implement the Elementary Cellular Automata system in F#.

![Rule 222](https://dev-to-uploads.s3.amazonaws.com/i/vyidka3r3s5bklyf7vtz.png)

_Rule 222_

![Rule 30](https://dev-to-uploads.s3.amazonaws.com/i/94c098zraiay9ra0an4l.png)

_Rule 30_

## Cellular Automata

Here's a 7 x 4 grid. The dots represent Empty cells, the X represent Full cells. All of our grids start with a single Full cell in the middle of the top row.

    ...X...
    .......
    .......
    .......

We then define a rule. A rule is a function which decides whether a single cell is Empty or Full. This rule function takes values of the 3 cells from the row directly above, corresponding to the cells above and to the left (`1`), directly above (`2`), and above and to the right (`3`). We visualise this below. The cell we are trying to calculate is `?`.

    123....        .123...        ..123..        ...123.        ....123
    .?.....        ..?....        ...?...        ....?..        .....?.
    .......        .......        .......        .......        .......
    .......        .......        .......        .......        .......
    
The same rule is applied row after row. The rule is not applied to cells in the far left column and far right columns. These cells will always remain Empty. We'll look at the naming convention of rules later on, but for now here's one example.
    
Below is _Rule 222_. The first pattern is saying that if cells `1`, `2`, and `3` are Full, then the cell `?` will be Full. And so on, for every possible combination of those 3 cells.

    XXX    XX.    X.X    X..    .XX    .X.    ..X    ...
     X      X      .      X      X      X      X      .
     
This system of rules is as simple as we can get. Each cell can only have two possible states, and the value of the next cell only depends on it's neighbours.

## Rules as Code
We just described the Celluar Automata domain. Let's implement it in code. 

- A `Cell` can be either `Empty` or `Full`.
- The `Rule` type is a function which takes 3 `Cell`s and returns the value of a single `Cell`.


```fsharp
// A Cell is either Empty or Full
type Cell = Empty | Full

// Rules are functions which take in the values of 3 Cells, and return a single Cell value
type Rule = (Cell * Cell * Cell) -> Cell

// Rule 222 implemented in code
let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty
```

## Modelling the Grid
We've just described the Cellular Automata system in its entirety. Patterns and complexity emerge from just those rules. The rules by themselves are abstract and we need to apply them somehow. Here we apply the rule on a simple grid. But the same rule could be applied to any other surface - a 3D surface, mobius strip, or grid where the values wrap around.

Onto the implementing the system on a grid. Let's start off by generating the first row.

```fsharp
let generateStandardFirstRow (width: int) =
    
    if width % 2 = 0 then invalidArg "width" (sprintf "Value must be an odd number. Value passed was %d." width)
    
    Seq.init width (function
        | n when n = (width / 2) -> Full
        | _ -> Empty
    )
```

So

```fsharp
generateStandardFirstRow 7
```

Gives us

    Empty Empty Empty Full Empty Empty Empty

In order to generate the next row we only need to know the row before it. We take the previous row and apply `Seq.windowed`. This splits the row of `Cell`s into groups of 3 `Cell`s, which we need in order to calculate the next value.

Recall that our rule requires 3 cells in order to calculate the next value. This is the cell above and to the left, the cell directly above, and the cell above and to the right. This is a problem for the far left and far right columns of the grid. They only have 2 of the 3 cells required. To get around this we enforce a rule that the left column and right column will always remain `Empty`.

```fsharp
let generateNextRow (rule: Rule) (row: Cell seq) =
    let generatedCells =
        row
        |> Seq.windowed 3
        |> Seq.map (fun v ->
            rule (v.[0], v.[1], v.[2])
        )
        
    // the first and last Cells of each row are Empty since we didn't generate a value for them above
    seq {
        yield Empty
        yield! generatedCells
        yield Empty
    }
```

Now let's write a function which generates row after row. Sequences in F# are lazily evaluated. They're the C# `IEnumerable` type under the hood. By treating everything as a sequence we're essentially defining the rules as to how the grid will be generated.

`Seq.unfold` iteratively applies the `Rule` to whatever the previous row was, collecting results. Notice we don't specify how many rows to generate, that's up to the caller of this function.

```fsharp
let generatePattern (rule: Rule) (firstRow: Cell seq) = 
    firstRow
    |> Seq.unfold (fun row ->
        Some(row, (generateNextRow rule row))
        )
```

Now we can generate the grid!

```fsharp
let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule222 firstRow |> Seq.take 10
```

But we want to visualise it. Here's a basic ASCII renderer.

```fsharp
let drawCell = function
| Full -> "X"
| Empty -> "."

/// Render the grid to an ASCII string
let drawGrid (grid: Cell seq seq) =
    grid
    |> Seq.map (fun row ->
        row
        |> Seq.map drawCell
        |> String.concat ""
    )
    |> String.concat "\n"
    
drawGrid rows
```

    ..................................................X..................................................
    .................................................XXX.................................................
    ................................................XXXXX................................................
    ...............................................XXXXXXX...............................................
    ..............................................XXXXXXXXX..............................................
    .............................................XXXXXXXXXXX.............................................
    ............................................XXXXXXXXXXXXX............................................
    ...........................................XXXXXXXXXXXXXXX...........................................
    ..........................................XXXXXXXXXXXXXXXXX..........................................
    .........................................XXXXXXXXXXXXXXXXXXX.........................................

# Other Rules
Our algorithm works! Let's experiment with other rules.

```fsharp
let rule90: Rule = function
    | (Full, Full, Full) -> Empty
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Empty
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty
    
let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule90 firstRow |> Seq.take 50
let arrayOfRows = rows |> Seq.toArray
    
drawGrid rows
```

    ..................................................X..................................................
    .................................................X.X.................................................
    ................................................X...X................................................
    ...............................................X.X.X.X...............................................
    ..............................................X.......X..............................................
    .............................................X.X.....X.X.............................................
    ............................................X...X...X...X............................................
    ...........................................X.X.X.X.X.X.X.X...........................................
    ..........................................X...............X..........................................
    .........................................X.X.............X.X.........................................
    ........................................X...X...........X...X........................................
    .......................................X.X.X.X.........X.X.X.X.......................................
    ......................................X.......X.......X.......X......................................
    .....................................X.X.....X.X.....X.X.....X.X.....................................
    ....................................X...X...X...X...X...X...X...X....................................
    ...................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................................
    ..................................X...............................X..................................
    .................................X.X.............................X.X.................................
    ................................X...X...........................X...X................................
    ...............................X.X.X.X.........................X.X.X.X...............................
    ..............................X.......X.......................X.......X..............................
    .............................X.X.....X.X.....................X.X.....X.X.............................
    ............................X...X...X...X...................X...X...X...X............................
    ...........................X.X.X.X.X.X.X.X.................X.X.X.X.X.X.X.X...........................
    ..........................X...............X...............X...............X..........................
    .........................X.X.............X.X.............X.X.............X.X.........................
    ........................X...X...........X...X...........X...X...........X...X........................
    .......................X.X.X.X.........X.X.X.X.........X.X.X.X.........X.X.X.X.......................
    ......................X.......X.......X.......X.......X.......X.......X.......X......................
    .....................X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....................
    ....................X...X...X...X...X...X...X...X...X...X...X...X...X...X...X...X....................
    ...................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................
    ..................X...............................................................X..................
    .................X.X.............................................................X.X.................
    ................X...X...........................................................X...X................
    ...............X.X.X.X.........................................................X.X.X.X...............
    ..............X.......X.......................................................X.......X..............
    .............X.X.....X.X.....................................................X.X.....X.X.............
    ............X...X...X...X...................................................X...X...X...X............
    ...........X.X.X.X.X.X.X.X.................................................X.X.X.X.X.X.X.X...........
    ..........X...............X...............................................X...............X..........
    .........X.X.............X.X.............................................X.X.............X.X.........
    ........X...X...........X...X...........................................X...X...........X...X........
    .......X.X.X.X.........X.X.X.X.........................................X.X.X.X.........X.X.X.X.......
    ......X.......X.......X.......X.......................................X.......X.......X.......X......
    .....X.X.....X.X.....X.X.....X.X.....................................X.X.....X.X.....X.X.....X.X.....
    ....X...X...X...X...X...X...X...X...................................X...X...X...X...X...X...X...X....
    ...X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...
    ..X...............................X...............................X...............................X..
    .X.X.............................X.X.............................X.X.............................X.X.

# Image Output
Here's a graphical renderer for the same grid implementation.

```fsharp
#r "nuget:SixLabors.ImageSharp"
open SixLabors.ImageSharp;
open SixLabors.ImageSharp.PixelFormats;

let cols = 501;
let rows = 250;

let image = new Image<Rgba32>(cols, rows);
let white = new Rgba32(255F, 255F, 100F, 1F);
let black = new Rgba32(0f, 0f, 0f, 1F);

let grid =
    generateStandardFirstRow cols
    |> generatePattern rule90
    |> Seq.take rows

let withIndexes x = x |> Seq.mapi (fun index item -> (index, item))

for (rowIndex, row) in withIndexes grid do

    for (cellIndex, cell) in withIndexes row do

        let colour =
            match cell with
            | Full -> black
            | Empty -> white

        image.[cellIndex, rowIndex] <- colour

image.Save("rule90.png")
image
```

![Rule 90](https://dev-to-uploads.s3.amazonaws.com/i/aq8723qxbey44zan9cq3.png)

# Rules
So far we've looked at a few specific rules. But how many rules are there and can we generate them dynamically? We've hardcoded rules as functions

```fsharp
let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty
```

All rules must return a value for each pattern. Because the patterns are static we could think of identifying rules by what they return for each case, what is on the right hand side of the `->`. We could think of the above rule as:

    (Full, Full, Empty, Full, Full, Full, Full, Empty)
    
So a rule is a identified as a list of 8 boolean values. If we use binary to represent this we need a byte (8 bits) of information. This means there are 2^8 rules, giving us 256 possible rules in the Wolfram automata system.

So there are only 256 rules in this Wolfram automata system, and the rule's name determines what it returns. This is illustrated below. The binary pattern maps 1 to `Full` and 0 to `Empty`.

| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | Written Out                     | Rule |
| --- | -- | -- | -- | - | - | - | - | ------------------------------- | ---- |
|  1  | 1  | 0  | 1  | 1 | 1 | 1 | 0 | 128 + 64 + 16 + 8 + 4 + 2 + 1 = | 222  |
|  0  | 1  | 0  | 1  | 1 | 0 | 1 | 0 | 64 + 16 + 8 + 2 =               | 90   |


```fsharp
let generateRule(ruleNumber: byte) = 
    let ruleBitString = Convert.ToString(ruleNumber, 2).PadLeft(8, '0');

    let patternToBitStringIndex = function 
        | (Full, Full, Full) -> 0
        | (Full, Full, Empty) -> 1
        | (Full, Empty, Full) -> 2
        | (Full, Empty, Empty) -> 3
        | (Empty, Full, Full) -> 4
        | (Empty, Full, Empty) -> 5
        | (Empty, Empty, Full) -> 6
        | (Empty, Empty, Empty) -> 7

    let ruleFn (cells: Cell * Cell * Cell) = 
        let bitIndex = patternToBitStringIndex cells

        match ruleBitString.[bitIndex] with
        | '0' -> Empty
        | '1' -> Full
        | _ -> raise (Exception("Unexpected input"))
        
    ruleFn
    
let rule254 = generateRule(254uy)
rule254 (Empty, Empty, Empty)
```

And there we have it, our rule function generator. Here are some interesting rules.

## Rule 62

![Rule 62](https://dev-to-uploads.s3.amazonaws.com/i/f75gmk7omjw9areynzav.png)

## Rule 110

![Rule 110](https://dev-to-uploads.s3.amazonaws.com/i/rgxj04vlx1u71920wsnn.png)

## Rule 150

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ygxfmlmpcgjswv2easor.png)

# Conclusion
F# is a perfect language to implement Cellular Automata. The type system allows us to exactly model the domain, and sequences make the implementation elegant. There's no confusing cruft in our code. From this basic implementation you can easily make modifications to the Cellular Automata system. Here's a few fun things to try out. What if ...

- The first row was randomly generated
- Cells could have a value other than `Full` or `Empty`? 
- Rules incorporated some degree of randomness when deciding the value of the next cell?
- The grid was hexagonal rather than square based?

The Jupyter Notebook and an F# project containing the code for this post is available [here](https://github.com/lmortimer/automata).

This is part of F# Advent Calendar 2020. Check out other posts [here](https://sergeytihon.com/2020/10/22/f-advent-calendar-in-english-2020/).

# Further Reading
- [Cellular Automata](https://content.wolfram.com/uploads/sites/34/2020/07/cellular-automata.pdf) Los Alamos Science (1983) - Stephen Wolfram
- [Oh My Gosh, It’s Covered in Rule 30s!](https://writings.stephenwolfram.com/2017/06/oh-my-gosh-its-covered-in-rule-30s/) - Stephen Wolfram
- Stephen Wolfram on the Lex Fridman [podcast](https://www.youtube.com/watch?v=ez773teNFYA)
  - [Abridged clip](https://www.youtube.com/watch?v=VguG_y05Xe8) where they discuss Cellular Automata and Rule 30