20 January 2008

A new convert to the LOOP facility

Some Common Lisp programmers hate the LOOP facility, some don't.  I used to fall into the first camp, for various reasons, the most important of which is that LOOP is effectively a specialized looping language grafted onto lisp.  Normally I'm a big fan of a single syntactic mode for all corners of a language (like the lisp family, or Smalltalk, quite unlike C or, god help us, perl).

I've been working on some basic forecasting and time series code recently, and I have to say, when you're looping over different time series and smoothing windows, LOOP results in neater code than almost any language I can think of. Here's a simple moving average forecast (in the interest of space, all examples have my anal-retentive sanity checking assertions removed):

(defmethod single-moving-average ((data sequence) (order integer))
(let ((n (length data)))
(/ (reduce #'+ data :start (- n order))

For such simple sums, the functional style reduce does the job. Once you get to a weighted moving average the math starts to get tricker. As I was thinking about the many, many traversals of sequences I'd be doing, I decided to check out LOOP more seriously by reading a chapter from Seibel's book I had previously skipped, 22. LOOP for Black Belts. I started to develop warm feelings for LOOP immediately. For starters, it does a great job of encapsulating the various sorts of set-up and tear-down you have to do when rolling your own loop so the mechanical bits for doing loops don't infest the rest of your code.

One really lovely touch makes it easy to avoid the off-by-one error — and fussing about — that comes when you use zero-indexed arrays. The FOR clause may indicate exclusive or inclusive bounds, with TO n including n, and BELOW n going up to but not including it. So here's a simple weighted moving average function:

(defmethod weighted-moving-average ((data sequence) (order integer))
(let ((n (length data)))
(/ (loop for i from 0 below n
sum (* (elt data i) (+ i 1)))
(/ (* n (+ n 1)) 2.0))))

Now I didn't really have to use LOOP for this, but the code I think is somewhat cleaner. The SUM clause accumulates by summing successive values of the expression after it, and in this simple LOOP clause that final sum will be the value of the expression.

My biggest example of LOOP-fu this weekend is a weighted moving average smoothing function. It takes a sequence of data and a sequence of weights and spits out a vector of the smoothed data. In this implementation I simply take the original values at the edges of the data where the smoothing sequence is longer than available values. What I need to do at each step is apply the weight vector to a window of data to compute the moving average for that step. This brings out the other really lovely feature of LOOP: parallel loop values. Here's the scary result, somewhat un-lisp-like to my eyes, but clearer I suspect than I'd be able to produce with functional style tools and DO:

(defmethod weighted-average ((data sequence) (weights sequence))
(let ((d-n (length data))
(w-n (length weights)))
(loop with smoothed = (make-array (list d-n))
with start = (- w-n 1)
with end = (- d-n w-n)
with denom = (reduce #'+ weights)
for i from 0 below d-n
if (or (< i start) (> i end))
do (setf (aref smoothed i) (elt data i))
do (setf (aref smoothed i)
(/ (loop for j from 0 below w-n
for dj from (- i start) to i
summing (* (elt weights j) (elt data dj)))
finally (return smoothed))))

A LOOP within a LOOP! The underlined section shows the parallel loop indices, j going over the weights sequence and dj going over the current window on the data. In the outer LOOP I went a bit crazy and used a lot of its abilities — initializing temporary variables, LOOP conditionals, a FINALLY clause — with the results that look like an Algol-Lisp chimera.

If I were a code purist weighted-average would probably make me crazy. Good thing I'm not.

No comments: