I’m off on a round of conferences, classes and talks soon, so I figured I’d list them here.

OK, all you Clojure gurus, I need your help. I need to speed this algorithm up.

Just for fun I thought I’d write the Jarvis March algorithm in Clojure. This algorithm is for finding the convex hull of a collection of points. The basic idea is really simple. Imagine that all the points in the collection are represented by nails in a board. Find the left-most nail and tie a string to it. Then wind the string around the nails. The string will only touch nails that are part of the convex hull.

I wrote a blog the other day about functional refactoring and I had what I thought was a good example:

absPosition :: Buffer -> Int
absPosition (Buffer (x, y) contents) = x + lenPreviousLines contents
  where lenPreviousLines = 
    foldr ((+).length) 0 . take y . terminatedLines

No, this isn’t a blog about how to do TDD in a functional language. Rather, it’s a blog about the similarities between the two disciplines.

Clojure makes a nice language for writing scripts that explore things on the filesystem. For example, here is a cute little program that explores the FitNesse source tree counting the lines of production java code and comparing it to the lines of unit test code.

Here’s what wikipedia has to say about lazy evaluation:

The benefits of lazy evaluation include: performance increases due to avoiding unnecessary calculations, avoiding error conditions in the evaluation of compound expressions, the ability to construct infinite data structures, and the ability to define control structures as regular functions rather than built-in primitives.

It’s all true, but I think it misses a point. One of the nicest things about lazy evaluation is that it enables a different form of abstraction. Take a look at this code. It computes the Mandelbrot Set. There are many ways to code up this algorithm, but the code I just linked to is very typical – it’s a doubly nested loop which iterates over a specific rectangle in the complex plane. It’s hard to see anything that’s awkward about its iteration strategy in a procedural language – the algorithm does require starting and ending points in the plane.

Let’s look at a different way of approaching this. Here’s part of a Mandelbrot Set generator in Haskell:

mandelbrot :: Double -> [[Int]]
mandelbrot incrementSize =
  [[ escapeIterations $ translate offset . translate (x,y) . mandel
    | x <- increments]
    | y <- increments] 
   where increments = [0.0, incrementSize .. ]

window :: (Int, Int) -> (Int, Int) -> [[a]] -> [[a]]
window (x0, x1) (y0, y1) = range y0 y1 . map (range x0 x1)
  where range m n = take (n-m) . drop m

The interesting bit is the mandelbrot function. It contains a doubly-nested list comprehension which, essentially, mimics the behavior of a doubly-nested loop in the procedural algorithm. However, there is one interesting difference. This list comprehension actually represents the mandelbrot computation across a full quarter of the infinite plane – it goes from zero to infinity in x and y. All we have to do is pass it an increment size and it is configured to create that grid. If we want to zoom in to a particular place in the Mandelbrot Set, we can use the window function like this:

-- compute the mandelbrot from (10,10) inclusive to
-- (20,20) exclusive with an increment of 0.05 

window (10, 20) (10, 20) $ mandelbrot 0.05

The trick to this code is in window’s range computation. It takes a starting position, an ending position, and a list and it drops all of the elements of the list before the starting position, without evaluating them, and then it takes, from the front of the new list, end - start elements, giving us a sub-range from the original list. When that elements of that sub-list are evaluated, the computation for each point in the window occurs.

This code yields the computation that we want and the neat thing is, we are really only computing the piece we specified with window. We’ve essentially formed a general computation and imposed the edges later.

Looking back now at the imperative mandelbrot code, it’s easy to see that it was, in a way, mixing two concerns. The code which determined the range was mixed with the code which generated the set. Laziness allows us to separate the two concerns.

Note: There are much more direct ways of computing the Mandelbrot Set in Haskell. Here’s one which is particularly brief.

While I think Clojure is an interesting language, in order for it to be of real practical use, I must be able to use it in conjunction with other systems I am working on. Specifically, I’d like to write some FitNesse tools in Clojure; but for that to work, I’ll need to call into my Clojure code from Java.

I tweeted this not too long ago. The basic idea is that as you add tests, the tests get more and more specific. This makes sense since tests are, after all, specifications. The more specifications you have, the more specific the whole body of specifications becomes.

As a general rule, good design dictates that the more specific your requirements become, the more general your code needs to be. This is saying roughly the same thing as Greenspun’s Tenth Rule of Programming: “Any sufficiently complicated [...] program contains an ad hoc informally-specified bug-ridden slow implementation of half of Common Lisp.” Or rather, as more and more constraints pile upon a program, the designers look for ways to push those constraints out of the program itself and into the data.

In return for my tweet people asked for examples.

Coding with infinite sequences is very powerful, but also very bizarre. If you aren’t careful you can get algorithms that work fine, but are O(N^2) instead of O(N).

I’ve been working in Haskell recently, and I find myself doing much less refactoring. In fact, I rewrite more than I refactor.

I’m not talking about massive refactoring, but rather the sort of micro-refactoring that I do to move from one algorithm to another. If you are working in an imperative language, you can often make micro waypoints – little testable steps along the way as you change your code from one shape to another. You can add a variable, confident that behavior won’t change because you haven’t used it yet, and you can move one statement down below another, changing the order of a calculation if (again) you are confident that the overall computation is order in variant. As I TDD my code, I do those sorts of things. I often refactor by introducing a parallel computation in the same method as the old one, and if the test passes, I knock out the old way of doing things and leave the shiny new one.

In Haskell, however, I don’t do that, and it reduces the amount of time that I spend refactoring. Yes, I rename variables, add parameters, and introduce where-clauses, etc. But, refactoring in Haskell seems different, and I think I know why now. There are two reasons and they sort of intermingle.