Andrew's Automata

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]
            [goog.events :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."
  [live-or-dead]
  (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."
  [rule]
  (map #(bit-and rule %) [128 64 32 16 8 4 2 1]))

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."
  []
  (.clearRect CANVAS 0 0 CANVAS-SIZE CANVAS-SIZE))

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))))

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]))])

(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))

(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))))

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

(defn xcoords-lhs
  "Returns the cell x-coordinates for a finite sequence of cells on the
left hand side of the automata."
  [cells]
  (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."
  [cells]
  (range 0 (count cells)))

(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))

(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)))

(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
                     (range)
                     (take V-CELLS (iterate (partial evolve-seq rule) row-zero)))]
    (draw-sequence r s)))

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."
  [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."
  [check]
  (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."
  [checks]
  (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."
  []
  (clear-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"
  [row-type]
  (if (row-types row-type)
    ((row-types row-type))
    (white-row)))

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."
  []
  (clear-canvas)
  (black)
  (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
                 ev/EventType.CLICK
                 #(check-onclick check rule-no))))

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

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

  (ev/listen start
             ev/EventType.CHANGE
             #(let [new-start-row (get-row (.-value start))]
                (reset! start-row new-start-row)
                (draw-first-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)
    (.clearRect CANVAS 0 0 CANVAS-SIZE CANVAS-SIZE)
    (set-checks-values start)
    (draw-automata start (rand-row))
    (js/setTimeout #(draw-rules (dec start)) 3000)))