Side by side: Python, Common Lisp, Clojure

UPDATE: Find the rest of the code at http://bitbucket.org/gavinmcgovern/clj-bayes/.

My holiday project (of the sort that doesn’t involve cooking at least) is porting the Bayesian spam code from Peter Seibel’s great book “Practical Common Lisp” to Clojure. This will be a big part of the next-gen Big In Twitter that’s slowly coming together. Although I’ve been using Bayes, I haven’t really understood what was going on under the hood. I’m finding Peter’s chapter a fantastic walkthrough & approach to understanding it. He presents the basics and then goes on and adds optimizations. Perfect.

It was smooth sailing up until the other day. One little function tripped me up. I’ll show you.

Peter based some of his spam filter Common Lisp on a Python implementation from an article by Gary Robinson. Specifically Peter created a chi square function from this Python:

def chi2P(chi, df):
    assert df & 1 == 0
    m = chi / 2.0
    sum = term = math.exp(-m)
    for i in range(1, df//2):
        term *= m / i
        sum += term
    return min(sum, 1.0)

There’s a lot to like there (I removed the comments): concise, minimal noise, short. Even if you didn’t know the math (like me!) you could probably follow along. Would probably be even shorter if you used Python’s list comprehensions.

Here’s what Peter came up with for the Common Lisp version:

(defun inverse-chi-square (value degrees-of-freedom)
  (assert (evenp degrees-of-freedom))
  (min
   (loop with m = (/ value 2)
      for i below (/ degrees-of-freedom 2)
      for prob = (exp (- m)) then (* prob (/ m i))
      summing prob)
   1.0))

He uses the oddball loop macro. It’s a DSL for iteration. It’s charming, it’s weird, it doesn’t seem very Lispy. I like how it has synonyms, “summing” for “sum”, “collecting” for “collect”, etc. Verb tense agreement is important!

While there’s a loop in Clojure it isn’t at all related to Common Lisp’s loop. This is where things got a little muddy for me. Spent a lot of time trying various approaches and while I was able to achieve parts of the original function I wasn’t able to get the whole thing. The combination of “term *= m/i ” and the “sum += term” was killing me; so much happening at once.

Taking a breather I started poking around clojure-contrib. There is so much buried in there. A real gold mine. I eventually stumbled upon seq-utils and the “reductions” function. And that was exactly 100% what I needed. After Seq-utils and a little of Clojure’s list comprehensions and 10 minutes of coding I had this:

(defn inverse-chi-square
  [chi df]
  (assert (even? df))
  (let [m (/ chi 2.0)]
    (min
      (reduce +
        (reductions * (Math/exp (- m)) (for [i (range 1 (/ df 2))] (/ m i))))
      1.0)))

It’s been many many years since I did any sort of Common Lisp programming but one lasting memory was the vast quantity of high quality code freely available. Lots of motivated people writing excellent Common Lisp. I’m finding the same with the Clojure community. I love just being able to reach into the common libs, pull out a few gems and slap them together. Thanks! (Btw, anything wrong my version?!)