Tuesday, June 20, 2017

fn-code has moved

Dear readers,

I haven't been blogging for a while here at fn-code, but I've decided to restart the effort. However, one of the challenges of developing good content has been the blogger platform itself. Two particular issues I've seen have been the random "unposting" of some of my posts as well as the decision by Google to no longer host static assets on Drive. So, the new blog (including all of the old posts) is now http://markbastian.github.io/. I've got plenty of ideas for posts and now that things have settled down for me in other areas of my life you should be seeing new content soon.


Thursday, April 7, 2016

Another Tetris Clone in Clojure

Recently I was looking at a problem involving extracting and transposing submatrices of data within a larger data grid. Somehow this got me thinking how easy it would be to rotate tetrominos using Clojure. In case you are wondering, it is super easy:
(defn rotate-ccw [shape] 
  (apply mapv vector (map rseq shape)))

(defn rotate-cw [shape] 
  (apply mapv (comp vec rseq vector) shape))
These two functions will rotate a tetromino counterclockwise and clockwise, respectively. No math required.

After doing this trivial exercise I soon found myself asking myself "How fast can I code up Tetris in Clojure." It turns out that the answer is "pretty fast." Let me first say that this is not a new idea. It has been done here and here as well. I still thought it would be fun, so here is my solution along with some insights.

Here's the game. Press the left and right arrow keys to translate, up and down arrows to rotate, and the space bar to make the the tetromino immediately fall into place.

Read on to learn more about how the game was actually written.

Data First Design
As anyone who has seen my Clojure/conj video or talked to me knows, I believe the best approach to coding a solution to a problem is to model the data literally rather than design an API to represent the data. Why model a domain when you can represent it directly instead? Clojure is made for this approach. This exercise is no different, as the first step is to model the shapes as maps of vector literals. Rather than making some sort of base "Tetromino" class and extending a bunch of methods and having some field that loads a bitmap or some such nonsense, I just did what you see here:
(def shapes
  {:I [[0 0 0 0]
       [1 1 1 1]
       [0 0 0 0]
       [0 0 0 0]]
   :J [[0 0 0]
       [1 1 1]
       [0 0 1]]
   :L [[0 0 0]
       [1 1 1]
       [1 0 0]]
   :O [[1 1]
       [1 1]]
   :S [[0 0 0]
       [0 1 1]
       [1 1 0]]
   :T [[0 0 0]
       [1 1 1]
       [0 1 0]]
   :Z [[1 1 0]
       [0 1 1]
       [0 0 0]]})
Pretty cool, eh? You can look right at the shape entries and see the shapes as they are encoded in the data structures as 1s in a field of 0s. Of course, the current shape will be translating and rotating during the game, so I must keep track of that. I also want to track a few other game values, such as the current score, high score, values to keep track of when a tetromino falls, as well as the cells that are currently locked into place.

This can all be captured in a single function that generates an initial state representing a complete value for the game.
(defn initial-state []
  {:frame 0
   :speed 50
   :score 0
   :high-score 0
   :locked #{}
   :shape-pos [(rand-int 7) 0]
   :shape ((rand-nth (keys shapes)) shapes)})
The data structure above completely represents all of the values I need to keep track of for my entire game. The most interesting entries are locked, shape-pos, and shape. locked is a set of coordinates in the board that contain locked cells. shape-pos is the upper left hand coordinate of the current tetramino. shape is the current falling tetramino shape. Note that I do not keep track of rotation. I just rotate the piece in place.

At this point, all that remains is filling in some functions and methods around this data for user interaction, game rules, and rendering. Here are some of the details.

Implicit Board Representation
Rather than taking the usual approach of creating an MxN grid, I implicitly represent the board by using rules for boundaries (nothing can be outside of the board dimensions) and a hash set to represent the blocks currently "locked in" to the board. This definition looks like this:
(defn valid? [{:keys [locked] :as state}]
  (every? (fn [[x y :as c]]
            (and ((complement locked) c) 
                 (<= 0 x 9) (< y 22)))
          (shape-coords state)))

Basically, for every coordinate in the current falling shape (The shape-coords function) I check to see if it is within the game's x-y grid and if it is not contained in the locked set of cells.

Speaking of computing the coordinates of the current shape, this is something I'll do a lot, so here's a handy function to do it:
(defn shape-coords [{:keys [shape-pos shape]}]
  (let [d (count shape)]
    (for [i (range d) j (range d) 
          :when (= 1 (get-in shape [i j]))]
      (mapv + [i j] shape-pos))))
This function destructures the current shape position and shape cells from the game and returns the coordinates of the 4 cells in the shape (the 1s).

Given the above representations, the game reduces down to making valid tetromino moves within the board. There are two scenarios for moving a tetromino:
  1. The user moves it (This does not include the user making the tetromino fall faster). A user can translate or rotate a tetromino. The only thing the game must do when a user performs a translation or rotation is see if the new piece is in a valid location. If it is you accept the new value, if not you just reject the move.
  2. It is falling. When a tetromino falls (either over time or by a user forcing it to fall faster) there is only one thing to consider: Is the new position overlapping the set of locked blocks? If so, we do not allow the tetromino to fall, but instead add the former grid positions of the tetromino to the locked block set.
A key point here is that rather than allowing invalid operations to be performed and throwing exceptions or other similar mechanisms, this program simply rejects any invalid operations and always maintains a valid value for the current state.

Here are the functions for piece translation and rotation:
(defn x-shift [state f]
  (let [shifted (update-in state [:shape-pos 0] f)]
    (if (valid? shifted) shifted state)))

(defn rotate [state f]
  (let [shifted (update state :shape f)]
    (if (valid? shifted) shifted state)))
In the above code x-shift means "translate shift" and f is a function to be applied to the shape position (either inc or dec for right or left translation, respectively). rotate takes on of the two rotation functions I defined at the beginning of this post.

For falling, the logic is a bit more complex:
(defn fall [state]
  (let [shifted (update-in state [:shape-pos 1] inc)]
    (if (valid? shifted)
      (let [locked-coords (shape-coords state)]
        (-> state
            (update :locked into locked-coords)
            (score 1)
            (#(reduce clear-row % (map second locked-coords)))
            (into { :shape ((rand-nth (keys shapes)) shapes)
                   :shape-pos [(rand-int 7) 0]}))))))
Again, we first do a simple shift. If it is valid, we are done. If it isn't valid that means we've either moved off the bottom of the board or intersected with existing locked pieces. Either way, we lock the unshifted cells into the board and then check to see if rows need clearing. Finally, we add in a new random shape at the top of the board. I also give the player a point when a cell locks.

The player can also execute a fast drop in which they have a piece prepositioned and want it to immediately lock so they can get the next piece. This is as simple as:
(defn fast-drop [{:keys [locked] :as state}]
  (some #(when (not= locked (:locked %)) %) 
        (iterate fall state)))
The function iterates over the current state with the fall function until the set of locked set of cells change. This will occur when the falling piece can no longer fall.

Clearing Rows
Clearing a row occurs when all every cell in a row is locked. When this occurs, state is threaded such that 10 points are awarded, the speed is decreased (more on this in the next section), and cells are kept, removed, or shifted depending on their relation to the row to be removed.
(defn clear-row [{:keys [locked] :as state} row]
  (if (every? locked (for [i (range 10)] [i row]))
    (-> state
        (score 10)
        (update :speed dec)
        (assoc :locked
               (set (for [[i j] locked :when (not= j row)]
                      (if (< j row) [i (inc j)] [i j])))))

Bringing It All Together
The final function needed is a game-step function that is called by the user interface layer for each game time step. Here's the function:
(defn game-step [{:keys [frame locked speed] :as state}]
  (cond-> (update state :frame inc)
          (zero? (mod frame (max speed 1)))
          (some zero? (map second locked))
          (into (dissoc (initial-state) :high-score))))
The function updates the frame at each time step then does some conditional threading at the new game step. First, if the frame modded with the current speed is zero, the tetromino falls. So, speed in this game is really a misnomer. Lower speed makes the tetromino fall more frequently. Finally, if any y coordinate in the locked cells is at 0 (I am using screen coordinates, so 0 is at the top of the screen going down) we reset the game but maintain the current high score.

A Complete Rule Set and a UI
All of the above code in a single namespace completely defines the game engine. All that is needed is a user interface to display the current value and take user input. I won't go into the details of the UI in this post, but might later. However, here are a couple of high level details about the UI:
  • I actually did 2 interfaces - one using Quil and one using Reagent. The one embedded here is the Reagent version.
  • The Quil UI compiles to both Java and JavaScript where the Reagent version just compiles to JavaScript.
  • The rules are written as cljc files so cross compile without issue.
  • Either UI is only about 50-70 lines of code, so are pretty minimal.

Once again, Clojure's ability to let me model a domain directly as data and then write functions to manipulate those domain values has yielded a simple and concise solution to a problem. I find it pretty amazing that I can write an entire game, including UI, in about 150 lines of code. Not only is the solution brief, but I think the simple function names and full-state representation of values makes the code pretty readable. Despite being a simple case in this post, I've found this technique to be quite useful in domains of any size or complexity. However, a key requirement for this approach is a language that has full support for modeling the domain as data. Clojure is an excellent fit as it was designed to be data first from inception.

The complete source for this project can be cloned here.

Tuesday, December 1, 2015

Clojure: Getting Started

Often people will ask me how to get started in Clojure. Most often they have a Java background, but sometimes they are coming from C++, Python, or some other popular language. Either way, I rehash the same story and spent a bunch of time finding and consolidating the same links as the last time someone asked me this question.

This post is meant to be my simple, consolidated answer to "How do I get started with Clojure?"

Here's how...

Pick a Project
Before you do anything else, you really need to pick some simple project you will do in Clojure. In my experience, attempting to learn something without some concurrent hands-on experience isn't particularly effective. My first non-trivial (i.e. (prn "Hello World)) application was an implementation of the board game Cartagena that I talked about at Clojure/conj. You can watch it right here:

I suggest an application that has some state, whether it be a desktop application or single page web app (using ClojureScript). That way you can use atoms and understand how Clojure separates the concerns of state (atoms, agents, or refs), value (data), and transition (functions). I think board games make excellent projects, but then again I really like board games. You could do just about anything.

Watch & Read
Here are a few links I recommend to everyone, not in any particular order. They are all excellent.
  • Clojure for the Brave and True: Daniel Higginbotham's truly awesome book/online learning series on learning Clojure from the ground up. Buy it here. This is my #1 recommended getting started resource.
  • Clojure Evaluation: The single most important documentation page on Clojure in the entire universe. Once you understand this page you pretty much know the entire language (not the APIs). Yes, Clojure is this simple.
  • Clojure - Functional Programming for the JVM: Mark Volkmann's extremely direct and to the point single web page description of Clojure.
  • Rich Hickey's Greatest Hits: Most of these are more philosophical than tutorial in nature, but they give you great insights into the genius behind Clojure. Key concepts such as value, state, identity, etc. are described in these videos. My favorites:
    • Are We There Yet?
    • Simple Made Easy
    • The Value of Values
In Conclusion
Hopefully the above tips and links will give you a little help if you are considering Clojure and want to know where to start. Either way, I'll have something to point to next time someone asks me.

Friday, October 16, 2015

My Concern with Concerns

In the Computer Science world we often talk about the value of Separation of Concerns (SoC). This Wikipedia article on the subject says that well-separated code is more modular, maintainable, and reusable. The basic idea is that we separate our code into components by their roles so that those pieces can be used and developed independently as well as assembled into a greater whole.

However, I am concerned with the traditional treatment of concerns. We often look at concerns as a breakdown of our application into various interconnected pieces, or objects. For example, you might have a game program with a rendering system, an input system, a physics system, and so on. A spreadsheet application might have concerns regarding computations, persistence, and input. At a high level, and borrowing from the Wikipedia article, you might have concerns for things like business logic, persistence, data access, and presentation.

Two major flaws with the typical treatment of SoC as described above stand out to me:
  1. In many of these systems the various parts require knowing about each other to the degree that if you use one, you must also use the others. This leads to complected, interconnected systems. Rich Hickey talks all about it here.
  2. We have jumped past some core fundamental concerns of how we think about computing and moved straight to high level constructs (usually objects, layers, or systems). This is what I want to talk about.
These are the three low level concerns I am concerned about:

1. Representation: How do you describe the world?
The first concern to consider is how you represent your world. In a traditional object oriented approach, the simple solution is objects with their corresponding fields. Even in many functional or mostly functional languages like Scala you will use value types to represent your world. Consider the following three ways to represent a person:

package concerns;

public class Person {
    private String name;
    private int age;
    private double weight;

    public Person() {

    public Person(String name, int age, double weight) {
        this.name = name;
        this.age = age;
        this.weight = weight;

    public String getName() {
        return name;

    public void setName(String name) {
        this.name = name;

    public int getAge() {
        return age;

    public void setAge(int age) {
        this.age = age;

    public double getWeight() {
        return weight;

    public void setWeight(double weight) {
        this.weight = weight;
case class Person(name : String, age : Int, weight : Double)
{ :name "Zaphod" :age 21 :weight 160.0 }
Clojure is unique in that practitioners generally represents the world as simple data structures. Other languages would have you define a class for your data (Often in a painfully verbose way, I might add), but Clojure simply views everything as data. You can use gen-class or defrecord, but you generally don't unless you are shooting for Java interop or feel the need for a defined structural type.

Clojure is relatively unique in that it allows you to flexibly represent anything using a small number of primitives and heterogeneous, nested data structures. You have a single, uniform approach to representing anything as data, whether it be simple or extremely complicated.

Classes, on the other hand, require a new class for any level of modification of representation. A person with height would need to extend a base Person (e.g. PersonWithHeight extends Person). This leads to elaborate type hierarchies and an explosion of representations. Classes also fail disastrously when dealing with temporal changes. Suppose you want to transition from a Caterpillar to a Butterfly or from an Employee to a Manger (You got a promotion. Congratulations!). How do you handle these? Do you pass roles around? Does that work in the caterpillar to butterfly case? Is there a GoF anti-pattern for that?

This is not to say classes do not have their place. If your representation is well-known at design time a class can be an excellent fit for your problem. For example, a 3D mathematical vector is very well defined with fields along 3 axes. However, using classes to represent things with a wide variety of potential fields or that transition over time can be a disaster.

Clojure's simple approach to the concern of representation is wonderful, but we are here to discuss the separation of concerns, so let's talk about another concern that we need to keep separate...

2. Behavior: How do you modify or use your representation of the world?
The next concern is how you modify the representation of your world, or how you transition from one representation to another. Tied to this is how you do things with your objects, even if you don't modify them. In OOP this is done by class methods that operate on themselves or objects they are familiar with. This seems natural, as most verbs tend to operate on some noun. For example, a rename method clearly must rename something. What is that thing? For an object, it logically is the thing rename is attached to.

However, this complects the concerns of representation and behavior.

Consider the trivial situation of managing named objects. What if I want to rename a person, car, dog, or file? In OOP, I need to add a method to every object (e.g. setName or rename) that is nameable. You might argue for a common base class (e.g. AbstractRenameable), but now everything must extend this class, and you don't want to waste your one-shot inheritance on something so trivial. Instead, maybe you implement IName and proxy a DefaultName. In any event, you are complected up the wazoo for something so simple as the ability to rename an object. And you have to do this every time, for every field on every object.

Wouldn't it be better to have some independent function that renames every structurally similar piece of data? I can do this trivially in Clojure like this:
(defn rename[o name](assoc o :name name))

    { :name "Zaphod Beeblebrox"
     :age 21
     :weight 160.0 }
    "Ford Prefect"))

    { :type :spaceship
     :name "Heart of Gold"
     :color :red }
    "Millenium Falcon"))
This produces the following output:
{:name "Ford Prefect", :age 21, :weight 160.0}
{:type :spaceship, :name "Millenium Falcon", :color :red}
One function that works on any structurally similar object. Compare this to putting a rename method on every named object in existence. This is what I call a separation of concerns.

Let's look at a slightly less trivial example. Suppose you are writing a sprite-based game and have a variety of scene elements that you want to render. Each element must have information for its location and the image to be drawn. Let's look at how you might render a sprite-based image in our three languages using Java 2D:

Here is what you would add to the above class:
public void render(Graphics2D g){
    g.drawImage(getImage(), getX(), getY(), null);
This, of course, assumes you have also added fields and methods to manage the image and the item's location. You've now fundamentally intertwined your class with the Java 2D library, some AWT classes for handing images, and whatever else you've done to make this work.

Scala suffers from the same problem as Java because it still complects the concerns of representation and behavior. In Scala's defense, it does have duck typing, structural typing, and traits that allow you to do a variety of things to repeat yourself a lot less. It's a better situation, but it does add complexity to your solution and you have to go to a lot of effort to separate your behavior from your representation.

Clojure completely separates the concerns of representation and behavior by using pure data structures to represent data and functions to represent behavior. The only required interface is correct structural inputs to functions.
(defn render [g {:keys [image x y]}]
  (.drawImage g image x y nil))
In this example, any data conforming to the required interface (Having entries for the :image, :x, and :y keys) can be rendered. The data has no knowledge of Graphics2D and is only loosely coupled to AWT by having a field entry referencing an image. This data can be removed from the map entirely if not needed as opposed to an object which would have a null field that still references a foreign API. 

We're now double-complected in OOP-land and have complete separation with Clojure. Let's throw another concern into the mix...

3. Management: How do you keep track of the current state of the world?
Separate from the idea of how you represent and act in your world is how you keep track of your current (and perhaps historical) view of the world. This includes not just a handle to the current value of the world, but a mechanism for watching for changes and responding accordingly.

In Java this is accomplished via a fully implemented Java Bean, with getters, setters, property change support, property change listeners, and so on. Your bean class will have a mechanism to wire up things that listen for changes and changes are fired when change occurs. Again, we've further tied another concern to the object. We're now complected x3.

Scala doesn't address this concern directly, but you've got options. You can create Java Beans in Scala, but beans are an ugly, complicated mess that should be avoided if possible. You can use the Akka library, but in my experience Akka is too heavyweight and complicated for most problems.

Clojure, on the other hand, has atoms, agents, and refs. These concurrency primitives are designed exactly for the concern of state management. These 3 items each hold a value as their current state and have methods for performing safe modification synchronously, asynchronously, uncoordinated, or coordinated, depending on which primitive you need. All have the same API for dereferencing, watching for changes, and validating state. These primitives completely separate the concern of state management from the other concerns described in this post. You can read more about these primitives here.

One really great thing about Clojure concurrency primitives is that they are easy to use from any other JVM language, so you can leverage them in your Java or Scala projects to separate this concern if desired.

Summary and Conclusions
The following table summarizes what I have discussed in this post.

StateObject FieldsValues/Data
BehaviorObject MethodsFunctions
ManagementObject ReferencesConcurrency Primitives
Separation LevelComplectedSeparated

The key takeaway is that objects fundamentally complect all concerns by their very nature. Clojure's separation of data, functions, and state management allow for a clean separation of these concerns as part of the language design. So, rather than beginning to design the world as objects, layers, and systems start with data, functions, and state. The former solution automatically puts you on the road to complexity while the latter allows you to keep your concerns separated all the way down.

Thursday, September 24, 2015

Clojure State Management by Example

One of my favorite features of Clojure is the way changes in application state are handled. In Clojure we separate the concerns of our data (which is stored as values) and the management of how that data might change over time. Contrast this to most other languages that have mutable state tied to their object model at some level.

There are four state management primitives. Here's a very simple example of each and how they behave.

Vars are what you get when you use def. def simply defines a value. If you declare the def'd value as dynamic, you can rebind it on a per-thread basis. Meaning, within your current scope you can rebind the value of the previously def'd value. Here's the example:
(def ^:dynamic *a* 0) ;Note the *earmuff*
(def ^:dynamic *b* 1) ;Clojure uses them for things mean to be rebound

(prn (str "(original) a, b = " *a* "," *b*))

  (binding [*a* 1 *b* 0]
    (prn (str "(rebinding) a, b = " *a* "," *b*))
    (binding [*a* 11 *b* 45]
      (prn (str "(another binding) a, b = " *a* "," *b*)))
    (prn (str "(exiting scope) a, b = " *a* "," *b*)))
  (prn (str "(exiting scope) a, b = " *a* "," *b*)))

(prn (str "(original ns value) a, b = " *a* "," *b*))
The above produces this output:
"(original) a, b = 0,1"
"(rebinding) a, b = 1,0"
"(original ns value) a, b = 0,1"
"(another binding) a, b = 11,45"
"(exiting scope) a, b = 1,0"
"(exiting scope) a, b = 0,1"
As you can see, every time I rebind a and b in a new form, the old value are replaced within that scope. As soon as the form is exited, we are back to the previous binding. Finally, you can see that the last prn statement that prints the original binding value is unaffected by the future since the future is in a different thread. I don't find vars particularly useful or interesting, but for completeness's sake, there you have it. Our next three concurrency primitives are much more interesting.

Atoms provide synchronous, uncoordinated state management. These are the workhorse of Clojure state management. Here's how it works using a simple example that updates two atoms and dumps out their results. A built-in delay is added to each update for illustration's sake.
(def a (atom 0))
(def b (atom 1))

(defn slow [f] (Thread/sleep 300) f)
(defn slower [f] (Thread/sleep 400) f)

    (swap! a (comp slow inc))
    (swap! b (comp slower dec))))

  (loop [i 10]
    (when (pos? i)
        (prn (str "a, b = " @a "," @b))
        (Thread/sleep 100)
        (recur (dec i))))))
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 1,1"
"a, b = 1,1"
"a, b = 1,1"
"a, b = 1,1"
"a, b = 1,0"
"a, b = 1,0"
"a, b = 1,0"

The above output illustrates that atoms are synchronous since it took 300ms for slow to execute on a and an additional 400ms for slower to execute on b. Also, the functions are uncoordinated - There is a time when slow has completed its work and slower has not. There is no connection between the two swap! operations.

Refs provide synchronous, coordinated state management. Use a ref when you need a transaction to be performed correctly. For example, you could use Refs to track funds in a bank account. To transfer funds from one Ref'd account to another, put the transaction in a synchronized ref block. The following example is identical to the above, except that now we are altering a and b in a synchronized code block.
(def a (ref 0))
(def b (ref 1))

(defn slow [f] (Thread/sleep 300) f)
(defn slower [f] (Thread/sleep 400) f)

    (alter a (comp slow inc))
    (alter b (comp slower dec))))

  (loop [i 10]
    (when (pos? i)
        (prn (str "a, b = " @a "," @b))
        (Thread/sleep 100)
        (recur (dec i))))))
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 1,0"
"a, b = 1,0"
"a, b = 1,0"

Unlike the previous example, no change occurred in a or b until both the slow and slower functions were applied to a and b. Since the operations were synchronous, it took the entire compute time of both functions to pass before both a and be were concurrently updated.

Agents provide asynchronous, uncoordinated state management. If you want reactive behavior, use agents. As before, we are using the same example to illustrate agent behavior.
(def a (agent 0))
(def b (agent 1))

(defn slow [f] (Thread/sleep 300) f)
(defn slower [f] (Thread/sleep 400) f)

    (send a (comp slow inc))
    (send b (comp slower dec))))

  (loop [i 10]
    (when (pos? i)
        (prn (str "a, b = " @a "," @b))
        (Thread/sleep 100)
        (recur (dec i))))))
"a, b = 0,1"
"a, b = 0,1"
"a, b = 0,1"
"a, b = 1,1"
"a, b = 1,0"
"a, b = 1,0"
"a, b = 1,0"
"a, b = 1,0"
"a, b = 1,0"
"a, b = 1,0"

In this case, we see that both slow and slower executed concurrently, since a was updated after 300ms and b was updated only 100ms later.

Clojure's concurrency primitives are very easy to use and make it simple to manage program state. However, it is important to know when to use which. Hopefully this simple set of examples will give you a clear idea as to the behaviors of each so that you'll know when to use them.

Friday, August 21, 2015

A Clojure Snake Game

I recently decided to write a Snake game in Clojure as a small project. In the game you have a snake that grows as it consumes food. The goal of the game is to make the snake as long as possible without self-intersecting. I got the idea to do it on a Saturday morning and by that night I was done. Most of the coding was done in the evening since I was doing family activities all day. All told, this was probably a 3 hour project. The entire program is 75 lines of code. That's awesome! This includes both the JVM and JavaScript targets via Clojure and ClojureScript.
Here's the game:

Here's how you play:
  • Use your arrow keys or w, a, s, d to change the snake's direction. Note that you probably will need to click on the canvas first to gain focus.
  • When the snake hits a green "food" pill it grows one unit longer.
  • When the snake intersects itself it resets to its original length.
  • Your score is the length of your snake.
The Program
Here's the program. Read past it for my observations and comments.

(ns snake.core
  (:require [quil.core :as q #?@(:cljs [:include-macros true])]
            [quil.middleware :as m]))

(def world { :width 100 :height 100 :food-amount 1000 })

(defn gen-food [] [(rand-int (world :width)) (rand-int (world :width))])

(defn replenish-food [initial amount]
  (loop [food initial] (if (>= (count food) amount) food (recur (conj food (gen-food))))))

(defn wrap [i m]
  (loop [x i] (cond (< x 0) (recur (+ x m)) (>= x m) (recur (- x m)) :else x)))

(defn grow-snake [{:keys [snake velocity] :as state}]
  (let [[px py] (map + (peek snake) velocity)]
    (assoc state :snake (conj snake [(wrap px (world :width)) (wrap py (world :height))]))))

(defn eat [{:keys [snake food] :as state}]
  (if-let [pellet (food (peek snake))]
    (-> state (update :food disj pellet))
    (-> state (update :snake subvec 1))))

(defn reset? [{:keys [snake] :as state}]
  (if (apply distinct? snake)
    (assoc state :snake [(peek snake)])))

(defn setup []
  (do (q/smooth)
      (q/frame-rate 30)
      {:snake [[50 50]] :velocity [1 0] :food (replenish-food #{} (world :food-amount))}))

(defn draw [{ :keys [snake food] }]
  (let [w (/ (q/width) (world :width))
        h (/ (q/height) (world :height))]
      (q/stroke-cap :round)
      (q/stroke-join :round)
      (q/background 0 0 0)

      (q/fill 0 255 0)
      (q/stroke 0 255 0)
      (doseq [[x y] food](q/rect (* w x) (* h y) w h))

      (q/fill 255 0 0)
      (q/stroke 255 0 0)
      (doseq [[x y] snake](q/rect (* w x) (* h y) w h))

      (q/fill 0 255 255)
      (q/text (str "Score: " (count snake)) 10 15))))

(defn launch-sketch [{:keys[width height host]}]
    :title "Snake"
    :setup setup
    :update #(-> % grow-snake eat (update :food replenish-food (world :food-amount)) reset?)
    :draw draw
    (fn [{ :keys [velocity] :as state} { :keys [key key-code] }]
      (case key
        (:a :left) (if (not= [1 0] velocity) (assoc state :velocity [-1 0]) state)
        (:d :right) (if (not= [-1 0] velocity) (assoc state :velocity [1 0]) state)
        (:w :up) (if (not= [0 1] velocity) (assoc state :velocity [0 -1]) state)
        (:s :down) (if (not= [0 -1] velocity) (assoc state :velocity [0 1]) state)
    :middleware [m/fun-mode]
    :size [width height]
    #?@(:cljs [:host host])))

;#?(:clj (launch-sketch { :width 400 :height 400 }))

#?(:cljs (defn ^:export launch-app[host width height]
           (launch-sketch { :width width :height height :host host})))

Observations and Comments
The state in this program is represented by a simple data structure containing a vector describing the snake, a vector representing the snake's velocity, and a set of coordinates representing the locations of food. You can see where I create this at the end of the setup function.There are also some constants in the world def.

To update the state, this program makes use of the common Clojure pattern of "threading state." Basically, you write your functions so that program state is passed in as an argument and a modified, updated version of the program state is returned. Functions with a single action or concern are written in this manner and then chained to form more complicated behaviors. It makes your program very easy to reason about. In this program you can see where this is done in the update method:

#(-> % grow-snake eat (update :food replenish-food (world :food-amount)) reset?)

For those unfamiliar with Clojure, I am using the "thread first" macro (The arrow). The # creates an anonymous function with the % as the passed in argument. The arrow takes the argument and feeds it through each function in succession (grow-snake, then eat, then updating food, and so on.).

At the program level, the Quil library handles passing state to each relevant function for processing. In "fun-mode" (functional mode), Quil functions hand you the initial state for modification in methods for program setup, update, and input. For drawing, state is passed in and there is no function output since you will draw your state to the screen. In other applications you can follow this same pattern of state management using Clojure's amazing concurrency primitives (atoms, agents, and refs). In fact Quil is just using an atom under the hood.

Other minor details:
  • There's a commented out form (;#?(:clj (launch-sketch { :width 400 :height 400 }))) towards the end. Uncomment this if you want to launch the file from a REPL. I leave it commented so that it doesn't launch when I do a cljsbuild.
  • For some reason, the (:gen-class) directive doesn't seem to have any effect in the cljc file, so I have a separate launcher.clj that defines a main method for uberjar builds. Clone the project if you want to see what I mean.
You can clone the project here.

Clojure continues to amaze me by repeatedly enabling me to do so much in such a small amount to time and code. Simple ideas, such as representing your domain as data structures vs. classes and the ability to thread your state throughout your program via functions make development in Clojure rapid and productive. Nowadays, whenever I get an itch to try out a new program or concept, I just sit down and model the domain as data and then start writing functions to manipulate the data. Before I know it, I end up with a complete program. It's a very powerful and fun way to write applications.

Thursday, August 6, 2015

Clojure is Homoiconic, Java is Not

Recently I was reading this article regarding what is (or was) new in Java 8 and took an interest in the following section on Lambdas:
Lambda Expressions, a new language feature, has been introduced in this release. They enable you to treat functionality as a method argument, or code as data. Lambda expressions let you express instances of single-method interfaces (referred to as functional interfaces) more compactly.
I did a quick Google search on "java lambdas" and this tutorial was the first hit. Once again, the same type of statement is made:
One issue with anonymous classes is that if the implementation of your anonymous class is very simple, such as an interface that contains only one method, then the syntax of anonymous classes may seem unwieldy and unclear. In these cases, you're usually trying to pass functionality as an argument to another method, such as what action should be taken when someone clicks a button. Lambda expressions enable you to do this, to treat functionality as method argument, or code as data.
The thing that struck me about these articles is the consistent statement that that Java Lambdas (a.k.a. anonymous instances of single method interfaces) are "code as data" because the function can be passed as an argument. I guess if you define data as "instances of classes or functions" then this description is fine, but when I read these articles this is what comes to mind:

Technically, the ability to assign a function to a variable or pass a function as an argument to another function means that your functions are "first class" which is a good thing. However, I would not call this "code as data." Another related term is "higher order functions." These are functions that take functions as their arguments or return functions as their results. Again, this is a very powerful language feature that Java now sort of does, but this is not "code as data."

What do I think of when I think of "code as data?" I think of "Homoiconicity." Google seems to agree, since when I type "code as data" into a search box the first thing that comes up is this Wikipedia article on Homoiconicity. Let's explore the concept in more detail.

What is Homoiconicity?
Often homoiconicity is defined one the following ways:
  • The code is written in the data structures of the language.
  • Code as data.
Those more familiar with the concept seem to use "Code as data" more, but I think the first definition is a bit more clear if you are getting started with the idea. Either way, I am going to illustrate the concept by showing how Clojure code is actually written as Clojure data structures. To contrast, I'll also show what "homoiconic Java" would look like. Finally, I'll show you a simple Clojure macro in which we rearrange our code/data.

Homoiconic Clojure
To start, consider the following core Clojure data structures:
  • () is an empty List.
  • {} is an empty Map.
  • [] is an empty Vector.
  • #{} is an empty Set.
When we write code in Clojure, it is expressed in terms of the above data structures. Here is a very simple example that applies the str function (it's kind of like .toString) to the number 42:
user=> (str 42)
You might look at this and think this is the same as the following Java code:
public static String str(Integer i){
    return i.toString();

The only difference is the location of the parenthesis, right? Wrong! (str 42) not actually the function str with the argument of 42, but is a list containing two elements, the str symbol and the value 42. When the Clojure evaluator sees a list it attempts to resolve the first symbol (str in this case) and calls that function with the remaining elements of the list as arguments. While this may seem like splitting hairs at the moment, this is very important when you get to macros. It is also crucial to the point that Clojure code is data.

Here's another one:
(defn add [a b](+ a b))
Again, you might think this is the same thing as this Java function:
public static int add(int a, int b){
    return a + b;
As before, they are not the same. The above Clojure add function is actually built up with two lists (one nested) and a vector of arguments. The inner list contains three symbols (+, a, and b) and the outer list contains the defn symbol, a symbol naming your function ("add"), a vector of arguments, and our inner list.

Here's another example:
(merge-with + { :x 1 :y 2 :z 3 } { :x 9 :y 2 :z 4 })
By this point you should see that we have a list, two maps, and a bunch of symbols and values as opposed to a function that adds two maps. Yes, the evaluator will merge the maps, but the code itself is data (as in the native data structures of the language).

You can do this type of structural breakdown with any Clojure code. Clojure programs are literal data structures consisting of nested literal data structures, values, and symbols. For more details, read this. The key takeaway is that we are indeed writing our code as a bunch of data (literal data structures containing nested data structures, values, and symbols).

Homoiconic Java
What if you wanted to write Java in its own data structures?

Here are our Java collection interfaces that correspond to the Clojure ones above:
  • java.util.List
  • java.util.Map
  • java.util.Vector
  • java.util.Set
Java, for some inexplicable reason, does not yet have collection literals, so this will be a very verbose exercise. My apologies up front.

Ok, now let's write some Java code in the data structures of the language:
    List add = new LinkedList();
Sadly, I have no way to evaluate this code, but, hey, it's data. I chose to use a String to represent the + operation because Java doesn't have symbols, either.

Here's another attempt at how I might construct some code as data in Java. I realize that this will be an utter failure, but you're just going to have to follow along as I write a ton of code to make my point.
    Map a = new HashMap();
    a.put("x", 1);
    a.put("y", 2);
    a.put("z", 3);

    Map b = new HashMap();
    b.put("x", 9);
    b.put("y", 2);
    b.put("z", 4);
    List mergemaps = new LinkedList();
Again, this can't be evaluated, but it's about as close as you can get to homoiconicity in Java.

Why Homoiconicity? - Macros
Consider this question: "What can you do with data?" Think about an Excel spreadsheet, a simple comma separated value file, or some JSON data. These are things you can easily sort, manipulate, and transform.

In the same way, Clojure code can be manipulated and transformed as data. In Clojure there is a facility for this called a macro. When Clojure evaluates macros, it does not evaluate the arguments as with a regular function. Rather, it passes the unevaluated arguments into the macro to be manipulated. Once this is done, the result is returned and evaluated.

Here's an example:
(defmacro bizzaro-math
  "Do everything the opposite of normal"
  [[op & rest]]
  (conj rest (case op
               + -
               - +
               * /
               / *
This macro takes its arguments and inverts the first argument if it is a basic arithmetic operator. Note that this would not be possible if the arguments were evaluated rather than treated as data. Here are some examples of it in use:
(bizzaro-math (+ 2 3))
=> -1
(bizzaro-math (- 2 3))
=> 5
(bizzaro-math (* 2 3))
=> 2/3
(bizzaro-math (/ 2 3))
=> 6
(bizzaro-math (rem 2 3))
=> 2
The most important thing to note here is that the inner forms (e.g. (+ 2 3)) are not evaluated, but are manipulated by the macro, then evaluated. This is the ultimate demonstration that we do, indeed, have code as data.

A more in-depth discussion of macros is beyond the scope of this post, but the main takeaway is that macros allow you to manipulate code. This is a feature unique to homoiconic languages.

Parting Thoughts
Code as data, a.k.a. homoiconicity, is the ability to write your code in the data structures of your language. This goes way beyond the simple ability to pass a function as an argument. If that's all you are looking for, Java might be all you need. If you want full on FP on the JVM, you've got better options. Scala is a great bridge language that has first class functions, higher order functions, partial evaluation, composition, and all the other things you'd expect from a functional language. Clojure, however, is King if want it all. Not only is it functional, it is truly homoiconic.

Further Reading:
Beating the Averages
Clojure For the Brave and True
Clojure Macros