A Clojure Highlife

November 15th, 2009 No comments

I’ve been experimenting quite a bit in Clojure, a new programming language for the JVM. The new programming language is both interesting to me from a computer science and pragmatic point of view given that it is a truly functional programming language that can leverage the full breadth of libraries written for Java. I’ve experimented with Haskell in the past, but the library support and performance just weren’t there- and it was missing the simple elegance of a lisp. I’ve also tried my best to adopt functional programming techniques in my Python and Groovy code, but the languages’ multi-paradigm designs are unable to truly leverage the benefits of functional code.

Screenshot of my Highlife program

Screenshot of my Highlife program

For one of my first full programs written in Clojure I decided to create an implementation of Highlife, a derivative of Conway’s Game of Life. I implemented all of the simulation logic using pure Clojure and made use of Clojure’s Software Transactional Memory, or STM using Refs for sharing state effectively. The GUI is written using the Java Swing/AWT libraries via Clojure. There is some irony in that using Java libraries (calling Java methods, using Java classes, etc) from Clojure is more concise, readable, and in many ways easier than from Java itself. This is accomplished with virtually no special syntax and the code remains for the most part idiomatic Clojure.

My Highlife implementation features a “Seed” button which randomly populates the grid with new living cells, a pause button, a clear button, and the ability to click on a cell to flip its state while the simulation is running or paused. These features all work without locks, explicit state checks, or breaking/bending the simulation rules. Clojure’s STM guarantees these operations, along with recalculating, updating and drawing the grid, each happen atomically.

Since it is written in Clojure and compiled to JVM bytecode it should run on any system with Java 1.6 or later.

Download Here

Download Here

To run:

  1. Unzip the archive
  2. ‘cd’ into the ‘highlife’ directory contained in the archive
  3. Execute ‘java -jar Highlife.jar’
  4. Optionally you can pass the square grid dimension and initial seed, e.g. ‘java -jar Highlife.jar 90 4000′ for a 90×90 grid initially seeded with 4000 random living cells.

If you want to dig in a bit deeper below is the source code. You can run it directly from the Clojure REPL (and modify it on the fly!) or modify and compile it yourself. Enjoy!

; A Clojure Highlife
; Copyright 2009 Joseph Smith <joe@uwcreations.com>
;
;    This program 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.
;
;    This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.

(ns com.uwcreations.highlife
    (:gen-class)
    (:import (java.awt Color Dimension Graphics GridBagLayout GridBagConstraints)
             (javax.swing JButton JPanel JFrame Timer)
             (java.awt.event ActionListener MouseListener))
    (:use clojure.contrib.except))

;;some defaults
(def grid-dim 70)
(def point-size 8)
(def generation-length-millis 0)
(def initial-seed (int (* grid-dim grid-dim 0.20))) ; initial population is 20%

;cell datastructure
(defstruct cell :alive?)

(defn create-cell []
  (ref (struct cell false)))

;grid
(defn build-grid [dim]
  "Creates a 2D grid of cell refs"
  (vec (take dim (repeatedly (fn [] (vec (take dim (repeatedly #(create-cell)))))))))

(defn surrounding-neighbors-seq [grid x y]
  "Returns a lazy seq of surrounding cell refs"
  (let [x (int x) y (int y)]
  (map #(get-in grid %)
    [[(dec x) (dec y)] [x (dec y)] [(inc x) (dec y)]
     [(dec x)      y ]             [(inc x)      y ]
     [(dec x) (inc y)] [x (inc y)] [(inc x) (inc y)]])))

;memoize for performance
(def m-surrounding-neighbors-seq (memoize surrounding-neighbors-seq))

(defn count-living-neighbors [grid pt]
  "Returns the number of living neighbors to a cell"
  (let [[x y] pt]
    (count (filter #(= % true) (map #(:alive? @%) (filter #(not= nil %) (m-surrounding-neighbors-seq grid x y)))))))

(defn get-living-neighbors-seq [grid]
  "Returns a seq of living neighbor counts for each cell in the input grid"
  (doall (map #(count-living-neighbors grid %)
           (for [x (range (count grid)) y (range (count grid))] [x y]))))

(defn lives? [alive? num-neighbors]
  "Predicate representing the next state of a cell based on its current state and number of neighbors.
   This function defines the rules"
  (if alive?
    (contains? #{2 3} num-neighbors)
    (contains? #{3 6} num-neighbors)))

(defn update-cell [cell num-neighbors]
  "Updates a cell's state"
  (let [is-alive? (:alive? @cell)]
    (if (lives? is-alive? num-neighbors)
      (if (not is-alive?) (alter cell assoc :alive? true))
      (if is-alive? (alter cell assoc :alive? false)))))

(defn seed-grid [num grid]
  "Randomly populate the grid with living cells."
  (let [dims (count grid)]
    (throw-if (> num (* dims dims))
      "Number of initial living cells must be less than or equal to the dimensions of the grid")
    (dosync
      (doseq [coord (take num (distinct (repeatedly #(vector(rand-int dims) (rand-int dims)))))]
        (alter (get-in grid coord) assoc :alive? true)))))

(defn clear-grid [grid]
  "Set all cell :alive? values to false"
  (let [dims (count grid)]
    (dosync (doseq [x (range dims) y (range dims)] (alter (get-in grid [x y]) assoc :alive? false)))))

;;these functions translate between grid coordinates and display coordinates
(defn scale-point-for-display [pt]
  "Returns a vector of [x y width height] for the point to be drawn"
  (concat (map #(* % (+ 1 point-size)) pt) [point-size point-size]))

(defn display-to-grid-point [pt]
  "Takes pixel coordinates and Returns a vector of [x y] coresponding to a grid cell"
  (map #(int (/ 1 (/ (+ 1 point-size) %))) pt))

;memoize coordinate functions
(def m-scale-point-for-display (memoize scale-point-for-display))
(def m-display-to-grid-point (memoize display-to-grid-point))

;running state
(def running? (atom true))

;;begin gui stuff ---

;;drawing functions
(defn fill-point [#^Graphics g pt  #^Color color]
  (let [[x y width height] (m-scale-point-for-display pt)]
    (doto g
      (.setColor color)
      (.fillRect x y width height))))

(defn paint [#^Graphics g alive? pt]
  (if alive?
    (fill-point g pt (Color. 0 0 0))
    (fill-point g pt (Color. 255 255 255))))

;simualtion panel
(defn sim-panel [frame grid]
  (proxy [JPanel MouseListener] []
    (paintComponent [g]
      (proxy-super paintComponent #^Graphics g)
      (let [dim (count grid)]
        (dorun
          (map #(paint g (% 0) (% 1))
            (dosync (doall (for [x (range dim) y (range dim)] [(:alive? (deref (get-in grid [x y]))) [x y]])))))))
    (mouseClicked [e]
      (let [pt (m-display-to-grid-point [(.getX e) (.getY e)]) cell (get-in grid pt) alive? (:alive? @cell)]
        (dosync (alter cell assoc :alive? (not alive?)))
        (fill-point (.getGraphics this) pt (if (not alive?) (Color. 255 0 0) (Color. 255 255 255)))))
    (mousePressed [e])
    (mouseReleased [e])
    (mouseEntered [e])
    (mouseExited [e])
    (getPreferredSize []
      (let [dim (count grid)]
        (Dimension. (+ dim (* dim point-size)) (+ dim (* dim point-size)))))))

;;buttons
(defn seed-grid-button [grid panel]
  (proxy [JButton ActionListener] ["Seed Grid"]
    (actionPerformed [e]
      (seed-grid initial-seed grid)
      (.repaint panel))))

(defn clear-grid-button [grid panel]
  (proxy [JButton ActionListener] ["Clear Grid"]
    (actionPerformed [e]
      (clear-grid grid)
      (.repaint panel))))

(defn pause-life-button [sim-thread]
  (proxy [JButton ActionListener] ["Pause Simulation"]
    (actionPerformed [e]
      (swap! running? not)
      (if @running?
        (.setText this "Pause Simulation")
        (.setText this "Resume Simulation")))))

;update thread
(defn create-sim-thread [sim-grid panel]
  (Thread.
    #(let [dim (count sim-grid) grid-seq (for [x (range dim) y (range dim)] (get-in sim-grid [x y]))]
      (loop [gen 1]
        (if (not @running?)
          (do
            (Thread/sleep 300)
            (recur gen))
          (do
            (dosync (dorun (map update-cell grid-seq (get-living-neighbors-seq sim-grid))))
            (.repaint panel)
            (Thread/sleep generation-length-millis)
            (recur (inc gen))))))))

;simulation start function - call this to make things go
(defn start []
  (let [sim-grid (build-grid grid-dim)
        frame (JFrame. "A Clojure Highlife")
        panel (sim-panel frame sim-grid)
        sim-thread (create-sim-thread sim-grid panel)
        seed-button (seed-grid-button sim-grid panel)
        clear-button (clear-grid-button sim-grid panel)
        pause-button (pause-life-button sim-thread)

        layout (GridBagLayout.)
        seed-button-constraints (GridBagConstraints.)
        clear-button-constraints (GridBagConstraints.)
        pause-button-constraints (GridBagConstraints.)

        panel-constraints (GridBagConstraints.)]

    ;populate initial grid
    (seed-grid initial-seed sim-grid)

    ;action listener setup
    (.addActionListener seed-button seed-button)
    (.addActionListener clear-button clear-button)
    (.addActionListener pause-button pause-button)

    ;layout contraint definitions
    (set! (. seed-button-constraints gridx) 0)
    (set! (. seed-button-constraints gridy) 0)
    (set! (. clear-button-constraints gridx) 1)
    (set! (. clear-button-constraints gridy) 0)
    (set! (. pause-button-constraints gridx) 2)
    (set! (. pause-button-constraints gridy) 0)
    (set! (. panel-constraints gridx) 0)
    (set! (. panel-constraints gridy) 1)
    (set! (. panel-constraints gridwidth) 3)

    (doto panel
      (.setFocusable true)
      (.addMouseListener panel))

    (doto frame
      (.setLayout layout)
      (.add seed-button seed-button-constraints)
      (.add clear-button clear-button-constraints)

      (.add pause-button pause-button-constraints)
      (.add panel panel-constraints)
      (.pack)
      (.setVisible true))
    (.start sim-thread))) ;sim starts here

(defn -main
  ([] ;if no args are provided, use defaults
    (start))
  ([dims seed] ;modify defaults by passing args
    (def grid-dim (Integer/parseInt dims)) ;user-defined grid dimensions
    (def initial-seed (Integer/parseInt seed)) ;user-defined initial seed
    (start)))

Countdown to the end

May 2nd, 2009 No comments

Finish senior design project. Check. Win EWeek competition with project. Check. Make it to finals week alive. Check. Two finals and one project presentation stand between me and sweet sweet victory! Erm, I mean, my Computer Engineering degree. :)

Categories: Uncategorized Tags: , ,

Pond

February 14th, 2009 No comments

Heard from quacking outside my living room window. Here are some pictures from my balcony.

Categories: Uncategorized Tags:

Delicious

January 26th, 2009 No comments

What better way to start off the year. Here are a couple of the things I’ve cooked up over the past two weeks. One old favorite and something new!

Old Favorite – Chicken Adobo

New Creation – Chicken, Shrimp, and Cream Cheese Enchiladas

Good Measure – Pico de Gallo.

Amazing new creation – Chicken/shrimp enchiladas


Categories: Cooking Tags: , , ,

Cadence!

January 7th, 2009 No comments

Just too good a pic not to post.

My daughter

My daughter

Categories: Uncategorized Tags: ,

Slow down!

January 6th, 2009 No comments

So I can catch up!

Apple just released a new version of iLife, including an update to iPhoto called Faces. It detects and tags faces in your pictures with the person’s name. You can see it here: http://www.apple.com/ilife/iphoto/#faces

What’s frustrating is this was my semester project for a computer vision course I took in spring of 2008. My solution automatically detected and tagged recognized faces and prompted the user to tag new/unrecognized faces. The program continuously improved on a database of known faces to increase the chance of a positive detection and recognition of known faces (from different angles, lighting, facial hair, etc). To accomplish this I used a combination of the OpenCV computer vision toolkit for face detection (using Viola-Jones / Haar feature cascades)and the Identix SDK for identification statistics and eye locations (as registration coordinates when comparing different sized faces) when comparing facial regions of interest.

While I came up with the idea on my own, I realize it isn’t original. I’m sure Apple and others have been working on an implementation of this before I even had the idea. The real killer is Apple’s Facebook plugin. When I started working on the idea the main application I was envisioned was automatic tagging of your Facebook photos. Anyway, below are some pictures from my class demonstration presentation.

Face and eye detection in a group of people
Face and eye detection in a group of people
More face and eye detection
More face and eye detection
Calculated eye coordinates on a detected face
Calculated eye coordinates on a detected face
Using eye coordinates as registration points for comparing two faces
Using eye coordinates as registration points for comparing two faces
Scaling one face and eye coordinates for feature/structure comparison
Scaling one face and aligning eye coordinates for feature/structure comparison
A frame from my flowchart animation
A frame from my flowchart animation
Another frame from my flowchart animation
Another frame from my flowchart animation