Andrew's Automata

Table of Contents


This is a ClojureScript application which draws evolution diagrams of one dimensional cellular automata on a web page.

I started this small project in order to learn ClojureScript. When learning Clojure I was very familiar with programming in Java. But I haven't done any web programming for around 8 or 9 years, back in the days of EJB and JSP, so my JavaScript knowledge is very minimal. Therefore I have gained new sympathy for people coming to Clojure with only minimal experience of Java and the JVM.

Later on I found blog post about using Babel within Org. So I am now documenting this little program using Org. I don't think that the elisp code in that post is quite correct, but that is another subject. For Clojure I am using the default set up within Babel without writing any custom elisp for evaluation. This means that I am tied to Slime for Clojure, which makes things tricky for ClojureScript as there is no Swank server for Javascript yet.

I find that ClojureScript works best with lein and the cljsbuild plugin, which provides various REPLs. These can be used from the Emacs inferior-lisp mode but it seems there is no generic Babel plugin for inferior-lisp, only for various Slime flavours. Luckily it wasn't too hard to build something that did the job.

The other Clojure documentation tool is Marginalia. Marginalia is more like Javadoc in that it extracts the comments from your source code to build the documentation. Its main distinguishing feature is the way it sets the comments next to the code so its really easy to read both code and comments at the same time. I run Marginalia over the source code after it has been extracted from the main Org file.

So, this project is two things. A way for me to learn ClojureScript, and an experiment is using Org and Marginalia to document the code.

The results of all this are as follows

And finally

  • The site itself where you can explore one dimensional cellular automata to your hearts content!

Please feel free to get in touch with any comments or feedback.

The Code


First we create a namespace and import what we need. The repl library allows us to evaluate ClojureScript in a browser from a remote repl. The other two libraries are from Google Closure.

(ns automata
  (:require [clojure.browser.repl :as repl]
            [goog.dom :as dom]
            [goog.dom.classes :as cls]
            [ :as ev]))

When loaded into a browser this will connect back to a remote repl, and export the browsers evaluation capabilities.

(repl/connect "http://localhost:9000/repl")


Now we define a bunch of constants for use in various functions. Mostly to control the size of various elements when drawn on the page.

;; TODO retreive canvas size from the document
(def CANVAS-SIZE "The width and height of the canvas." 300)
(def CELL-SIZE "The size of each cell in pixels." 5)
(def CELL-GAP "The size of the gap between cells, in pixels." 1)
(def CELL-INTERVAL "The gap between the start of one cell, and the start of the next." (+ CELL-SIZE CELL-GAP))

These constants control the number of cells that need to be calculated to fill the canvas.

(def V-CELLS "The number of cells in a column on the canvas." (int (/ CANVAS-SIZE 6)))
(def LHS-CELLS "The number of cells on the left hand side of a row on the canvas." (int (/ CANVAS-SIZE 12)))
(def RHS-CELLS "The number of cells on the left hand side of a row on the canvas." (inc LHS-CELLS))

Not strictly speaking the canvas, but all interaction with the canvas happens via its graphics context. This (and the drawing routines below) could be rewritten using generic graphics functions from Closure.

(def CANVAS "The graphics element from the canvas."
  (-> (dom/getElement "canvas")
      (.getContext "2d")))


One dimensional cellular automata consist of a single infinite line of cells, and a rule for evolving the next generation. Each cell can be either on or off (black or white, alive or dead, etc.). The rule is defined by specifying an output for all possible inputs. For each cell, the inputs are itself and the two cells on either side, making a total of eight possible values for the three binary inputs. The inputs are enumerated below.

(def ALL-INPUTS "A vector of possible inputs for the evolution of a cell."
  [[1 1 1] [1 1 0] [1 0 1] [1 0 0] [0 1 1] [0 1 0] [0 0 1] [0 0 0]])

To convert from a rule number to a rule consider this. Each possible input for a cell results in the cell in the next generation being either alive or dead. If the cell lives then we give that input a one. If the cell dies we give that input a zero. This gives us 8 ones or zeros to make an 8 bit number, i.e. a rule number from 0 to 255.

(defn decode-rule
  "Creates a rule number from the given set of binary inputs."
  (js/parseInt (apply str live-or-dead) 2))

(defn encode-rule
  "Given a rule number, creates a sequence of live or dead values for
  the next generation of cells."
  (map #(bit-and rule %) [128 64 32 16 8 4 2 1]))

Drawing functions

Next we have the functions that actually draw on the canvas.

Two helpers to start with. The first sets the colour used for drawing the cells. The function is called 'black' for some obscure reason. Next is the function for erasing all cells from the canvas.

(defn black 
  "Sets the color of the canvas"
  (set! (.-fillStyle CANVAS) "rgb(0,0,0)"))

(defn clear-canvas
  "Clears the entire canvas."

This function draws a single square on the canvas representing a live cell. The coordinates x and y are given in terms of cells. The origin is at the top of the canvas in the middle. So cells on the left hand side have a negative x coordinate. This function is called for every cell, and the fill variable indicates whether the cell should actually be filled in, i.e. whether it is live or not.

(defn draw-cell
  "When fill is true, draws a single cell on the canvas, otherwise leaves it blank.
The input coordinates are given in terms of cells, and converted here into pixel coordinates."
  [[x y] fill]
  (when fill
    (let [xpos (+ (- (/ CANVAS-SIZE 2) CELL-INTERVAL) (* CELL-INTERVAL x))
          ypos (* CELL-INTERVAL y)]
      (.fillRect CANVAS xpos ypos CELL-SIZE CELL-SIZE))))

Working with cells

Now we have dispensed with the paractical matter of actually drawing the automaton, we come to the abstract matter of calculating its evolution.

First we have four functions to create different initial states for the automaton.

;; A row in the automata is represented by a vector of two infinite sequences.
;; The first sequence is the cells from the center out to the left, and the
;; second is the cells from the center out to the right.
;; A 0 indicates a non-live (white) cell, and a 1 indicates a live (black cell).

(defn middle-cell
  "Returns a row with one cell live in the center."
  [(repeat 0) (lazy-seq (cons 1 (repeat 0)))])

(defn white-row
  "Returns a row with no cells live."
  [(repeat 0) (repeat 0)])

(defn black-row
  "Returns a row with all cells live."
  [(repeat 1) (repeat 1)])

(defn rand-row
  "Returns a random row."
  [(repeatedly #(rand-nth [0 1])) (repeatedly #(rand-nth [0 1]))])

Evolving cells

For these functions a rule is represented by a map, and so calculating the new state for the cell is a simple map lookup, using the three input values as the key.

(defn evolve-cell
  "Takes a rule and three input cells, and produces the value for the outptut cell.
A rule is represented by a map from all possible inputs to the output."
  [rule input]
  (rule input))

We represent the current state of the automata as two sequences, and so we have two functions here. The first evolves the left hand side of the automaton. We use partition to split the sequence up into the sets of three inputs that each cell requires to determine its state for the next generation. Note that we have to peek at one item from the other side in order to have the inputs for the first cell on the left hand side. Note also the use of reverse, the left hand side runs from right to left, but the inputs in the rules are specified from left to right.

The second function is a little simpler as it does not have to do the reverse.

In both of these functions we could replace "(partial evolve-cell rule)" with simply "rule". It used to be more complicated to do the calculation before I started using a map for the rule, and I've left it how it was as I think it is a little more explicit this way.

(defn evolve-lhs
  "Computes one evolution of the left hand side of the automata."
  [rule lhs rhs]
  (map (comp (partial evolve-cell rule) reverse) (partition 3 1 (cons (first rhs) lhs))))

(defn evolve-rhs
  "Computes one evolution of the right hand side of the automata."
  [rule lhs rhs]
  (map (partial evolve-cell rule) (partition 3 1 (cons (first lhs) rhs))))

This function simply produces a new complete state for the automaton by seperately evolving the old state's two halves.

(defn evolve-seq
  "Computes one evolution of the automata."
  [rule [lhs rhs]]
  [(evolve-lhs rule lhs rhs)
   (evolve-rhs rule lhs rhs)])

Passing the cells to the drawing functions

Once the cells have been calculated, they must be drawn. The drawing function above draws a single cell, and it requires cell coordinates, which it will then convert to coordinates on the canvas.

These two functions return ranges of cell coordinates for the x-axis. For the left hand side these start at -1 and decrease. For the right hand side they start at 0 and increase.

(defn xcoords-lhs
  "Returns the cell x-coordinates for a finite sequence of cells on the
left hand side of the automata."
  (let [end (- (inc (count cells)))]
    (range -1 end -1)))

(defn xcoords-rhs
  "Returns the cell x-coordinates for a finite sequence of cells on the
right hand side of the automata."
  (range 0 (count cells)))

The next three functions are used to draw half a row of the automaton. The first is a utility and can draw either side, and the next two are specializations which call it.

(defn draw-half
  "Given a row number, and a finite sequence of cells, draws the cells on one half of the automata.
Also requires a function to produce the cell x-coordinates."
  [row half coord-fn]
  (doseq [cell (map (fn [x c] [[x row] (= 1 c)]) (coord-fn half) half)]
    (apply draw-cell cell)))

(defn draw-lhs
  "Given a row number, and a finite sequence of cells, draws the cells on the
left hand side of the automata."
  [row lhs]
  (draw-half row lhs xcoords-lhs))

(defn draw-rhs
  "Given a row number, and a finite sequence of cells, draws the cells on the
right hand side of the automata."
  [row rhs]
  (draw-half row rhs xcoords-rhs))

This function takes one complete generation of the automaton (i.e. two infinite sequences of cells as described above) and realizes only those parts needed to fill the canvas. It also takes a row (or generation) number which specifies how far down to draw the row.

(defn draw-sequence
  "Draws the given row on the canvas, where a row is represented by
two (possibly infinite) sequences of cells."
  [row [lhs rhs]]
  (draw-lhs row (take LHS-CELLS lhs))
  (draw-rhs row (take RHS-CELLS rhs)))

This function iterates the evolution of the automaton, drawing each generation as a row on the canvas.

(defn draw-automata
  "Draws multiple rows of the automata starting with the given start row, evolving using the given rule."
  [rule row-zero]
  (doseq [[r s] (map vector
                     (take V-CELLS (iterate (partial evolve-seq rule) row-zero)))]
    (draw-sequence r s)))

The UI

The UI consists of a canvas, which contains the drawing of the evolution of the automaton. There are 8 elements to allow the user to select the rule graphically, and an input field to type a numeric rule number. The 8 elements and the numeric box are linked, so changing one will cause the corresponding change in the other. There is also an input field to select the initial configuration of the automaton, drawn as the first row at the top of the canvas.

There is one button, which clears the canvas and draws the automaton.

We need to store the starting row. This is really for when the user elects to start with a random row. We immediately display the row, and then we must store it, so then when the user hits the draw button, the initial row doesn't get regenerated.

(def start-row
  "Holds the current starting row, set whenever the user selects a new row type."
  (atom (middle-cell)))

We have 8 input elements (drawn with divs in a table) for the user to choose the current rule. Here are two functions to help out with those.

(defn swap-alive-dead
  [cb dead]
  (apply cls/addRemove cb (if dead ["alive" "dead"] ["dead" "alive"])))

(defn get-checks
  "Gets all the dom elements for the checkboxes on the page."
  (map #(dom/getElement (str "cb-" %)) (range 0 8)))

(defn set-checks-values
  "Called when the user enters a rule number. Parses the number into
    the correct configuration of check boxes to represent the rule."
  (doseq [[c cb] (map vector (encode-rule rule) (get-checks))]
    (swap-alive-dead cb (= 0 c))))

These two functions help with converting the settings the user has made with the input elements into rules. We need to convert these settings into a rule number, for display in the rule number field and into a rule in the map format, to use to calculate the automaton's evolution.

(defn check-to-bit
  "Returns 1 if the element is checked, 0 otherwise."
  (if (cls/has check "alive") 1 0))

(defn checks-value
  "Returns a rule number decoded from the current state of the input elements on the page."
  (decode-rule (map check-to-bit (get-checks))))

(defn checks-to-rule
  "Returns a rule represented as a map from inputs to outputs."
  (zipmap ALL-INPUTS (map check-to-bit checks)))

These two functions are the onclick handlers for the various input elements.

(defn draw-onclick
  "Called when the user presses the draw button. Draws the automata on the canvas."
  (draw-automata (checks-to-rule (get-checks)) @start-row))

(defn check-onclick
  "Called when the user presses one of the output cells on the rule specifier."
  [cell rule-no]
  (swap-alive-dead cell (cls/has cell "alive"))
  (set! (.-value rule-no) (checks-value)))

This is used to generate the initial row. The function which does the worked is retrieved from the map of possible starting row types.

(def row-types
  "A map from the names of the row types (as entered by the user)
  to the actual row type functions."
  {"middle-cell" middle-cell
   "white-row" white-row
   "black-row" black-row
   "rand-row" rand-row})

(defn get-row
  "Returns a row based on the given row type string. 
   Returns an all white row if the row type is unrecognised"
  (if (row-types row-type)
    ((row-types row-type))

This function is called whenever the user changes the initial row type. The canvas is cleared and the new row is drawn at the top.

(defn draw-first-row
  "Clears the canvas and draws the first row."
  (draw-sequence 0 @start-row))
;; Set all the event handlers for the controls on the page.
;; <br/><b>rule-no</b> is a text field where the user can enter a rule number.
;; <br/><b>draw</b> is a button which draws the automata on the canvas.
;; <br/><b>start</b> is a select box where the user can choose the type of start row.
;; <br/><b>cb<1-8></b> are checks for picking the output for individual inputs.
(let [rule-no (dom/getElement "rule-no")
      draw (dom/getElement "draw")
      start (dom/getElement "start")]

  (doseq [i (range 0 8)]
    (let [check (dom/getElement (str "cb-" i))]
      (ev/listen check
                 #(check-onclick check rule-no))))

  (ev/listen draw ev/EventType.CLICK draw-onclick)

  (ev/listen rule-no
             #(set-checks-values (js/parseInt (.-value rule-no))))

  (ev/listen start
             #(let [new-start-row (get-row (.-value start))]
                (reset! start-row new-start-row)

This is a test function you can call from the repl - it starts a process that will cycle through all the rules in in descending order, starting with whatever number you pass in.

(defn draw-rules [start]
  (when (> start -1)
    (set-checks-values start)
    (draw-automata start (rand-row))
    (js/setTimeout #(draw-rules (dec start)) 3000)))


This file is part of Andrew's Automata.

Andrew's Automata is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

Andrew's Automata is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Andrew's Automata. If not, see

Date: June 2012

Author: Andrew Cowper

Org version 7.8.11 with Emacs version 24

Validate XHTML 1.0