Travis Vachon - combinate.us

WeatherBill → Utah Street Labs

2011-05-20T00:00:00+00:00

Today will be my last day at WeatherBill. It’s said that it takes 10 years to become a good programmer and I dare say the last 2.5 have been well spent for me. I learned a couple entirely new domains - finance, agriculture - and worked with a great team building out an innovative, potentially world changing product. Weather related risk management is a huge, massively underserved market that affects literally everyone on the planet, and I’m proud to say I played a key role in discovering how to build products that meet the needs of farmers across the American Midwest. Discovery is a hard, painful process in software engineering, forcing hard decisions about how to design and build systems without a clear picture of the true business needs, especially in a domain as complex as ours. This, of course, makes the experience that much more valuable. I’m very excited about WeatherBill’s product and potential, and I wish my friends and coworkers nothing but the best.

I’ll be taking a week off, imposing on the hospitality of a very good friend off the coast of Woods Hole. I’d like to do a little fishing, a lot of reading and a huge amount of unwinding. I’ll also be signing off the internet and telephony from Sunday evening until Wednesday, a pleasure I honestly can’t remember ever indulging.

After Memorial Day I’ll be joining Utah Street Labs. We think the way people buy and sell from each other in a post-Facebook world should be much more pleasant and I’m very excited to spend the next couple years finding out if we’re right.

Hacking the Doomsday Machine

2011-03-20T00:00:00+00:00

En route to Montreal to visit some friends a few weeks ago, my wife and I cut the boredom of the northern New York highway system by alternating reading Michael Lewis’s The Big Short out loud. Eventually the light faded enough that reading became impractical, so I pulled out my laptop, inspired to return to a piece published by Simon Peyton Jones and Jean-Marc Eber in the 2003 functional programming book The Fun of Programming. Based on an earlier research paper by Peyton Jones et al, How to write a financial contract details a set of primitives for describing financial contracts. The authors build a simple model for determining the value of a contract over time and discuss the advantages of having a formal declarative model for financial contracts. It doesn’t take too much imagination to see the utility of this kind of standard representation for regulators and others attempting to understand the reality of the risks in the financial markets, and indeed, proposals for tools to enable this in real world exist.

The system proposed by the authors is straightforward, and can be cleanly captured in Clojure using protocols, types and plain old functions.

A Tight Core

The core of the library is small - only 10 primitives - and can be implemented in Clojure using a custom def form:

(defcontract zero []
  "A contract to give nothing and receive nothing.")
(defcontract one [currency]
  "A contract to receive one unit of currency.")
(defcontract give [contract]
  "A contract to give a counterparty a specific contract.")
(defcontract and [contract-a contract-b]
  "A contract to receive both contract-a and contract-b.")
(defcontract or [contract-a contract-b]
  "A contract representing a choice between receiving contract-a and receiving contract-b.")
(defcontract cond [condition contract-a contract-b]
  "A contract to receive either contract-a or contract-b according to a conditional (that is, boolean) index.")
(defcontract scale [index contract]
  "A contract to receive a contract scaled up by the value of an index.")
(defcontract when [index contract]
  "A contract to receive another contract at a particular time.")
(defcontract anytime [index contract]
  "A contract granting the option to receive another contract any time during a particular period.")
(defcontract until [index contract]
  "A contract granting the option to receive another contract until a particular time."

Each defcontract introduces a new type along with a helper function. The helper function isn’t strictly necessary, but makes it easier to use higher order functional programming facilities when creating new contracts and provides a place to hang a docstring. To implement defcontract we’ll first write an example of the code we’d like to generate and use that to create a simple template macro:

;; the code we'd like
(deftype Zero [])
(defn zero "A contract representing 0" [])

;; the macro to do it
(defmacro defcontract
  [name args & [comment]]
  (let [tname (symbol (s/capitalize (str name)))]
    `(do
       (deftype ~tname ~args)
       (defn ~name ~(str comment) ~args (new ~tname ~@args)))))

We can use these primitives to formalize our $20 birthday contract with our Grandmother:

(when (at (DateTime. 2011 7 5))
      (give (scale (const 20) (one :usd))))

In English, this contract says “on July 5, 2011, give a counterparty $20.” Once acquired, Gram can formally represent her obligation, and perhaps even write a computer program to automatically fulfill it.

An Interface With the World

Many of these contract primitives utilize Observables. An Observable is an “objective… possibly time varying” quantity whose true value may or may not be known at the time the contract is entered into. The Nasdaq, the value of the principal on a mortgage and the temperature outside our front door are all Observables, and it is easy to imagine writing contracts against each of them. We can define a simple protocol for Observables, declaring a values function which, given a time series, should return a seq of the value of the Observable corresponding to each point in the series:

(defprotocol Observable
  (values [observable time-series]))

Peyton Jones et al. describe a small number of primitive Observables, of which probably the most important is lift. lift is an Observable primitive which, given a function, will apply that function to each element of one or more other Observables. For example, to create an Observable representing the interest on 4.5% fixed rate loan we can apply the function

(fn [principal] (* 0.045 principal))

to each element of an Observable representing the principal of that loan over time. I can use lift for this:

(def interest-observable []
     (lift (fn [principal] (* 0.045 principal))) principal-observable)

Note that Observables generally don’t perform any computation on instantiation beyond what is required to set up a object in the JVM. Indeed, because an Observable usually represents a continuous function, we don’t have enough information to make it concrete until we know the granularity of the time series we will be evaluating it against. We can see this in the implementation of Lift:

(deftype Lift [f args]
  Observable
  (values [observable t] (apply map f (map #(values % t) args))))
(defn lift [f & args] (Lift. f args))

Upon instantiation, Lift just stores a function and some arguments which are themselves Observables. When a client passes a time series along in the call to values we can get the values of the underlying Observables and then apply the stored function to each set of values provided by the Observables to yield a single seq of values. For example, we can lift the + operation to Observables:

(defn + [& args] (apply lift clojure.core/+ args))

and use it to add together two constant value Observables:

> (values (+ (const 5) (const 6)) [1 2 3 4 5])
(11 11 11 11 11)

Observables can be arbitrarily complex under the surface, and can participate in this system by exposing their values via the Observable protocol. Because we use a protocol for this, any Java object can be extended to participate in this system. As with Clojure seqs themselves, it is good practice to formulate relatively simple underlying Observables and combine them using regular Clojure functions lifted to act on Observables.

A Valuation Model

Now that we can represent contracts and the real world data underlying them we can formulate a model for determining the expected value of a particular contract. What we would really like is a sequence of values representing the expected value of a contract over time. For example, our $20 dollar birthday contract with Gram might have an expected value of less than $20 in January due to concerns about her ability to pay up in July - she might forget, or need the $20 for gas.

This actually sounds a lot like what we already know how to do with Observables, and indeed, once we have determined the expected value of a contract we can use that expectation as an Observable to formulate new contracts. It makes sense, then, to implement our valuation model by extending Observable to our primitive contract types. Of our 10 types, the values functions for 6 are straightforward applications of standard Clojure constructs to our primitive types:

(extend-protocol Observable
  Zero
  (values [_ _] (repeat 0))
  Give
  (values [contract t] (map #(* -1 %) (o/values (.contract contract) t)))
  And
  (values [contract t] (map (fn [a b] (+ a b))
                               (o/values (.contract-a contract) t)
                               (o/values (.contract-b contract) t)))
  Or
  (values [contract t] (map (fn [a b] (max a b))
                               (o/values (.contract-a contract) t)
                               (o/values (.contract-b contract) t)))
  Cond
  (values [contract t] (map (fn [c a b] (if c a b))
                               (o/values (.condition contract) t)
                               (o/values (.contract-a contract) t)
                               (o/values (.contract-b contract) t)))
  Scale
  (values [contract t] (map (fn [o c] (* o c))
                               (o/values (.observable contract) t)
                               (o/values (.contract contract) t))))

Each of the other primitives in our model requires some additional work. The authors describe four functions (plus a constant) that capture the semantics of the remaining contract primitives:

(def *currency*)

(defn *exch*
  "Given a time series and a currency, return a seq of the exchange
rate from currency to the model currency (*currency*) at each point
in the time series"
  [currency time-series])

(defn *discount*
  "Given a seq of observable values and a seq of contract values over
time, return a seq of the 'fair' contract values over time. This usually
means adjusting contract values down to account for uncertainty about the
observables underlying the contract values."
  [observable-values contract-values])

(defn *snell*
  "Given a seq of observable values and a seq of contract values over
time, calculate the 'Snell envelope' of the contract values under the
observable values. At a high level, the returned seq should reflect the
adjustments to the contract values given that they may be realized
any time the observable values are true."
  [observable-values contract-values])

(defn *absorb*
  "Given a seq of observable values and a seq of contract values over time,
return a seq of the 'fair' contract values given that the contract values
given that they may be realized until the first true value in the observable."
  [observable-values contract-values])

(extend-protocol Observable
  One
  (values [contract t] (*exch* (.currency contract) t))
  When
  (values [contract t] (*discount*
                        (o/values (.observable contract) t)
                        (o/values (.contract contract) t)))
  Anytime
  (values [contract t] (*snell*
                           (o/values (.observable contract) t)
                           (o/values (.contract contract) t)))
  Until
  (values [contract t] (*absorb*
                           (o/values (.observable contract) t)
                           (o/values (.contract contract) t))))

This is the most complex and difficult to understand part of the paper, and a full explanation of these functions is beyond the scope of this piece - the authors themselves do not attempt a detailed exploration of them, but simply present them along with some material to give the reader an intuitive understanding of their semantics. With this complexity comes great power - by simply redefining these 4 functions, we can fundamentally change how we model our risk. To lay down a baseline we can make some simple assumptions that provide reasonable, easy to understand implementations of these functions. Our assumptions are:

the exchange rate between any two currencies is 1:1
we have perfect information about the observables underlying a contract and therefore have no reason to discount contracts that rely on future events
we will not be using anytime and until

This means that:

*exch will return a constant seq of 1
*discount* will return a seq that returns a constant value up until the first true value in the Observable, and then 0. The constant value will be the value of the Contract when the Observable is first true
we can skip the implementation of *absorb* and *snell*

This makes our implementation of the model relatively simple:

(defn use-default-model
  []
  (def *currency* :usd)

  (defn *exch*
    [currency time-series]
    (map (constantly 1) time-series))

  (defn *discount*
    [observable-values contract-values]
    (let [[_ value]
          ;; find the value of the contract the first time the
          ;; observable is true
          (some (fn [[obs _ :as pair]] (if obs pair nil))
                (map vector observable-values contract-values))]
      ;; return a seq that is constantly value until the first time
      ;; the observable is true, and then is constantly 0
      (map (fn [h] (if h (or value 0) 0))
           (drop-last
            (reductions (fn [h [obs _]] (and h (not obs)))
                        true
                        (map vector observable-values contract-values))))))

  (defn *snell*
    [observable-values contract-values])

  (defn *absorb*
    [observable-values contract-values]))

These assumptions are clearly far too simple for production use, but they provide a base on which to build. More information on models and implementations for each can be found in the paper, and Armin Straub has some basic material on the Snell envelope. For a deeper understanding of all these concepts, you’ll need to find your local financial engineer and buy him a few drinks.

A Simple Bond

To get a better intuition for this library we’ll work through the implementation of a very simple bond structure. A financial bond is “a formal contract to repay borrowed money with interest at fixed intervals.”. We will model a $100 bond with a 4 part repayment schedule. There are 6 interesting points in time for the principal of this bond - the initial value, the value at each of the payment dates, and the final value. We model this as a map and turn it into an Observable by defining a new Observable primitive called schedule:

(defobservable schedule
  [sched]
  (values [_ t] (map sched t)))

(def principal (schedule
                {0 total
                 1 total
                 2 (- total principal-payment)
                 3 (- total (* principal-payment 2))
                 4 (- total (* principal-payment 3))
                 5 (- total (* principal-payment 4))}))

Note that this Observable will only work with fairly restrictive notion of time - time must be modeled as a series of integers from 0 to 5. It would be fairly straightforward to write a function that would support more sophisticated notions of time, and we leave this as an exercise to the reader.

From this Observable we can build a library of more complex Observables and Contracts using the primitives we have already defined. In the following code we assume that the observable namespace has been aliased to o and the contract namespace has been aliased to c:

;; an observable of the interest payments on our bond
(def interest-payments (o/* (o/const 0.015) principal))

;; an observable of the payments on our bond
(def payments (o/+ interest-payments principal-payments))

;; a contract for the interest payment at a specific time
(defn interest-payment-at
  [time]
  (c/when (o/at time) (c/scale payments (c/one :usd))))

We can use this library to build our bond structure:

(def four-payment-bond
     (c/and (c/when (o/at 0) (c/scale (o/const 100) (c/one :usd)))
            (c/give (c/and (interest-payment-at 1)
                           (c/and (interest-payment-at 2)
                                  (c/and (interest-payment-at 3)
                                         (interest-payment-at 4)))))))

Now for the moment of truth. We’ll use values to get the value of this contract at each point in our primitive timeline:

covenant.bond> (v/use-default-model)
#'covenant.valuation/*absorb*
covenant.bond> (o/values four-payment-bond [0 1 2 3 4 5])
(-3.75 -103.75 -77.25 -51.125 -25.375 0)

This looks right: at first, the expected value of this contract is the $100 we’ll receive minus the four payments we’ll make and interest. Interest comes out to $3.75, so we expect to lose that much over the lifetime of the contract. At time 1, the $100 has already been paid - if we were to acquire the contract at this point we’d take on all of the interest payments, but none of the original payment. As interest payments are made, the expected loss from this contract goes to 0. We can model the other side of this transaction using give:

covenant.bond> (o/values (c/give four-payment-bond) [0 1 2 3 4 5])
(3.75 103.75 77.25 51.125 25.375 0)

A Call for Participation

The source for this library can be found on GitHub, alongside Marginalia generated documentation. While the basics have been laid down, it needs additional work and expertise to be useful in a real world context. This work falls into a couple categories:

Models

More sophisticated and complete models are needed to enable non-trivial usage of this library. Implementations of *absorb* and *snell* would be great, especially from statistically minded financial engineers.

Examples

The simple bond presented above is useful as a proof of concept, but more examples would help elucidate the power of this model. There are thousands of different financial instruments in the world, and it would be fun and interesting to start collecting a menagerie in a central location.

The goal of this project is not to solve the problem of an impenetrably complex financial system - indeed, being able to formally represent contracts could easily make the problem worse, taking this complexity into entirely new realms. It is, however, built on the belief that formal models are useful, and can serve as the foundation for higher level tools to provide better insight into a complicated system. It is clear that the mavens at the heart of our financial system will continue dreaming up complicated financial instruments, and it is imperative that the rest of us have the tools to separate the wheat from the chaff. Patches welcome!

Advice to a Novice Programmer

2011-02-21T00:00:00+00:00

A friend from Ithaca asked for advice on getting started with programming. Specifically, he asked how I started and whether I’d recommend Java classes. Fortunately for him, this is a subject I can bloviate on for quite a while, and my response ended up being fairly long, at which point I realized it might hold the potential for some greater social value than it could achieve as part of a one to one conversation. With that in mind, I’ve done some some minor editing and reproduced my message below.

My story is that I started with an “intro to computer science” class in the spring of my sophomore year at Williams, and was able to use that experience to snag a Google Summer of Code internship. The class was taught using Java, which IMHO only worked because it was a normal 10-15 hour/week class. I picked up Python on my own that summer and used it exclusively for the internship. I learned Python mainly from Python in a Nutshell, a path I think is absolutely perfect if a) you have the basics under your belt and b) you have a reasonably well defined project you’d like to hack on for a couple months. I think it’s important to note, however, that without these two things, picking up Python from PiaN would be pretty brutal - it’s really more of a reference book with a technical but well written language overview at the front.

The demand for programming skills right now is through the roof, and the vibrancy of open source software (spend some time browsing GitHub) means that even if I wasn’t employed I could keep busy for the rest of my life behind a keyboard. One of the most valuable qualities a programmer can have is a deep familiarity with a particular non-programming domain coupled with solid baseline programming skills. Someone who can successfully apply “computational thinking” to a domain with a shortage of it can do pretty well.

Interestingly, I know a lot of people in the industry who don’t have a formal background in computer science. I think it’s probably easiest to get baseline programming skills ramped up by going through a mix of formal classes and personal, unguided exploration, and I think that trying to learn this stuff with just one or the other is probably much less likely to be successful.

My wife is actually starting down this same path - looking to augment her domain specific knowledge with some baseline programming skills - and I got her a book called Hello World!. It’s designed for “Kids and Other Beginners” and is literally designed to be consumable by 12 year olds, but she has really loved its willingness and ability to explain basic concepts in clear, easy to understand language.

I would definitely recommend programming classes. If you can find something taught in Python I’d recommend it, but Java is the lingua franca these days and is not a bad alternative. Regardless of which “formal education” path you choose, I would strongly recommend picking up a side project that you think might be fun and engaging. You could try searching GitHub for a fun open source project and try to modify it to do something different, or even just work through a book like “Hello World” and find inspiration there. Here’s a neat thread of ideas:

http://www.daniweb.com/forums/thread32007.html

Whichever path you choose make sure you’re having fun!

Arduino and Clojure

2010-12-27T00:00:00+00:00

Arduino is the coolest toy I’ve gotten for Christmas in a while. After working through the Make introductory guide I was excited to get it hooked up to a swank-clojure emacs buffer, and fortunately the hard work has already been done. Cloduino takes care of the heavy lifting of talking to an Arduino board running Firmata, which means I can eval Clojure in an emacs buffer and see the board react instantly. It took a little more digging than the Cloduino page suggests to get things set up properly, but with that done it works like a charm. The tricky bits here are figuring out where to put various things, so some of the setup instructions are specific to Snow Leopard, specifically OS X 10.6.5.

Setup

First, download the Arduino IDE and drag it into your Applications folder. I still use the IDE for verifying and uploading Processing scripts to the Arduino board and I’d strongly recommend working through some basic examples if this is your first foray into Arduino. Once you’re ready to start playing with the board over the serial port, open up the IDE and load the appropriate Firmata sketch from File > Examples. I used StandardFirmata_2_2_forUNO_0_3 because I have an Uno board, but YMMV. Whichever sketch you choose, make sure you have the right serial port selected from Tools > Serial Port and upload it to the board.

Next you’ll need to copy some dependencies from the IDE to your Java extensions directory. On Snow Leopard this is /Library/Java/Extensions, so this should look like:

cp /Applications/Arduino.app/Contents/Resources/Java/{RXTXcomm.jar,librxtxSerial.jnilib} \
   /Library/Java/Extensions/

Now comes the fun part: head to wherever you like to develop code and create a new project with lein:

lein new arduino-sandbox

Now open up arduino-sandbox/project.clj in your favorite editor and add cloduino, org.clojars.nakkaya/rxtx-macosx-native-deps, and native-deps. Your dependencies section should look something like:

  :dependencies [[org.clojure/clojure "1.2.0"]
                 [org.clojure/clojure-contrib "1.2.0"]
                 [clodiuno "0.0.2-SNAPSHOT"]]
  :native-dependencies [[org.clojars.nakkaya/rxtx-macosx-native-deps "2.1.7"]]
  :dev-dependencies [[native-deps "1.0.5"]]

You’ll also need to add :jvm-opts ["-d32"] to your defproject to ensure the JVM uses a 32 bit data model - this is required for compatibility with the native dependencies. Your project.clj should now look like:

(defproject arduino-sandbox "1.0.0-SNAPSHOT"
  :description "FIXME: write"
  :dependencies [[org.clojure/clojure "1.2.0"]
                 [org.clojure/clojure-contrib "1.2.0"]
                 [clodiuno "0.0.2-SNAPSHOT"]]
  :native-dependencies [[org.clojars.nakkaya/rxtx-macosx-native-deps "2.1.7"]]
  :dev-dependencies [[native-deps "1.0.5"]]
  :jvm-opts ["-d32"])

Finally, head back to the command line, cd into your project and run lein deps.

Blink

To make sure everything is working, fire up a repl with lein repl. Pull cloduino into the repl namespace with

(use 'clodiuno.core 'clodiuno.firmata)

and initialize the board, assigning it to a var named board:

(def board (arduino :firmata "/dev/tty.usbmodem621"))

You may need to change "/dev/tty.usbmodem621" to match the serial port Arduino uses on your system - it should have a similar name to the one you chose in the IDE. The board will take a few seconds to initialize, but once it returns it should be ready for interaction.

The easiest way to interact with the board at this point is to control the builtin LED, which is tied to pin 13. To turn it on and off, first put the pin into OUTPUT mode:

(pin-mode board 13 OUTPUT)

You can now turn it on by writing HIGH to the pin:

(digital-write board 13 HIGH)

You can turn it off by writing LOW to the pin:

(digital-write board 13 LOW)

Analog

Of course, to do anything interesting you’ll need to do a bit of hands on wiring. I built a sensor circuit attached to analog pin 0 (a light sensor works great) and an LED circuit attached to pin 9, both of which are described in the Make guide.

To set these pins up for this configuration, enter the following at the REPL:

(pin-mode board 9 PWM)
(enable-pin board :analog 0)

To turn the LED on at a particular brightness, use analog-write:

(analog-write board 9 250)

Try a variety of values between 0 and 255 to see it change.

To get a reading from the sensor, use analog-read:

(analog-read board 0)

This means we can read from a physical input and write to a physical output using Clojure. Let’s put these together in a tantalizing hint at what we might be able to do with these capabilities:

(defn map-int [x in-min in-max out-min out-max]
  (int (+ (/ (* (- x in-min) (- out-max out-min)) (- in-max in-min)) out-min)))

(while true
  (analog-write board 9 (map-int (analog-read board 0) 0 1023 0 50)))

If everything is working properly, this should give you an LED that reacts to the value of the sensor. Of course, you could do the same thing using pure Processing running on the Arduino board, so I recommend you start playing with something a bit more complex. Have fun tinkering!

resrc part 2: solidifying the abstraction

2010-10-19T00:00:00+00:00

In our last installment, we laid out a core abstraction for RESTful resources. We also implemented a basic routing function to map identifiers to resources, and a content negotiation function that mapped a list of acceptable content types to particular representation of a resource. The result was a functional resource processing function, but lacked the ease of use and DRYness that a Clojure programmer can expect from a well written library. In this installment we look at ways to fix that. We’ll also harvest some low hanging performance optimization fruit and begin to specialize our abstraction to take advantage of the power of Ring.

Better

We’ll start once again with resources. We’d like to be able to succinctly define a resource and associated representations. We first write down an example of how we’d like this to work:

(deftest test-resource
  (let [resource (resource
                  (get "fuz ")
                  (put +request)
                  [:text/html (str +response "representation")])]
    (is (= "fuz representation"
           (process-request ["/bar" resource] get "/bar" [[:text :html]] "foo ")))
    (is (= "foo representation"
           (process-request ["/bar" resource] put "/bar" [[:text :html]] "foo ")))))

Let’s unpack that. The resource function we’d like to define will need to take a set of method handlers and a list of representations. Because the signature for our method handlers will be repetitive and its parameters often discarded, we’d like to be able to leave it out and give these handlers access to the parameters via special symbols prefixed with +. We’d like to be able to specify representations using a succinct content type syntax and use the same “magic variable” technique for making the response available in the representation function.

Clojure’s macros are just the tool for the job, but a macro like this needs to be carefully executed, as it looks like it could be fairly complicated. At a high level, we’d like to transform code like

(resource
 (get "fuz ")
 (put +request)
 [:text/html (str +response "representation")])

to code like

(with-representations
 (reify Resource
        (get [+resource +request] "fuz ")
        (put [+resource +request] +request))
 [[[:text :html] (fn [+resource +response]
                   (str +response "representation"))]])

Is this really all that complex? Looking closer, it appears that aside from some syntax massaging around the protocol method implementations and representation function, this is actually a fairly standard substitution macro. With that in mind, we’ll tackle the syntax helpers in isolation by writing a couple functions that operate on quoted Clojure forms:

(defn emit-resource-handler
  [[method & forms]]
  `(~method [~'+resource  ~'+request]
            ~@forms))

(defn split-type
  [type]
  [(keyword (namespace type)) (keyword (name type))])

(defn emit-representations
  [representations]
  (apply vector
         (map (fn [[type representation]] [(split-type type)
                                          `(fn [~'+resource ~'+response] ~representation)])
         (partition 2 representations))))

Both of these functions utilize a technique for avoiding Clojure’s symbol capture safety mechanisms. Symbol capture like the kind we use in this macro is usually a subtle bug in macro code. In this case, however, we force symbol capture by unquoting and requoting a symbol like ~'+request. Whoever writes the form that will be passed in to emit-representations will now be able to use +resource and +response without explicitly defining them.

With these functions written, our macro is now straightforward:

(defmacro resource
  [& args]
  (let [[representations & specs] (reverse args)]
    `(with-representations (reify Resource ~@(map emit-resource-handler specs))
       ~(emit-representations representations))))

We can use it to succinctly define a new resource:

(def r (resource
 (get "fuz ")
 (put +request)
 [:text/html (str +response "representation")]))

user> (let [[[_ rep]] (representations r)] (rep r (get r "foo ")))
"fuz representation"

user> (let [[[_ rep]] (representations r)] (rep r (put r "foo ")))
"foo representation"

Faster

The routing method we wrote last time took set of routes and a path as input and returned a tuple representing the matched resource and any parameters extracted from the path:

resrc.core> (find-resource ["/foo/:id" :bar] "/foo/10")
[:bar {"id" "10"}]

Formulated this way, find-resource must process the raw list of routes and resources every time it is invoked, even though the list may not have changed since the last invocation. It also forces consumers to have access to both the list of routes and the path of the request, and it would be nice to only require them to think about the request itself.

We can fix both of these problems by splitting the computation into two pieces. We’ll define a new function compile-routes that will return a function of one argument, the request path. This returned function will be responsible for mapping a path to the resource-params tuple we are familiar with. Since we’re doing performance optimization, lets get some baseline performance numbers so we can get a sense of what we’re gaining:

(dotimes [_ 5] (time (find-resource bunch-of-routes "/bar/10")))
"Elapsed time: 1.774 msecs"
"Elapsed time: 1.694 msecs"
"Elapsed time: 1.461 msecs"
"Elapsed time: 2.743 msecs"
"Elapsed time: 1.588 msecs"

We’ll start by thinking about what it means to compile a single route. We’d like to turn a route into a function that takes a path and returns either a resource-params tuple or nil:

(defn compile-route
  [[path-spec resource]]
  (fn [path] (when-let [params (clout/route-matches path-spec path)]
              [resource params])))

Next, we can use this function to pre-compile our routes into a list of functions. Matching a path at runtime will now be a matter of evaluating functions until we find a match:

(defn compile-routes
  [routes]
  (let [compiled-routes (map compile-route (partition 2 routes))]
    (fn [path] (some #(% path) compiled-routes))))

Let’s take a look at what we’ve gained:

(def compiled-routes (compile-routes bunch-of-routes))
(dotimes [_ 5] (time (compiled-routes "/bar/10")))
"Elapsed time: 1.712 msecs"
"Elapsed time: 1.38 msecs"
"Elapsed time: 1.504 msecs"
"Elapsed time: 1.662 msecs"
"Elapsed time: 1.193 msecs"

This is an improvement, but it’s not as dramatic as we might like. One optimization we didn’t include was to use Clout to pre-compile path specifications into a format it is able to use more efficiently. We’ve created a perfect place for this in compile-route:

(defn compile-route
  [[path-spec resource]]
  (let [compiled-path-spec (clout/route-compile path-spec)]
    (fn [path] (when-let [params (clout/route-matches compiled-path-spec path)]
                [resource params]))))

Let’s run our benchmarks again:

(def compiled-routes (compile-routes bunch-of-routes))
(dotimes [_ 5] (time (compiled-routes "/bar/10")))
"Elapsed time: 0.219 msecs"
"Elapsed time: 0.102 msecs"
"Elapsed time: 0.091 msecs"
"Elapsed time: 0.095 msecs"
"Elapsed time: 0.128 msecs"

That’s more like it! We’ve gotten a solid performance boost by extracting repeated computation out using higher order functions.

Stronger

Now that we’ve explored two improvements to the core library, let’s take a look at extending our abstraction to play nicely with Ring.

Specializing our abstraction for Ring means that we can make a couple assumptions that were previously off limits:

requests and responses will be Clojure maps
these maps will have certain keys and values as specifed in the Ring spec

First, we’ll take advantage of this new information to write a cleaner version of the process-request method we defined earlier. As usual, we’ll write down how we’d like it to work:

(deftest test-process-request
  (let [resource
        (c/resource
         (c/get "foo ")
         [:text/plain (str +response "bar")])]
   (is (= "foo bar"
          (:body (process-request ["/bar" resource]
                                  {:method :get
                                   :uri "/bar"
                                   :headers {"Accept" "text/plain"}}))))))

This looks a lot like our previous process-request, with most of the arguments to the original embedded within the Ring request. We can’t quite use the original because it threw away path and response content type information, which we’d now like to include in the request and response:

(defn process-request
  "method should be a method supported by Resource.

Assumes representations are functions from [resource request & rest] to response."
  [routes request]
  (let [path (:uri request)
        [resource path-params] (core/find-resource routes path)
        method (ns-resolve 'resrc.core (symbol (name (:method request))))
        accepts-list (parse-accept ((:headers request) "Accept"))]
    (if-let [[response-type representation]
             (core/find-acceptable accepts-list (core/representations resource))]
      (add-content-type
       (representation
        resource
        (method resource (assoc request :path-params path-params)))
       response-type)
      {:status 405 :headers {}})))

This function depends on a new function parse-accept. We’ll write an example of how this should work:

(deftest test-parse-accept
  (is (= (seq [[:text :plain] [:text :html]])
         (parse-accept "text/plain, text/html")))
  ;; should sort by 'q' param
  (is (= (seq [[:text :plain] [:text :html]])
         (parse-accept "text/html;q=0.5, text/plain;q=0.8")))
  ;; q defaults to 1
  (is (= (seq [[:text :plain] [:text :html]])
         (parse-accept "text/html;q=0.5, text/plain"))))

And finally, implement it:

(defn parse-accept
  "accepts-string is a string like
text/*, text/html, text/html;level=1, */*"
  [accept-string]
  (sort-by-q-value
   (map #(parse-accept-component (s/trim %))
        (s/split accept-string #","))))

We’ll leave out the implementation of parse-accept-component and sort-by-q-value for now, but as usual they’ll be available in the linked source.

There is one other improvement we can make to our library to make it easier to work with Ring. In our original resource macro, only +resource and +request were made available to method handlers. This means that in practice, defining Ring resources would involve a lot of code like:

(resource
 (get (let [{body :body headers :headers} +request] (str headers body))))

The let, used to destructure the Ring request, is boilerplate that obscures the actual meat of the handler. We can get rid of it by extending our implicit wrapping let to include all keys defined in the Ring specification:

 (defn emit-resource-handler
   [[method & forms]]
   `(~method [~'+resource {~'+server-port :server-port
                           ~'+server-name :server-name
                           ~'+remote-addr :remote-addr
                           ~'+uri :uri
                           ~'+query-string :query-string
                           ~'+scheme :scheme
                           ~'+request-method :request-method
                           ~'+content-type :content-type
                           ~'+content-length :content-length
                           ~'+character-encoding :character-encoding
                           ~'+headers :headers
                           ~'+body :body
                           :as ~'+request}]
             ~@forms))

Which gets the following test running:

(deftest test-resource
  (let [resource (resource
                  (get +body)
                  [:text/html  {:body (str +response "representation")}])]
    (is (= "foo representation"
           (:body (process-request ["/bar" resource]
                                   {:method :get
                                    :uri "/bar"
                                    :headers {"Accept" "text/html"}
                                    :body "foo "}))))))

Next: Something Useful

We’ve developed a general purpose library for defining resources and making requests against them. Next time we’ll refine this into something closer to a full fledged web development framework. We’ll see how the underlying Resource abstraction can be used to build a system that will feel familiar to modern web developers and is well suited to building powerful RESTful services.

(the code described in this post is available on GitHub)

resrc part 1: bootstrapping an abstraction

2010-10-17T00:00:00+00:00

Ring, Clojure’s answer to WSGI and Rack, is a wonderfully simple implementation of the HTTP request/response and intermediary abstractions. This simplicity facilitates integration with components that interact with the networking stack and provides a solid base on which to build web focused abstractions, but by itself falls short of the capturing the full REST architectural style of the web. To ease development of applications that take advantage of the web ecosystem, it would be useful to have an abstraction that captures REST in a first class way. Let’s take a look at how that might be implemented in Clojure.

Resource

Resources are the building block of the web, so it makes sense to tackle them first. A resource is ”any information that can be named,” and is accessed according to a uniform interface of 4-6 different methods. We’ll start by writing down the core of this interface, get, put, post and delete:

(defprotocol Resource
  (get [resource request])
  (put [resource request])
  (delete [resource request])
  (post [resource request]))

As with all protocols, the first argument is the object itself. The second argument, request, will probably be a Ring HTTP request map. Note, however, that this protocol doesn’t specify that explicitly, and as a result may also be used to represent non-HTTP resources in any other system implemented in a RESTful style.

Before we get too much further we should document this abstraction with examples of its use. We’ll use clojure.test to provide these examples in a way that can double as regression testing:

(deftest test-Resource
  (let [r (reify Resource
                 (get [res req] "fun"))]
    (is (= "fun" (get r nil)))))

Identifier

REST associates resources with resource identifiers. On the web these take the form of URIs. We’d like to define a function that maps the path portion of a URI to a resource, so we’ll first write some examples of how we’d like it to work:

(deftest test-find-resource
  (let [routes ["/foo" 1
                "/foo/:id" 2]]
    (is (= [1 {}] (find-resource routes "/foo"))
        (= [2 {"id" "bar"}] (find-resource routes "/foo/bar"))
        (= nil (find-resource routes "/bar")))))

Given a path and vector of alternating path specifications and resources, we’d like to iterate through the path specifications, at each iteration comparing the path against a specification. Once we find a match, we return a tuple containing the resource and a map of the parameters extracted from the path. If no matching specification is found we return nil. The implementation of this is relatively simple using partition and some:

(defn find-resource
  [routes path]
  (some (fn [[path-spec resource]]
          (when-let [params (route-matches path-spec path)]
            [resource params]))
        (partition 2 routes)))

Representation

A resource is an abstract concept that doesn’t bind to any particular representation at definition time. Instead, consumers of a resource should be able to provide a list of representations they are able to handle at the time they perform a request against that resource. A given resource may have many representations, and should return the representation deemed “most preferable” by the client. So given two datastructures like:

(let [representations [[[:text :plain] resource-1]
                       [[:text :html] resource-2]
                       [[:image :jpeg] resource-3]]
      accepts-list [[:text :html] [:* :*]]])

We should be able to use accepts-list to pick a representation. We’ll write down some examples of how we’d like this function to work:

(deftest test-find-acceptable
    (let [representations [[[:text :plain] 1]
                           [[:text :html] 2]
                           [[:image :jpeg] 3]]]

      (is (= [[:text :plain] 1] (find-acceptable [[:* :*]] representations)))
      (is (= [[:text :plain] 1] (find-acceptable [[:text :plain]] representations)))
      (is (= [[:text :html] 2] (find-acceptable [[:text :html] [:* :*]] representations)))
      (is (= [[:image :jpeg] 3] (find-acceptable [[:image :jpeg] [:* :*]] representations)))))

And finally write the function definition down:

(defn find-acceptable
  [accepts-list representations]
  (some (fn [type] (find-representation type representations))
        accepts-list))

We’ll leave out the details of find-representation now, but they are available in the resrc source.

Representation information, being metadata on a particular “resource”, will likely be associated with values as Clojure metadata. To encourage uniformity in metadata naming, we’ll define a couple wrappers over the Clojure metadata functions to make this simple:

(def *representations-key* :resrc-representations)

(defn with-representations
  [obj representations]
  (with-meta obj (assoc (meta obj) *representations-key* representations)))

(defn representations
  [obj]
  (*representations-key* (meta obj)))

Processing Requests

All that remains is to assemble the pieces into a system:

(deftest test-process-request
  (let [resource
        (with-representations
          (reify Resource (get [_ request] (str request "bar ")))
          [[[:text :plain] (fn [resource response] (str response "baz"))]])]
   (is (= "foo bar baz"
          (process-request ["/bar" resource] get "/bar" [[:text :plain]] "foo ")))))

(defn process-request
  [routes method path accepts-list request]
  (let [[resource _] (find-resource routes path)]
    (if-let [[_ representation]
             (find-acceptable accepts-list (representations resource))]
      (representation resource (method resource request))
      :not-acceptable)))

This is a fairly generic implementation, which throws away path parameter and accepted content type information, so probably isn’t very useful for real world applications. We’ll address this later, as we specialize on Ring based applications.

Next: Sweetness and Light

Writing out the simplest code possible to capture this abstraction was definitely a good exercise, but it left us with an API that isn’t very fun to use and does more work at request time than it really needs to. In our next installment we’ll layer on some sugar to make it easier to use these abstractions. We’ll also suck out some of the fat in the request processing path, and add some new functions specifically for working with Ring.

Clojure++

2010-09-27T00:00:00+00:00

I was lucky enough to be able to make it to San Francisco last week, not for you know what (who has two grand?), but to see coworkers and friends. It sure didn’t hurt that JavaOne brought a lot of talent into the area, and I took advantage of that by attending Rich Hickey’s talk at the special edition of the Bay Area Clojure User Group meetup. As Sean Corfield notes in the meetup feedback, the talk was both “entertaining and thought provoking,” which I think is about all you can ask of a talk about language internals.

The big takeaway, I’d say, is that Rich is interested in making Clojure a language that runs code like the stuff we write run really damn fast. At the moment, he’s working on static linking and enhanced primitive support, which looks like this:

(defn fib [n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 3565.579 msecs"

;; hint arg and return
(defn ^:static fib ^long [^long n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 395.365 msecs"

That’s right: add a few annotations to the method signature, and get 9x performance. Thanks to Clojure’s autoboxing and promotion of ints to longs, this works for just about any values you’d want to use here.

There is one exception, and it was an important part of what Rich had to say last Monday: this function, and most numeric functions in Clojure, will no longer auto-promote values to Big numbers to avoid overflowing longs and doubles. This is already somewhat controversial, and will no doubt remain so, but Rich did a good job of explaining its necessity as a workaround for the JVM’s inability to handle values that might be objects or primitives. Inconveniencing legitimate consumers of arbitrary precision math (you know who you are!) to make everyone else happier is a tradeoff that makes sense to me.

The vision behind this work is the enablement of functional patterns with bare metal performance - mapping a statically linked function over an array of primitives should be no slower than a corresponding imperative loop. Performance of idiomatic code will be a feature of Clojure, which is pretty uncommon.

Rich’s presentation and the gaggle of smart people asking questions yielded many other gems throughout the night. Clojure seems to be on course for a solid amount of additional development. Parallelism will be improved via fork/join and some cleanup of binding semantics. Pods - more on these after Clojure Conj - will help bring side-effect laden Java code into the fold in a clean way. Clojure’s Java underpinnings will eventually move to Clojure, and provide a much more solid foundation for tooling along with them. These changes will largely be “additions” to the language or entirely transparent, unlike some of the important changes to semantics slated for the near future.

This, I think, is probably going to be the story of Clojure - the language - from here on out. Don’t expect an actor model or an object system from the core implementation (add them if you really want them!). Do expect a healthy community of interesting, performant libraries and a language that will continue to take whatever steps are necessary to replace Java in your day to day life: this is the clear goal of its creator.

Bundler

2010-09-25T00:00:00+00:00

Being a warning about an excellent dependency management tool:

The release of Rails 3 ushered in a new era of gem management for Rails developers in the form of Bundler. This is a very good thing, since a) the previous state of affairs was pretty painful and b) Bundler is a shining example of the kind of great tooling the Ruby community does so well. It’s not just good for Rails 3 developers either: Gemfiles can suck in dependencies from .gemspecs, and Bundler can easily be used with legacy Rails.

Of course there are warts, and while Bundler’s are pretty minor, that didn’t stop them from eating half my week. One of Bundler’s neat features is the ability to specify a git repository for a particular gem. Instead of looking in gem repositories for the gem, bundle install will check the repository out, look for a .gemspec, and put the code in the right place. This is a nice way to track private gems that change frequently without the overhead of picking version numbers and shipping releases. As of Bundler 1.0, however, there’s no way to use bundler package to pack a gem specified this way into a local package cache. This means that when you run bundle install on your production machine it has to be able to talk to the development git repository - at best, inconvenient, and at worst, entirely infeasible. The solution for us, for now, was to include our dependency as a vendored, submoduled plugin, and just include third party dependencies in our Gemfile. This forces us to include all of the plugin’s dependencies in the top level Gemfile, and isn’t at all ideal, but it does the job for now.

The takeaway is that if the workflow you are planning to implement using bundler needs to use bundle package and :git sources together, you’re out of luck for now. Happily, this wart is slated for removal in version 1.1, here’s hoping it ships early!

π in Clojure

2010-02-09T00:00:00+00:00

After reading Carl Sagan’s Contact I’m crushing on π, so I looked it up on Wikipedia, where, of course, several algorithms for computing it are described in detail. One of them, the Brent-Salamin algorithm, has the really neat property of doubling the number of digits it gets right on each iteration.

The algorithm starts with four terms (images ripped from Wikipedia):

And then iterates on them like:

Whenever you get tired of iterating, you can just plug the latest versions of the terms into:

In Clojure, we’ll start by defining a function to do the heavy lifting:

(defn brent-salamin-term
  "compute terms of the the Brent-Salamin algorithm"
    [])

We’ll want two versions of this function, one that will be called with no arguments, to get the initial values of the parameters:

  ([] [1 (/ 1 (sqrt 2)) (/ 1 4) 1])

And a second which will implement a single iteration of the algorithm:

  ([a b t p]
     (let [A (/ (+ a b) 2)
           B (sqrt (* a b))
           T (- t (* p (sqr (- a A))))
           P (* 2 p)]
       [A B T P])))

Finally, we’ll define a short function to calculate π given Brent-Salamin terms:

(defn brent-salamin-pi
  [a b t _]
  (/ (sqr (+ a b)) (* 4 t)))

For idiomatic access to the values generated by this algorithm, we’ll define a lazy sequence:

(def brent-salamin-terms
     (iterate #(apply brent-salamin-term %) (brent-salamin-term)))

And another for the values of π:

(def brent-salamin-pis (map #(apply brent-salamin-pi %) brent-salamin-terms))

Things look pretty good:

user> (take 5 brent-salamin-pis)
(2.914213562373095 3.1405792505221686 3.141592646213543
 3.141592653589794 3.141592653589794)

But wait - we should probably be careful with precision. Ideally, I’d like to be able to get an arbitrarily precise version of π. Let’s take a look at what kind of numeric types we’re dealing with by printing the class of the inputs to our terms algorithm:

([a b t p]
   (prn (class a))
   (prn (class b))
   (prn (class t))
   (prn (class p))
   (let [A (/ (+ a b) 2)
         B (sqrt (* a b))
         T (- t (* p (sqr (- a A))))
         P (* 2 p)]
     [A B T P]))

user> (apply brent-salamin-term
             (apply brent-salamin-term (brent-salamin-term)))
java.lang.Integer
java.lang.Double
clojure.lang.Ratio
java.lang.Integer
java.lang.Double
java.lang.Double
java.lang.Double
java.lang.Integer
[0.8472249029234942 0.8472012667468914 0.22847329108090064 4]

Ugh - what a mess. We start off with integers in the first iteration, and move quickly to doubles. That’s fine for the real world, where according to Wikipedia “a physicist needs only 39 digits of Pi to make a circle the size of the observable universe accurate to one atom of hydrogen,” but we’re trying for gold here. Let’s start by using BigDecimals wherever we can (see sidebar).

Brent-Salamin using BigInteger

(defn brent-salamin-term
  ([] [1M (/ 1M (sqrt 2M)) (/ 1M 4M) 1M])
  ([a b t p]
     (let [A (/ (+ a b) 2M)
           B (sqrt (* a b))
           T (- t (* p (sqr (- a A))))
           P (* 2M p)]
       [A B T P])))

(defn brent-salamin-pi
  [a b t _]
  (/ (sqr (+ a b)) (* 4M t)))

user> (apply brent-salamin-term
             (apply brent-salamin-term
                    (brent-salamin-term)))
java.math.BigDecimal
java.lang.Double
java.math.BigDecimal
java.math.BigDecimal
java.lang.Double
java.lang.Double
java.lang.Double
java.math.BigDecimal
[0.8472249029234942 0.8472012667468914
 0.22847329108090064 4M]

This is better thanks to Clojure’s smart arithmetic operators - if they receive a BigDecimal they’ll do BigDecimal operations - but there’s still a problem in our sqrt function. Unfortunately, Java doesn’t give us a BigDecimal square root function out of the box, so we’ll have to roll our own. Michael Gilleland at Merriam Park Software explains Heron’s method in Big Square Roots, and while the Java implementation leaves something to be desired, a basic Clojure implementation is actually quite nice:

(defn sqrt
  [n]
  (loop [n n g 1]
    (let [next-guess (/ (+ (/ n g) g) 2)]
      (if (= g next-guess) g (recur n next-guess)))))

That is, until we compile the file, at which point everything explodes!

error: java.lang.ArithmeticException: Non-terminating decimal expansion;
 no exact representable decimal result.

The problem here is that we haven’t specified a precision for the BigInteger operations that happen when we create our lazy sequences at compile time, and indeed, we don’t want to. Instead, we’ll make them into functions so that callers can choose whatever precision they want when they are created. This gets everything compiling, and we jump over to the REPL to give it a whirl:

user> (with-precision 10 (take 10 (etc/brent-salamin-pis)))
java.lang.ArithmeticException: Non-terminating decimal expansion;
  no exact representable decimal result.

The problem (and it’s the last one, I promise!) is that with-precision creates a thread local binding which isn’t available when the lazy sequence is realized later on. Fortunately, Clojure 1.1 includes a handy function for just this purpose, bound-fn. bound-fn creates a function that carries thread local bindings along into whatever context it is evaluated.

(defn brent-salamin-terms
  []
  (iterate (bound-fn [t] (apply brent-salamin-term t)) (brent-salamin-term)))

(defn brent-salamin-pis
  []
  (map (bound-fn [t] (apply brent-salamin-pi t)) (brent-salamin-terms)))

Finally - success!

user> (with-precision 10 (take 5 (etc/brent-salamin-pis)))
(2.914213562M 3.140579251M 3.141592648M 3.141592656M 3.141592656M)

This turned into a bit of a slog at the end, but only when we started caring quite a bit about precision. The default behavior of the language leads to very elegant code organized around lazy sequences that will work in almost all real world applications, and that seems like a major win.

Colophon

2010-01-08T00:00:00+00:00

Unless you’re a web publishing nerd, you should probably stop reading here.

Back in college I wrote an awful lot - one of the advantages of a liberal arts education - but since then I’ve fallen woefully out of practice. I’m pretty sure at least part of the problem is the unpleasant experience that is composing thoughts in WordPress, and my previous attempts to hack together an emacs2WordPress workflow just haven’t panned out.

I’m happy to report, then, that I’m preliminarily very excited about Jekyll, a “blog aware static content generator” written by one of the GitHub guys. Static content generation is certainly nothing new, but the implementation is slick, and some simple Rakefile hacks and git orchestration makes the whole thing really smooth.

So now, writing moves from snippets collected in org files, OmniFocus notes and emacs buffers to Markdown formatted files in my Jekyll tree, and finally gets pushed via Git to a repository on my server, where a post-receive hook runs runs Jekyll. Jekyll works its magic and dumps the results into a directory served by httpd, and that’s what you see. This seems to work pretty well, and lets me keep my text editing where I like it, in emacs. Some handy Jekyll editing functions from ~~Alex Payne~~ metajack help tie things together.

I originally wanted to take advantage of GitHub’s free hosting of Jekyll sites, but ended up wanting a bit more flexibility than they currently provide, mainly around feed generation and serving.

To celebrate the occasion, and just in time for the start of the work year, I’ve also started publishing at a different URL. The luxury of an unusual name keeps me at the top of ”g travis vachon”, so I don’t feel bad about going with something a little more fanciful. combinate is nice and succinct and captures a lot of what I like in the world and technology in particular and, most importantly, wasn’t taken.

So, Happy New Year, and here’s to writing more.