Well, now that my senior year of high school is over, the original reason for this blog’s existence (a yearlong class assignment) is gone. However, blogging seems to be a pretty popular thing to do these days, so I think I’ll try to continue with it. If this goes on for long enough, I’ll need to change the website layout, but I’ll worry about that if it comes to that.
Anyway, the topic of this post is elemetary cellular automata. If you are also an undergraduate at CMU, you may recognize this topic from DMP (15-051)! Actually, this blog post came about because I decided, for whatever reason, to write my DMP ECA code in Haskell. I am actually quite bad at Haskell, but if I blog enough about it, maybe one day I’ll be good at it. (Or maybe after taking 15-150.)
Just a warning: the code in this blog post does expect UTF-8. If your environment can’t handle UTF-8…I mean, it’s 2019. If my Linux TTY can handle it, so can your terminal emulator. If this is really a problem, the code should be easy enough to edit to use ASCII approximations. I’ll try to remember to point this out in the narrative.
introduction
Since most people who would actually read my blog are probably more familiar with this topic than I am, I’ll keep this fairly short. This content may or may not be straight from DMP.
Let’s say we have a string of cells, each of which can be in a state 0 or 1. Okay, that’s just a boring bitstring. Let’s add a local rule which specifies how each cell evolves. In order to keep things simple, we’ll require that each cell’s new state be only a function of its current state and the current states of its two neighbors. To keep things even simpler, we’ll allow a cyclic boundary condition in which the ends of the string wrap around, so that no cell is without two neighbors. In this way, we can easily establish a global rule, which states that the entire string evolves by simultaneously applying the local rule to each individual cell.
Well, there are only 23 = 8 possible configurations of three adjacent cells. Our local rule functions as a lookup table, mapping each possible configuration to one of two new states. Thus, there are only 28 = 256 possible local rules. This may seem pretty boring, but surprisingly complex emergent behavior can appear in the global rule, even with a very simple, deterministic local rule.
This blog post will present a short Haskell program that demonstrates this by simulating a given local rule.
defining our types
Let’s start by defining the main types that will be used by our program. Each cell in an ECA must be in one of two states, so it seems natural to use a Bool to represent it. A configuration of the cellular automaton is just a list of cells:
type Cell = Bool
type Config = [Cell]
Recall that a local rule will return an updated value of a cell based on the current states of a cell and its two neighbors. We’ll define a LocalRule to be a function that does exactly that:
-- a LocalRule takes: (a cell) -> (left neighbor) -> (right neighbor) -> (new cell)
type LocalRule -> Cell -> Cell -> Cell -> Cell
For example, a simple local rule is to take the two neighboring cells and xor them. This can be written concisely as:
xor :: LocalRule
xor _ = (/=)
Here, we also see the advantage of choosing the argument order (cell) -> (left neighbor) -> (right neighbor): it makes it slightly more convenient to partially apply functions.
writing the global rule
Our global rule is simple: update the configuration by applying the local rule to each individual cell. This suggests the definition of the function global:
global :: LocalRule -> Config -> Config
global rule config =
map (local config) [0..hi]
where
local config index =
let len = length config
cell = (!!) config index
left = (!!) config $ mod (index + len - 1) len
right = (!!) config $ mod (index + 1) len
in rule cell left right
hi = length config - 1
We use modular arithmetic to implement the cyclic boundary condition and use a list of indices to pick out individual cells in the configuration. At this point, we can test our simulation with the simple xor rule:
λ> global xor [False, True, False]
[True, False, True]
which updates 010 → 101 as expected.
the simulation code
Now that we have at least a functioning single-step simulation, the next thing we want to do is write code to apply the global rule an arbirtrary number of times. First up, the whole [False, True, False] format is difficult to read. Let’s define some functions to make the simulation output slightly more bearable. The traditional method of showing the output of a cellular automaton is to use a sequence of blocks, so we’ll write a function called blockify to convert a configuration to a string of blocks. We’ll also frame the blocks with a pretty border.
blockify :: Config -> [Char]
blockify config =
"│" ++ (map (\x -> if x then '█' else ' ') config) ++ "│"
frame :: [Char] -> [Char]
frame content =
top ++ content ++ bottom
where
len (x:xs) = if x == '\n' then 0 else 1 + (len xs)
horizontal = take (len content - 2) $ repeat '─'
top = "┌" ++ horizontal ++ "┐\n"
bottom = "\n└" ++ horizontal ++ "┘"
Okay, now for the actual running the code. When we simulate the cellular automaton, we would like to take a local rule, an initial configuration, and a simulation depth and print out a pretty picture of how the automaton evolves.
simulate :: LocalRule -> Config -> Int -> IO ()
simulate rule initial depth =
putStrLn $ frame $ run (global rule) initial depth
where
run rule initial 0 = blockify initial
run rule initial n =
(blockify initial) ++ "\n" ++ (run rule (rule initial) (n - 1))
And, to verify that this works, let’s try it on the xor rule:
λ> simulate xor [False, False, False, False, True, False, False, False, False] 4
┌─────────┐
│ █ │
│ █ █ │
│ █ █ │
│ █ █ █ █ │
│█ █│
└─────────┘
To summarize what we have so far: we can define a new local rule like:
xor_all :: LocalRule
xor_all cell left right = (cell /= left) /= right
And we can simulate it with a given starting configuration and depth like:
λ> simulate xor_all [False, True, False, False, False, False, False] 4
┌───────┐
│ █ │
│███ │
│ █ █ █│
│ █ ████│
│ █ ██ │
└───────┘
automating rules
We can easily define a new LocalRule with an explicit formula in our code. However, there are some rules that are not so nice to explicitly write out, and playing with all 256 possible rules is rather tedious. We’d like to have some way of automatically generating a local rule based on a numeric code 0 ≤ x ≤ 255.
Actually, there is already a standard numeric code for each possible local rule of an elementary cellular automaton: Wolfram codes. Taken from Wikipedia, here is how we decipher the code for, for instance, Rule 110:
- Write 110 in binary. This becomes
01101110. - Each binary digit is the new state for a cell in a certain configuration. All eight possible combinations of three cells
(left, center, right)are listed in decreasing order and paired with a digit in the rule code.
So, for Rule 110, if a cell and its neighbors are in the 111 configuration, the center cell will evolve into the 0 state. All of these patterns for Rule 110 are listed below:
| Current State | New State |
|---|---|
| 111 | 0 |
| 110 | 1 |
| 101 | 1 |
| 100 | 0 |
| 011 | 1 |
| 010 | 1 |
| 001 | 1 |
| 000 | 0 |
Since this is already a standardized code, it would be nice to have a function that could automatically generate the appropriate LocalRule with a simple invocation like rule 90. We first need to convert a number into a list of binary digits:
-- rounded log base 2 of an integer
log2 :: Int -> Int
log2 x = floor $ log (fromIntegral x) / log 2
-- expand, e.g. 12 -> [1, 1, 0, 0]
binary_expand :: Int -> [Int]
binary_expand n =
bin_exp_aux n $ log2 n
where
bin_exp_aux x d
| d < 0 = []
| x >= 2^d = 1 : bin_exp_aux (x - 2^d) (d - 1)
| otherwise = 0 : bin_exp_aux x (d - 1)
We need to force that list to be of length eight, whether that means zero-padding or chopping off bits (which shouldn’t happen on valid inputs, but it’s good to plan):
-- force binary number to length 8, chopping off upper bits if needed
pad8 :: [Int] -> [Int]
pad8 num
| length num <= 8 = pad ++ num
| length num > 8 = drop len num
where
len = abs $ 8 - (length num)
pad = take len $ repeat 0
Now we can write a function rule to generate a LocalRule from its Wolfram code, essentially serving as a lookup table.
-- make a LocalRule from its Wolfram code
rule :: Int -> LocalRule
rule n =
\cell left right ->
(map to_bool $ pad8 $ binary_expand n) !! (7 - cell_as_num cell left right)
where
to_num x = if x then 1 else 0
to_bool = not . (== 0)
cell_as_num c l r =
sum $ map (\(x,y) -> 2^x * y) $ zip [0..] $ map to_num [l, c, r]
preset starting configurations
The last thing we’ll do is define some pre-set initial configurations. It’s pretty annoying to type [False, True, False, ...] each time we want to run something. Let’s define a few lengths and configurations:
-- useful lengths
width = 77 :: Int -- does not include border or center
halfwidth = floor $ (fromIntegral width) / 2
half = take halfwidth $ repeat False
-- some popular initial configurations
center, leftmost, rightmost, alternate :: Config
center = half ++ [True] ++ half
leftmost = [True] ++ half ++ half
rightmost = half ++ half ++ [True]
alternate = foldl (++) [] $ take halfwidth $ repeat [True, False]
simulating rules
Yay, we can now simulate arbitrary rules easily! Let’s give an example with the previous xor function, which is equivalent to rule 90.
λ> simulate (rule 90) center 38
┌─────────────────────────────────────────────────────────────────────────────┐
│ █ │
│ █ █ │
│ █ █ │
│ █ █ █ █ │
│ █ █ │
│ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ │
│ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ │
│ █ █ │
│ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ │
│ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ │
│ █ █ │
│ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│ █ █ █ █ │
│ █ █ █ █ █ █ █ █ │
│█ █ █ █ █ █ █ █│
└─────────────────────────────────────────────────────────────────────────────┘
Wow, a pretty fractal! (If the text is garbled in your browser, this image shows what it’s supposed to look like.) This shows how surprisingly complex behavior can emerge from a very simple local rule. Here’s another famous example: Rule 110, which somehow turns out to be computationally universal.
λ> simulate (rule 110) leftmost 76
┌─────────────────────────────────────────────────────────────────────────────┐
│█ │
│██ │
│███ │
│█ ██ │
│█████ │
│█ ██ │
│██ ███ │
│███ █ ██ │
│█ ███████ │
│███ ██ │
│█ ██ ███ │
│█████ █ ██ │
│█ ██ █████ │
│██ ███ █ ██ │
│███ █ ████ ███ │
│█ █████ ██ █ ██ │
│███ ██ ████████ │
│█ ██ ████ ██ │
│█████ █ ██ ███ │
│█ ████ ███ █ ██ │
│██ █ ███ ██ █████ │
│███ ██ █ █████ █ ██ │
│█ ████████ ██ ██ ███ │
│███ ██ ██████ █ ██ │
│█ ██ ███ █ ███████ │
│█████ █ ████ █ ██ │
│█ ██ ███ ██ ██ ███ │
│██ ███ █ ██ ███ ███ █ ██ │
│███ █ ██ ██████ ███ ██ █████ │
│█ ████████ ███ █████ █ ██ │
│███ ██ █ ███ ████ ███ │
│█ ██ ███ ███ ██ █ ██ █ ██ │
│█████ █ ██ █ █████ ██ ████████ │
│█ ██ ████████ ██████ ██ │
│██ ███ █ ██ █ ██ ███ │
│███ █ ██ ██ ███ ██ ███ █ ██ │
│█ ██████████ █ █████ █ ██ █████ │
│███ ██ ███ ██ █████ █ ██ │
│█ ██ ███ █ ██ ████ ██ ██ ███ │
│█████ █ ██ █████ █ ██ ██████ █ ██ │
│█ ██ ██████ ████ ███ █ ███████ │
│██ ███ █ ██ █ ███ ████ █ ██ │
│███ █ ██ ██ ███ ██ █ ███ ██ ██ ███ │
│█ ███████ ███ █ ████████ ██ ███ ███ █ ██ │
│███ ██ █ ██ ███ ██████ ███ ██ █████ │
│█ ██ █████████ ██ █ ███ █████ █ ██ │
│█████ █ █████ ██ █ ███ ████ ███ │
│█ ██ ██ █ ██ ███ ███ ██ █ ██ █ ██ │
│██ ███ ███ ██ ███ █ ██ █ █████ ██ ████████ │
│███ █ ███ ██ ███ █ ██ ████████ ██████ ██ │
│█ █████ █████ █ ████████ ██ █ ██ ███ │
│███ ███ ██ ███ ██ ███ ██ ███ █ ██ │
│█ ██ █ ██ ███ █ ██ ███ █ █████ █ ██ █████ │
│█████ █████ █ ███████ █ ██ ███ ██ █████ █ ██ │
│█ ███ █████ ██ █████ █ ██ ████ ██ ██ ███ │
│██ █ ██ █ ██ ███ █ ██ █████ █ ██ ██████ █ ██ │
│███ █████ ██ ███ █ ██ ██ ████ ████ ███ █ ███████ │
│█ ███ █████ █ ██ ████████ █ ██ █ ███ ████ █ ██ │
│███ ██ █ ███████ █ ████ ███ ██ █ ███ ██ ██ ███ │
│█ █████ ██ █ ████ █ ███ ████████ ██ ███ ███ █ ██ │
│███ █████ ██ █ ██ ██ █ ███ ██████ ███ ██ █████ │
│█ ██ █ █████ ██ ███ ██████ ██ █ ███ █████ █ ██ │
│█████ ██ █ ██ ████ ██ █ █████ ██ █ ███ ████ ███ │
│█ █████ ██ ███ █ █████ ██ █ ██ ███ ███ ██ █ ██ █ ██ │
│██ █ █████ █ ████ █ █████ ██ ███ █ ██ █ █████ ██ ████████ │
│███ ██ █ █████ ████ █ ██ ███ █ ██ ████████ ██████ ██ │
│█ █████ ██ █ ██ █ ██ ██ ████ ████████ ██ █ ██ ███ │
│███ █████ ██ █████ ██████ █ ███ ██ ███ ██ ███ █ ██ │
│█ ██ █ █████ █ ███ ████ █ ██ ███ █ █████ █ ██ █████ │
│█████ ██ █ ████ █ ██ █ ███████ █ ██ ███ ██ █████ █ ██ │
│█ █████ ██ █ ██ █████ ██ █ ██ █████ █ ██ ████ ██ ██ ███ │
│██ █ █████ ██ ████ ██ █████ ███ █ ██ █████ █ ██ ██████ █ ██ │
│███ ██ █ ██████ ██ ████ ██ █ ██ ██ ████ ████ ███ █ ███████ │
│█ █████ ██ █ ██ ███ █ ██ ███ ████████ █ ██ █ ███ ████ █ ██ │
│███ █████ ██ ████ ████ ███ █ ██ █ ████ ███ ██ █ ███ ██ ██ ███ │
│█ ██ █ █████ █ ███ ███ █████████ █ ███ ████████ ██ ███ ███ █ ██ │
│█████ ██ █ ██ ██ █ ██ █ ███ ██ ██ █ ███ ██████ ███ ██ █████│
└─────────────────────────────────────────────────────────────────────────────┘
So yeah, this entire post was basically a ploy to draw pretty pictures with Haskell. If you’d like, all the code from this post is wrapped up in a nice little file.