Tuesday, December 1, 2015

Clojure: Getting Started

Introduction
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

Introduction
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:

Java
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;
    }
}
Scala
case class Person(name : String, age : Int, weight : Double)
Clojure
{ :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))

(pp/pprint
  (rename
    { :name "Zaphod Beeblebrox"
     :age 21
     :weight 160.0 }
    "Ford Prefect"))

(pp/pprint
  (rename
    { :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:

Java
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
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
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.

ConcernOOPFP
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

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

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

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

(future
  (loop [i 10]
    (when (pos? i)
      (do
        (prn (str "a, b = " @a "," @b))
        (Thread/sleep 100)
        (recur (dec i))))))
Output:
"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
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)

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

(future
  (loop [i 10]
    (when (pos? i)
      (do
        (prn (str "a, b = " @a "," @b))
        (Thread/sleep 100)
        (recur (dec i))))))
Output:
"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
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)

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

(future
  (loop [i 10]
    (when (pos? i)
      (do
        (prn (str "a, b = " @a "," @b))
        (Thread/sleep 100)
        (recur (dec i))))))
Output:
"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.

Summary
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

Introduction
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)
    state
    (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))]
    (do
      (q/smooth)
      (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]}]
  (q/sketch
    :title "Snake"
    :setup setup
    :update #(-> % grow-snake eat (update :food replenish-food (world :food-amount)) reset?)
    :draw draw
    :key-pressed
    (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)
        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.

Conclusion
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

Introduction
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)
"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();
}

str(42);
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();
    add.add("+");
    add.add(1);
    add.add(1);
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();
    add.add("merge-with");
    add.add("+");
    add.add(a);
    add.add(b);
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
               + -
               - +
               * /
               / *
               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

Wednesday, July 22, 2015

Three Reasons You May Not Want to Learn Clojure

Introduction
I've been coding in Clojure for over a year now and not everything is unicorns and rainbows. Whatever language you choose will affect how you think and work and Clojure is no different. Read on to see what some of these effects are and why you might want to reconsider learning Clojure.

1. You will write at least 10X less code than your Java counterparts
Often, the measure of a library or project is its size. Programmers like to compare the size of their projects, just like muscle car people like to compare the size of their engines. Here are some situations where this might happen:
  • Lunch with buddies
  • Job interview
  • Internal performance evaluation
Here's a typical conversation:

You: "Yeah, I just finished delivering the Awesome 2000."
Them: "Oh, yeah? Tell me about it."
You: "Well, it is this software product that simultaneously creates world peace, solves world hunger, and saves the environment. Zero carbon footprint, too."
Them: "Cool, how many lines of code was that?"
You: "Oh, like 2 million."
Them: "Wow, awesome."

You will now get a high five, a job offer, or a big raise depending on who you are talking with. However, if you stated that the number of lines of code in your product was 200 then the response might be more along the lines of "Oh, a toy program written in a toy language." For some reason, probably because it is easy, many people like to equate lines of code with programming ability rather than some other metric like, oh, I don't know, the actual features of the programs you've developed. Clojure, sadly, excels at implementing features but is very poor at being verbose about it.

If you want to demonstrate your ability to code by writing lots of it, Clojure is a terrible, horrible, no-good language. I can't think of another language that is worse in this respect. You will never be able to brag again, in an circumstance, about how big your code base is compared to someone else's.

2. You won't be marketable for certain jobs
True Story: Once upon a time I was at a job interview and the interview panel asked me to go up to the board and code up a Fibonacci sequence generator. I asked what language they wanted it in and they said they didn't care, but they were a C++ shop. Since they didn't care, I wrote a very short tail-recursive Scala version which I am sure they found incomprehensible. I used to program in C++ and at one time I think I was quite good at it. However, I am just not that interested in C++ any more. It was a great job interview because I didn't get the job. I am sure that the story would have ended the same had I done the exercise in Clojure, except for the parenthesis would have been in the right place.

If you want to be a professional Clojure programmer, there will be a smaller number of job openings for someone of your skills and interests than for the standard Java or C# developer. If you are interested in being part of a clone army doing widely-available boring work, Clojure is not for you.

3. You will get things done faster
Clojure makes you productive, really productive. So, if you can get a product to market 3-10 times faster than you once could, what does your employer do with all that extra time you just bought them? Fire you and pocket the savings, that's what! Just kidding. Mostly.

While it is true that a company might take advantage of their newfound savings in cost and time by eliminating the software team that just bought them the savings, the more likely scenario is that 1) they will reapply you to something else; or 2) if they are trimming fat, you aren't part of it. Often you will become the new go-to person for getting things done because you've demonstrated an ability to get things done. This does lead to problem 3a: You have too much work to do because you are a productivity magnet.

While you can't predict what your employer will do in a given situation, one constant you can be sure of in the current software job market is that you must be agile. If you demonstrate value you can be sure that will have the opportunity to continue to demonstrate value. If, on the other hand, you resist change you will eventually be phased out by your own employer or by another company that displaces yours entirely.

Conclusion
Yes, Clojure is an enabling and empowering language, but this is not without its down sides. I didn't even get into some of the other issues, like not having the opportunity to rewrite your Java code in JavaScript because Clojure compiles both ways. If these are the kinds of problems you like to deal with, you just might want to give Clojure a try.

Shameless Plug
Like this blog? Please share, subscribe, or follow it (just enter your email at the top right).

Tuesday, July 14, 2015

Quil, Clojure, and WORA

Introduction
Since my last post, I've been playing with the excellent Quil library, a "Clojure/ClojureScript library for creating interactive drawings and animations." Prior to this, I was writing demonstrations using the following scheme:
  1. Develop all logic using cljc files (cljx before Clojure 1.7). In general, application logic is pretty platform-independent and can be wholly or nearly-wholly written in whatever language you are working in (Clojure in our case). Any slight variances (e.g. having to create a java.util.Date or a JavaScript Date) can easily be handled by Clojure's new Reader Conditionals.
  2. Decide on a UI technology (likely Java Swing with Java2D or HTML Canvas depending on what type of demo I wanted) and implement a front end using that particular choice.
  3. Optionally implement the "other" solution from #2 so that I now have a Java and JavaScript solution.
This strategy works pretty well, but I still have duplication of effort when it comes to the user experience. The awesome thing about Quil is that it allows you to launch your UI as either a Clojure or ClojureScript application targeting the JVM or JavaScript-enabled browser, respectively. Now, I can pretty much write everything as cljc files with a few reader conditionals and easily produce targets that run on the JVM or in a browser.

To get my feet wet with Quil, I re-implemented the renderer for my Lunar Lander project in Quil. I was so happy with the results that I removed the Canvas/ClojureScript renderer completely and now just use a single renderer for both the JVM and JS versions of the project.

Results
By the time I was done with my new rendering code and refactoring of everything else, all of the cljs files were gone. I now have a single clj file that is nothing more than a (:gen-class) macro and a main function calling the application entry point in the cljc code. Everything else is written as cljc files. Only a small number of reader conditionals were used to make any Clojure or ClojureScript specific changes as required. Rather than go over every example of how I used reader conditionals, take a look at this file that demonstrates how to create a single Quil "Sketch" that works with both host platforms. Aside from the above linked file, the only other conditionals required were a couple java.util.Date vs. JavaScript Date conditionals used in the simulation namespace. The vast majority of the code was identical for all hosts.

Conclusion
I've been developing code for the JVM for over 10 years and have always liked the "Write once, run anywhere" (WORA) aspect of JVM languages, and have found that WORA works for the most part. However, you can't always rely on your host machine having a modern JVM, especially in the era of mobile devices. The browser is really the most ubiquitous host platform, and the ability to write a single application that can be compiled to run as a JVM app or a JavaScript app with very little effort is a huge advantage for Clojure and Clojurists.

Afterthoughts
The complete application described in this blog can be found here. Note that you will need to build and install my numerics project as well. Once numerics is installed, cd over to lander and type lein run for the Clojure version of the game. You can play the web version right here (Note that you will need a keyboard or some way to emulate the 'f' key and left and right arrow keys.).

Wednesday, June 24, 2015

A Lunar Lander Game in Clojure

Introduction
In a prior post, I spent a great deal of time talking about Predator-Prey systems, ordinary differential equations, and solving these equations in Clojure. In this post, I describe a recent project I did that uses the same ODE solver to do something much more fun - implement a physics-based lunar lander game.

Here are the rules and operations for the game:
  • To win, you must land the lander on the terrain with a rotation of 0 and an absolute vertical velocity less than 10 m/s.
  • To engage the lander's thruster, press the 'f' key or space bar.
  • To turn the lander, press the left and right arrow keys.
  • If you go off the edge of the screen, land too fast, or land at an angle, you lose.
  • Press enter to start/restart the game.
The simplest solution is to just press the space bar when you get pretty close to the ground and carefully tap it so that you land very slowly. To give yourself a little challenge, turn the lander and give yourself some horizontal thrust. Then try to land it. I may later enhance the game with landing zones so you can't just land anywhere, but for now you can land anywhere you want.

Without further ado, here's the game:

If you are reading this blog via an aggregator that doesn't pick up the .js content, this is what the game looks like:

Implementation/Clojure Details
Now that you've had some fun trying the game out, here are a few high points. I won't go into a lot of detail in most of these sections since each could be a post in and of itself, but I will spend a good amount of time on multimethods, which were a big win in this application. If you want to build it, the entire project is available at https://github.com/markbastian/lander. Note that you will need to clone my numerics library for the Runge-Kutta solver and lein install it.

Platform Compatibility
Clojure 1.7 (Currently RC2) has the new cljc extension, which makes cross-compiling Clojure and ClojureScript a breeze. It is much easier and faster than the old cljx solution. I didn't make a JVM-based solution in parallel this time, but it would be pretty easy.

Game Physics
This was one of the easiest parts of the game since I just modeled the lander using differential equations and stepped forward using a Runge-Kutta integrator at each simulation step. The differential equations are:
\({dp\over dt} = v\)
\({dv\over dt} = -9.81 + thrust\)

Thrust is only applied when the user turns it on and the actual solution breaks the position (p) and velocity (v) vectors up into their x and y components.

And here's the code:
(defmethod sim :live [state-ref]
  (let [{:keys [theta thrust time state]} @state-ref
        t (.getTime (js/Date.))
        dt (* (- t time) 1E-3)
        dvx #(-> theta (* Math/PI) (/ -180) Math/sin (* thrust))
        dvy #(+ -9.81 (-> theta (* Math/PI) (/ -180) Math/cos (* thrust)))
        new-states (rk/rk-step [#(% 3) #(% 4) dvx dvy] state dt tableaus/classic-fourth-order)]
    (swap! state-ref into { :state new-states :time t })))

Terrain
Terrain is generated using the midpoint displacement method (source). Read about it here. Every new game procedurally generates a new terrain profile. There's a good chance I'll do a full on 3D terrain generation algorithm for a future blog post.

State
State is held in a single atom. As usual, when writing Clojure apps, I just modeled my problem as a data structure held by a Clojure concurrency primitive and everything else fell into place. The values tracked were game state (discussed later in the multimethods section), physical simulation state, time, theta (the lander's rotation), thrust (toggled on and off by user input), and terrain. All of this was easily managed in a single atom. One of the most beautiful things about Clojure is the simplicity of modeling your domain. When you stop thinking in objects and start thinking in terms of data and functions on data, life becomes much simpler.

Project Size
The project is ~200 LOC. Not too shabby for a complete game. There are certainly areas where I could have further reduced the amount of code, such as in the rendering section, but there comes a point where everything works fine and there's no need to mess with it further. Although I don't believe in brevity for brevity's sake, I do believe less code is easier to maintain and navigate than more code, so I always appreciate a concise solution.

Multimethods - The Big Win
In a computer game, you will have different stages of play, or game states (not to be confused with the physics state being maintained in the sim loop). For example, when you start a game there is a setup stage. Once everyone has joined there is a main game phase in which most play occurs. Finally, when someone wins there is usually some sort of congratulatory display or an option to play again. Each stage or game state entails a different set of rules regarding what input is received, what is rendered, and so on. However, each state has common functions such as receiving input and rendering. This is where Clojure multimethods come into play - they allow you to call the same overall game logic, but dispatch different functions based on some custom function.

In this game, the game is in one of four states:
  1. :before - The state of being before any game has been played.
  2. :live - A game is currently being played.
  3. :win - A game has been played and you won.
  4. :lose - A game has been played and you lost.
Depending on the state of the lander game, different logic is executed for the input, rendering, and simulation functions. For example, in :before, :win, and :lose state the game only allows you to start/restart a game, where in :live state the game accepts input to control the lander. In :live state the game renders the lander, terrain, and stats. In :before state the game only renders its directions.

The cool thing about all of this is that in Clojure I only have one main game loop (shown below). It repeatedly calls game-state, state, and render. At the same time, input is taken via the handle-keydown and handle-keyup methods. What happens when these methods are invoked depends on the current game state, with the right logic being dispatched via multimethods.
(defn ^:export init[canvas]
  (set!
    (.-onload js/window)
    (let [state (atom { :game-state :before })]
      (do
        (js/setInterval #(do
                          (gs/game-state state)
                          (sim/sim state)
                          (render/render state canvas)) 1)
        (set! (.-onkeydown js/document) (fn [e] (in/handle-keydown state e)))
        (set! (.-onkeyup js/document) (fn [e] (in/handle-keyup state e)))))))

Here is how it is done. I have 5 methods that I am invoking polymorphically based on the current game state (Note that they are shown together here, but are in separate files in the project):
;Watch the actual game state and transition to a new state based on the current physical state.
(defmulti game-state (fn [state] (@state :game-state)))

;Simulate the physics of the game based on the game state.
(defmulti sim (fn [state] (@state :game-state)))

;Draw to the screen based on the game state.
(defmulti render (fn [state _] (@state :game-state)))

;Handle input based on the game state.
(defmulti handle-keydown (fn [state _] (@state :game-state)))
(defmulti handle-keyup (fn [state _] (@state :game-state)))

The actual function dispatched when a defmulti is called depends on the dispatch function. In this case the dispatch function is (fn [state] (@state :game-state)). Now that I've defined the multimethods and their dispatch functions, I need to create methods that dispatch based on the right game state. Here's how it works for the render multimethod:
(defmulti render (fn [state _] (@state :game-state)))

(defmethod render :before [_ canvas] (intro-screen canvas))

(defmethod render :win [state canvas]
  (do
    (draw canvas @state)
    (win-screen canvas)))

(defmethod render :lose [state canvas]
  (do
    (draw canvas @state)
    (lose-screen canvas)))

(defmethod render :live [state canvas] (draw canvas @state))

So, given the state of the game, different render methods are called based on the state of the game. The same is true for all of the other multimethods defined above. For example, the :live method for the sim multi method was shown earlier. When the game is not in a live state, it simply calls the method show below, which conveniently makes the lander stop wherever it was when the game ended.
(defmethod sim :default [state-ref] ())
I won't go through all of the methods I defined, but you should get the idea from what I've posted. Multimethods provide a very effective and powerful way to dynamically dispatch different behaviors based on a custom defined function.

Finally, I could have defined my multimethods in one common namespace and provided implementations in another. Had I chose to provide both HTML Canvas and Swing/Graphics2D versions of this application, I could have implemented a single game loop that performs all logic in terms of multimethods and defined implementations in separate namespaces. Depending on which version of the application I wanted to run I would require the corresponding namespaces.

Conclusion
In this post, I presented a lunar lander game written in Clojure along with some observations about the code. As with my other Clojure projects, I am impressed by how I can make a non-trivial application with such a small amount of code. Various aspects of Clojure contributed to this, but the thing that most impressed me with this particular application was the use of multimethods to easily transition between game states and manage which functions should be dispatched under what conditions.

Thursday, June 11, 2015

Differences between Null, Nil, nil, Some, and None

Introduction
During a recent code review, a coworker who had the good fortune of jumping straight from Java to Clojure was asking me a few questions about some Scala code she'd been asked to edit. The particular problem involved recursive accumulation of some list data and our conversation drifted towards some questions regarding the different-yet-similar-sounding terms in these JVM languages. Java, Scala, and Clojure together have Null, Nil, nil, Some, and None. Most of these are related in their respective languages to how exceptional behaviors are handled with respect to references and/or collections. Here I explain each of these from the perspective of their host languages and my opinion of the effectiveness of each solution.

Before diving in, let me be clear that null exists in all JVM languages, including Scala and Clojure. However, these and other more modern languages provide additional facilities for dealing with situations where Java would default to using null and/or throw NPEs.

Java
In Java, you may encounter null when using an uninitialized reference (the default value for all references is null), when attempting to get a collection element that doesn't exist, or when someone decides to return null from their function to indicate a bad result. Java has no special handling for null. If you try doing anything with a null value, you get a NullPointerException and all is lost.

Not only is trying to do something with null exceptionally bad, Java (pre 8) has no built-in mechanisms to help you out. You just do lots of null checking.

Here are some methods for dealing with null in Java:
  • Always check your references. Liberally spread if(foo != null){ /*Do stuff with foo here*/ } everywhere you don't have absolute control of your references and aren't absolutely sure foo is initialized.
  • Always initialize your references at declaration or (preferably) make them final. Effective Java Item #15 says "Minimize Mutability." I find it very hard to be effective when writing Java, but this is definitely a good tip. Whenever possible, make everything final with a meaningful (i.e. non-null) value.
  • Don't write your code in Java. There are some perfectly good alternatives (See below).
  • Use the new Optional class from Java 8. This is the similar to Scala's Option type so I won't say much here aside from saying that Scala had it first. There's a trend there.
Scala
Recognizing the evils of null and NullPointerExceptions, Scala designed a better way - the Option type. Rather than returning null when something goes bad, the Scala way is to return either Some value if the computation succeeded or None if it failed. Here is an example of how you might use Option types to model a random food grab into your refrigerator:
  /**
   * A really lame function that might return a random food.
   */
  def randomFood = math.random match {
    case x if x > 0.75 => Some("Ham")
    case x if x > 0.5 => Some("Cheese")
    case x if x > 0.25 => Some("Bacon")
    case _ => None
  }
If you made a call to randomFood you could then call isDefined or isEmpty on the result to see if a meaningful result was returned. If the result is meaningful you can then call get to retrieve the value stored in the Some. In reality, nobody ever does this because it isn't any better than performing a null check. The only time you might do this is when calling Scala from Java because Java doesn't understand Scala functions.

What people really do with Options is use the fact that Scala implicity converts them to Iterables to perform functional operations on them. You can use functions on Options like map, foreach, flatten, reduce, and so on. Here's an example:
val sandwich = Some("Bread") :: 
  ((0 until 10) map { _ => randomFood }).toList ::: 
  Some("Bread") :: Nil

//Prints something like List(Some(Bread), Some(Ham), Some(Ham), None, Some(Bacon), Some(Bacon), Some(Ham), None, Some(Ham), Some(Bacon), None, Some(Bread))
println(sandwich)

//Prints something like List(Bread, Ham, Ham, Bacon, Bacon, Ham, Ham, Bacon, Bread)
println(sandwich.flatten)
Scala also has Nil, which is the empty list. Nil is the odd man out in this post as it is a specific instance of an empty collection rather than a construct for handling exceptional behavior, especially with respect to null. Due to Scala's powerful type system and inferencing, the Scala compiler will figure out what kind of list you are working with as soon as you add some items to your list.
scala> val x = 1 :: 2 :: 3 :: Nil
x: List[Int] = List(1, 2, 3)

scala> Nil
res0: scala.collection.immutable.Nil.type = List()
As you can see in the last line, Nil can't infer a type when no elements of any type are provided. Sometimes using empty collections like this in Scala can cause problems in which the compiler can't infer the type information. In such cases, you can just declare the type when declaring the def or val (we don't use vars). Here's an example that illustrates the point:
scala> Some(4) map { x => x * x } getOrElse 0
res0: Int = 16

scala> Some(4.0) map { x => x * x } getOrElse 0
res1: AnyVal = 16.0

scala> None map { x => x * x } getOrElse 0
<console>:8: error: value * is not a member of Nothing
              None map { x => x * x } getOrElse 0
                                ^
scala> val n : Option[Double] = None
n: Option[Double] = None

scala> n map { x => x * x } getOrElse 0
res3: AnyVal = 0

scala> n map { x => x * x } getOrElse 0.0
res4: Double = 0.0
As can be seen from the example, using operations such as map and getOrElse are convenient ways to transform Optional types to desired outputs. At the same time, care must be taken to make sure type information isn't lost so that you get the expected result. Despite these potential pitfalls, Scala's ability to treat Options as Iterables makes dealing with them very convenient.

Overall, Option is a much better solution than dealing with frequent null checking.

Clojure
Being hosted on the JVM, Clojure's nil is identical to Java's null. However, how Clojure treats nil is very different from Java. Rather than exploding every time nil is used a la Java or adding special features to handle exceptional behavior a la Scala, Clojure has a few simple rules that make it easy to work with nil. First, in logical expressions nil logically evaluates to false (along with false itself). In Clojure we call this "truthiness" and it is awesome. Second, when dealing with collections nil is treated like an empty list. These simple rules result in a simple, elegant solution to the dreaded null problem and it also results in a lot less code. To illustrate, here's our random food grab function in Clojure:
(defn rand-food []
  (condp < (rand)
    0.75 "Ham"
    0.5 "Cheese"
    0.25 "Bacon"
    nil))
As you can see, I don't do anything special (No Some/None construct) and just return nil (which is null in Java). It is the simplest solution, which is what Clojure is all about. In Java, this solution would be error-prone since it is using null. Here's how it works in Clojure:
(let[food (take 10 (repeatedly rand-food))
     layers (filter identity food)]
  (conj (into ["Bread"] layers) "Bread"))
=> ["Bread" "Ham" "Bacon" "Cheese" "Ham" "Bacon" "Ham" "Bacon" "Bacon" "Ham" "Ham" "Bread"]
Here's another snippet of examples that show how Clojure deals with nil when it is placed in the position of a null argument or collection. Compare or in Clojure with getOrElse in Scala. Much simpler.
(reduce + (map #(* % %) [1 2 3])) ;A non-nil example
=> 14
(reduce + (map #(* % %) nil)) ;I can reduce into a nil collection
=> 0
(or nil 4) ;Compare to getOrElse in Scala
=> 4
(and nil 4) ;Both items must exist
=> nil
(conj nil 4) ;I can conjoin 4 to nil to create the list (4)
=> (4)
As with Scala, Clojure provides a better way to handle null than Java. In contrast to Scala, Clojure does not add any special classes to handle null. Rather, it uses slightly different rules so that nil has meaning in collection and logical operations. For more on nil in Clojure, read about "nil punning" here.

Hands down, I prefer Clojure's handling of nil to either Scala or Java's approach.

Conclusion
Null is a unavoidable fact of life. Sometimes things go wrong and the best answer is no answer. How this situation is dealt with depends very much on the language you are working in. Java, realizing that null is bad, throws lots of exceptions that you get to deal with, usually with lots of error checking. Scala provides a mechanism to return something (Some value) or nothing (None) that allows you to more easily deal with situations that might go bad. Clojure has a few rules for how to deal with nil, primarily the concepts of "truthiness" and treating nil like an empty list. The rules pretty much solve all your problems when it comes to nil.

These approaches shed light on the designs of these languages, especially the more recent ones. Scala is, in my opinion, a complicated language that solves many problems via additional mechanisms to deal with the problems inherited from Java. I still think it is a great language, but it does take a decidedly baroque approach to solving problems. Clojure, despite seeming otherworldly at first, is a truly simple language. The more I use it, the more impressed I am with its simple design and philosophy. Either way, I think you'll find either of these language's solutions to the null problem preferable to Java's.

Wednesday, May 27, 2015

Exercises in Clojure with Commentary

Introduction
I was recently browsing some links from my Twitter feed and came across some programming exercises and their solutions. I selected a few that I thought were interesting, solved them, and now I want to present my solutions here along with some commentary on how they were solved. I think the solutions and especially their comments might be helpful to new Clojurists as well as Java developers who are looking for some examples of why Clojure code is so much more concise. Without further ado, here they are.

Problem 1: Square Code/Crypto Square
Read all about it here and here. Basically, you do the following to encode a text string:
  1. Convert the initial string to a lowercase character string with only alpha characters
  2. Arrange the result of step 1 into a square of text (If the string length is not a square integer the last line will not be as long as the rest of the square)
  3. Create a sentence in which the "words" are the columns of the square
Here is my solution:
(require '[clojure.string :as s])

(defn crypto-square[s]
  (let[ss (-> s s/lower-case (s/replace #"[^a-z]" ""))
       l (-> ss count Math/sqrt Math/ceil int)]
    (->> ss
         (partition l l (repeat ""))
         (apply map vector)
         (map #(apply str %))
         (s/join " "))))

You can give it a try right here:


Enter text to encode:
Result:

Commentary:
  • This solution makes heavy use of threading macros (-> is called "Thread first" and ->> is called "Thread last"). These are great for assembling computation pipelines. These macros take the item after the arrow and repeatedly insert the argument into the next form in the pipeline, carrying forward the result into each successive form. The "first" and "last" refer to where in the succeeding form the new argument goes (first goes after the function name in the form, last goes in the last position in front of the last parens).
  • The partition function creates partitions from a sequence with a specified chunk and step size. A final default argument is used to pad the last partition when the sequence cannot be equally subdivided.
  • The default padding argument to partition along with the repeat function make ensuring that the string was square trivial. Any missing characters in a non-square string are filled in by padding with empty strings.
  • The apply method (which I use in several more of these examples) "applies" a function to a sequence by inserting the function in the first position of the sequence and evaluates the new sequence as if it were a list.
  • A key takeaway in this example is that threading computations as shown really only works with immutability and side-effect free functions. Were either of these properties missing, there are no guarantees regarding your computations and assembling these sorts of pipelines are impossible.
Problem 2: Kindergarten Garden
In this problem, described here and solved here, two rows of plants are assigned to a group of students who are sorted alphabetically by name. Each student gets a block of plants from left to right (two each in the front row and two each in the back). Depending on the letters in the diagram, you are to determine which kind of plants each student has.
;Solution 1
(defn char->plant[s]
  (map #(case %
         \V "Violets"
         \R "Radishes"
         \C "Clover"
         \G "Grass") s))

(defn kinder[names rows]
  (apply merge-with concat
         (map
           #(zipmap (sort names) (partition 2 %))
           (map char->plant (s/split-lines rows)))))

;Solution 2
(defn kinder-thread-last[names rows]
  (->> rows
       (s/split-lines)
       (map #(map { \V "Violets" \R "Radishes" \C "Clover" \G "Grass" } %))
       (map #(zipmap (sort names) (partition 2 %)))
       (apply merge-with concat)))
Results:
(def ch ["Alice" "Bob" "Charlie" "David" "Eve" "Fred" "Ginny" "Harriet" "Ileana" "Joseph" "Kincaid" "Larry"])
(def rows "VRCGVVRVCGGCCGVRGCVCGCGV\nVRCCCGCRRGVCGCRVVCVGCGCV")
(prn ((kinder-thread-last ch rows) "David"))
;prints ("Radishes" "Violets" "Clover" "Radishes")
Commentary:
  • I provided two solutions. My first did not use threading macros. I think the thread last version (#2) is much easier to read. It is quite easy to see the sequence of steps being followed.
  • Another important thing to note is how I mapped the characters in the gardens to plants. I can use a case statement like what is done in the char->plant function. However, a simpler and more concise solution is to simply use a map. Clojure maps (and vectors and sets) are not just data structures, but are also functions. This may seem weird at first, but it actually makes sense. A map (in any language) is simply a discrete 1:1 function that maps keys to values. A vector is a function of its indices and a set is a function of its contents. Using this knowledge, I just mapped the characters in the strings using the map of characters to plant names as an inlined function.
Problem 3: Treasure Hunt
In the treasure hunt problem described here you are given a 2D array of two digit map coordinates. From a starting coordinate that I am assuming comes from a pirate, you look up each successive coordinate on the map by using the first and second digits of the current coordinate as the row and column on the map. Once a coordinate maps to itself, start digging, you are done.

Here is my solution:
(defn map-step[m clue]
  (let [n (get-in m [(dec (quot clue 10)) (dec (rem clue 10))])]
    (when (not= n clue) n)))

(defn treasure-hunt [m start]
  (take-while identity (iterate (partial map-step m) start)))
Here it is in action:
(def treasure-map [[34 21 32 41 25]
                   [14 42 43 14 31]
                   [54 45 52 42 23]
                   [33 15 51 31 35]
                   [21 52 33 13 23]])

(prn (treasure-hunt treasure-map 11))
;prints (11 34 42 15 25 31 54 13 32 45 35 23 43 51 21 14 41 33 52)
Commentary:
  • The map-step function simply computes the next step in the map. What's beautiful about this method is that it very naturally uses the Clojure get-in function to solve the problem. get-in is a Clojure function that allows you to drill down into a nested data structure by providing a vector of successive indices. Conveniently, our two-digit coordinates can be split into a vector for get-in access. Note that I do need to decrement the coordinates to make them 0 indexed.
  • The only additional logic required was the exit criteria. I compared the looked up coordinate to the input. If they are different, I return the update. Otherwise, nil is returned.
  • The treasure-hunt is where the real awesomeness happens. I can create a partial map-step function by filling in the first argument of the function with a treasure map. I now have a function that takes an [x y] coordinate and returns an [x y] coordinate. I want to repeatedly do this until I return nil. Sounds like a perfect candidate for Clojure's iterate function. iterate takes a function and an initial condition and repeatedly returns the result of the applied function and reapplies that result to itself. To determine a stopping condition, I take results while the function satisfies the identity function. Identity is a clever method that simply returns what is passed to it. In Clojure, anything not false or nil will pass logical truth tests (this is called truthiness), so as long as my function returns new coordinates I will take coordinates from it.
  • It is quite common in Clojure to store your state in a structure and do a computation that returns a new state that is similarly structured to the original. Whenever you do this, iterate may be a great option. You can take a certain number of items from the iterated function or continue until a stop condition is met.
  • Finally, this problem really is one of data navigation, and that is something Clojure excels at. Clojure is all about nested heterogeneous data structures and has many methods to safely inspect, update, and transform them. Furthermore, Clojure's semantics for truthiness and handling of nil makes what would normally be exceptional behavior simple to handle.
Problem 4: Queen Attack
The basic problem is this:  Given two queens on a chessboard, are they in an "attack" configuration. In other words, are they in a shared column, row, or diagonal. Here's a solution from my original browsing exercise. As presented here, the problem is to encode an 8x8 board using different characters. I took a different approach and simply used the coordinates of the pieces to determine if they were visible to each other.

Here is my complete solution:
(defn queen-attack?[w b]
  (let [diff (map - w b)
        zs ((juxt first second #(reduce - %) #(reduce + %)) diff)]
    (true? (some zero? zs))))
Here are a few invocations of the function with results in comments:
(prn (queen-attack? [2 3] [2 10])) ;true - same row
(prn (queen-attack? [9 10] [2 10])) ;true - same column
(prn (queen-attack? [4 3] [2 10])) ;false
(prn (queen-attack? [7 12] [5 10])) ;true - same diagonal
Commentary:
  • The most important thing to note in this solution is that being on the same row, column, or diagonal reduces to simple difference checks on the piece indices. A zero difference in the row or column means you are on the same row or column. If the sum or difference of the row and column change is 0 you are on the same diagonal. If this last rule doesn't make sense, stop for a second and think about it. To move diagonally, you must move the same amount up or down as you do left or right. So, the sum or difference (depending on direction) will be 0.
  • I use juxt to compute the 4 potential zeroes. I also discuss juxt at length in this post.
  • some zero? checks if any zeroes exist. If any exist, the result is true. It none exist the result is nil. Therefore, I call true? to covert a nil to false. Note that Clojure uses "truthiness" when doing logic checks (i.e. nil and false return false, everything else returns true). So, I could just as easily drop the true? check if I felt like it.
  • Probably the biggest takeaway from this problem is the difference between a standard OOP solution vs. an FP solution. In OOP the natural approach to the problem would be to start with a  nice class hierarchy such as a Board (which would contain 64 Squares). You would probably have a ChessPiece class which you'd extend into Pawn, Rook, Knight, Bishop, Queen, and King classes. At this point you'd probably determine some basic methods such as move and attack which would allow you to finally approach solving the problem. In FP, you generally think directly in terms of what you are trying to do since your domain model is just data. Had I been asked to solve the problem for all chess pieces in Clojure, I'd probably just create a multimethod that dispatches on the attacker type (:pawn, :rook, :knight, :bishop, :queen, or :king). Each resulting defmethod would be as concise as the above function.
Conclusion
In a few short lines, I was able to solve 4 programming puzzlers using Clojure. While none of the problems were particularly hard, each illustrated several interesting functions and aspects of Clojure programming that I thought were worth pointing out. In particular, Clojure excels at representing, manipulating, and navigating data as simple structures. I find it much easier to model the data directly using Clojure's data structures than developing elaborate class hierarchies for each problem. This way of thinking allows you to jump right into solving your problem without having to spend a lot of time figuring out how to represent the data.

If you liked this page or learned anything from it, please tweet the link,follow me on Twitter, and/or follow this blog. Your support and interest is the fuel that drives the effort.




Friday, May 15, 2015

FP from the Fire Hose

Earlier this year I gave a presentation at work entitled "Functional Programming (FP) from the Fire Hose." My goal was to present, to a mostly OOP audience, some of the basics of FP while also providing examples that show that FP isn't just academic. You can't sell people on FP with concepts alone. People's eyes just glaze over and roll back into their heads when you start talking functional concepts like first class and higher order functions, immutability, statelessness, referential transparency, homoiconicity, and the like (I won't even say the M-word). With that in mind, I tried to go fast on FP and show several clear examples that demonstrate FP in action, even at a very small scale.

In my presentation, I do (or attempt to do) the following:
  1. Explain FP in 5 minutes to an OOP audience
  2. Explain why functions are important using collections as the context.
  3. Explain that first class functions are a necessary but not sufficient condition for FP. You also must have immutability.
  4. Solve a small problem in both FP and OOP style. The examples, written in Clojure and Java, respectively, show the simplicity and power of FP vs. traditional OOP.
  5. Demonstrate how you can write functional code in a stateful application using Clojure concurrency primitives.
Here's the video and links to additional resources. I hope you enjoy.



The slides are here, and the accompanying repo and demo are here.

If you liked this page or learned anything from it, please tweet the link,follow me on Twitter, and/or follow this blog. Your support and interest is the fuel that drives the effort.

Saturday, April 11, 2015

A-maze-ing Mazes with Clojure

Mazes can be pretty fun. Children love them. Add a dungeon theme (e.g. monsters, loot, and a dragon boss) and most computer programming adults like them, too.

In this post, I'll show you how to make some mazes in Clojure/ClojureScript. Feel free to print some off for your next trip with your kids or adapt this code to your next campaign if you are a DM.

The techniques I'll be covering are Prim's algorithm and Depth-First Search with Backtracking. Afterwords, I'll show you the code and discuss some interesting points.

Here are the algorithms:

Prim's Algorithm
This algorithm will produce mazes with a fair amount of branching and not a lot of long corridors. Here are the steps in the algorithm:
  1. Mark all cells in your maze as undiscovered.
  2. Select a start cell and mark it as visited.
  3. Mark all neighbors of the start cell as frontier cells.
  4. Randomly select a cell from the frontier as your next cell.
  5. Add it to the maze.
  6. Add any neighbors of the selected cell that are undiscovered to the frontier.
  7. Connect the selected cell to the maze by randomly selecting an adjacent cell that is already in the maze and mark the two cells as connected.
  8. If the frontier is not empty, goto 4. Otherwise, your maze is complete.
  9. You can optionally mark a cell as the end, but this is just a convenience for knowing when you can leave the dungeon. The maze is fully connected so the endpoint is arbitrary.
Depth-First Search with Backtracking
DFS will produce longer corridors since it continues to move forward until it is blocked. Here are the steps in the algorithm:
  1. Select a cell, mark it as in the maze, and put it on the path stack.
  2. Randomly select an unvisited neighbor of the current cell, connect it to the previous cell, and put the new cell on the path stack. Since we are always stepping forward to a different cell we are going to make longer paths. This is the "Depth-First" part of the algorithm.
  3. If the current cell has unvisited neighbors, goto 2. Otherwise, pop the top off the path stack, make the new top of the stack the current cell, and goto 2 (This is the "backtracking" part of the algorithm). Repeat until every cell has been visited.
  4. As with Prim's algorithm, you can choose an exit if desired, but this is arbitrary.
You can read more about these here and here.

Without further ado, here are mazes generated using these algorithms. There is a reset button below the second maze to recreate them if you want.

Maze generated using Prim's algorithm

Maze generated using Depth-First Search with Backtracking


The Source
Here is the complete implementation of the maze generators. Less than 50 lines! Despite being such a small namespace, it does a lot. Continue on past the code to see my comments and observations regarding this exercise.

Note that I did not include the source for rendering the mazes onto the HTML canvas. You can see that as well as a standalone Java Swing version of the code by checking out the complete project here.

(ns mazegen.rules)

(defn create-empty
  "Create an empty rectangular maze."
  [rows cols]
  (vec (take rows (repeat (vec (take cols (repeat #{})))))))

(defn neighbors
  "Compute the neighbors of a given coordinate."
  [maze [i j]]
  (->> (map vector
            ((juxt inc identity dec identity) i)
            ((juxt identity inc identity dec) j))
       (filter #(get-in maze %))))

(defn open-wall
  "Create pathways between the src and dst coords of the maze."
  [maze src dst]
  (-> maze
      (update-in src conj dst)
      (update-in dst conj src)))

(defn prim-gen
  "Create a maze using Prim's method."
  [empty-maze start end]
  (loop [maze (update-in empty-maze start conj :start)
         frontier (into #{} (neighbors maze start))]
    (if (empty? frontier)
      (update-in maze end conj :end)
      (let [dst (rand-nth (vec frontier))
            n (neighbors maze dst)
            { f true s false } (group-by #(empty? (get-in maze %)) n)]
        (recur (open-wall maze (rand-nth s) dst)
               (into (disj frontier dst) f))))))

(defn depth-first-gen
  "Create a maze using a depth-first recursive search with backtracking."
  [empty-maze start end]
  (loop [maze (update-in empty-maze start conj :start)
         visited [start]]
    (if (empty? visited)
      (update-in maze end conj :end)
      (let [n (neighbors maze (first visited))
            f (filter #(empty? (get-in maze %)) n)]
        (if (empty? f)
          (recur maze (rest visited))
          (let [dst (rand-nth (vec f))]
            (recur (open-wall maze (first visited) dst)
                   (conj visited dst))))))))

Comments, Observations, Lessons Learned
Here are some points that you might find interesting from this exercise:
  • The Data Model: In Java you would likely have a Maze class with Cells or some similar type hierarchy. In Clojure, you generally think about the data and model your domain in terms of simple data structures (vectors, maps, and sets). As the program grows, the data can flexibly grow with it. I modeled the maze as a 2D vector of sets. Each set represents a cell that contains links to other cells as well as any other data that I want to throw into it. In this case, I add :start and :end keywords to cells to represent entry and exit points. Had I used an object hierarchy, I would have to have made some decisions a priori regarding what can and can't go into a Cell. Would a cell have a start, be a start, or something else? Suppose I wanted to add a dragon at the exit that I had to fight to complete the maze. In Object Land, I now have to go back and redesign my type hierarchy to accommodate such a thing. In Clojure, I simply add a :dragon to the current cell set. If I decide I want something more hierarchical, I could easily change my sets in each cell to a map, or even add a map entry to the set (Maybe the dragon isn't just a keyword - Perhaps I also need to store its hit points or other attriubutes). Alternatively, I could have represented the maze as a map of [x y] coordinates as keys and another nested data structure as values.
  • The neighbors function has some awesomeness that needs some explaining. First, see that I am using the juxt function (as explained here and here) to determine my neighbor's coordinates. However, I may get coordinates like [-1 0] that are off the maze (the maze has minimum coords of [0 0] and maximum of [(dec dim) (dec dim)]). Rather than checking if the coordinate is in the grid or not, I attempt to access it using the get-in function. The great thing about get-in is that it allows you to safely drill down into nested data structures. If the element is missing or the path you are navigating is bad, it returns nil (You can also provide an optional default value). Contrast this to Java or Scala, where you must be very careful about navigating into nested data structures (e.g. maps of maps). One wrong get and you will get a NullPointerException. The filter method is called on the results of calling get-in over all of the coordinates in the maze. Filter will drop all of the nils that are returned, so anything off the maze goes away.
  • The neighbors and open-wall methods make use of threading macros (-> is thread first) and (->> is thread last). These deserve a post of their own, but the short explanation is that they take a value and feed it through a succession of functions. As each function is called, the result is passed to the next function. This allows you to create processing pipelines. The first vs. last distinction has to do with where the thing being threaded goes in the next function (first or last position). As I said, this is worthy of its own post and I won't go into a ton of detail here.
  • Finally, we don't goto in Clojure. Any self-respecting language would use recursion instead. Clojure has a pattern for recursion called loop-recur. Loop is the first line of the pattern and initializes a set of items to be iterated upon. This is typically followed by an if or other branching statement that has a stop condition and a recursion condition. If the stop condition is met, you return. If the recur condition is met, you update the items being iterated upon. In my examples, I used recur to track the maze, the active cell, the frontier, and similar items. One important point about loop-recur is that recur must be in the tail position of the calculation (the last thing being calculated before looping). By doing so, the construct is transformed under the covers so that the stack does not grow and you are just doing a simple loop.
There is more that can be gleaned from this short application, but I think this is good for now. It is easy to see, however, that Clojure is a very powerful and expressive language.

Conclusion
Mazes are an interesting problem that can demonstrate a lot of features of functional programming. In this case, the functional language of choice was Clojure. Clojure's powerful data modeling aspects combined with its expressiveness made it easy to create a flexible and concise solution to this problem.
If you liked this page or learned anything from it, please tweet the link and/or follow me on Twitter. Your support and interest is the fuel that drives the effort.