Customizing Common Lisp's Iterate: Averaging

Posted on September 20th, 2016.

When I first started learning Common Lisp, one of the things I learned was the loop macro. loop is powerful, but it's not extensible and some people find it ugly. The iterate library was made to solve both of these problems.

Unfortunately I haven't found many guides or resources on how to extend iterate. The iterate manual describes the macros you need to use, but only gives a few sparse examples. Sometimes it's helpful to see things in action.

I've made a few handy extensions myself in the past couple of months, so I figured I'd post about them in case someone else is looking for examples of how to write their own iterate clauses and drivers.

This entry is the first in a series:

• Averaging
• Timing

This first post will show how to make a averaging clause that keeps a running average of a given expression during the loop. I've found it handy in a couple of places.

1. End Result
2. Code
3. Debugging

End Result

Before we look at the code, let's look at what we're aiming for:

(iterate (for i :in (list 20 10 10 20))
         (averaging i))
; =>
15

(iterate (for l :in '((10 :foo) (20 :bar) (0 :baz)))
         (averaging (car l) :into running-average)
         (collect running-average))
; =>
(10 15 10)

Simple enough. The averaging clause takes an expression (and optionally a variable name) and averages its value over each iteration of the loop.

Code

There's not much code to averaging, but it does contain a few ideas that crop up often when writing iterate extensions:

(defmacro-clause (AVERAGING expr &optional INTO var)
  "Maintain a running average of `expr` in `var`.

  If `var` is omitted the final average will be
  returned instead.

  Examples:

    (iterate (for x :in '(0 10 0 10))
             (averaging x))
    =>
    5

    (iterate (for x :in '(1.0 1 2 3 4))
             (averaging (/ x 10) :into avg)
             (collect avg))
    =>
    (0.1 0.1 0.13333334 0.17500001 0.22)

  "
  (with-gensyms (count total)
    (let ((average (or var iterate::*result-var*)))
      `(progn
        (for ,count :from 1)
        (sum ,expr :into ,total)
        (for ,average = (/ ,total ,count))))))

We use defmacro-clause to define the clause. Check the iterate manual to learn more about the basics of that.

The first thing to note is the big docstring, which describes how to use the clause and gives some examples. I prefer to err on the side of providing more information in documentation rather than less. People who don't need the hand-holding can quickly skim over it, but if you omit information it can leave people confused. Your monitor isn't going to run out of ink and you type fast (right?) so be nice and just write the damn docs.

Next up is selecting the name of the variable for the average. The (or var iterate::*result-var*) pattern is one I use often when writing iterate clauses. It's kind of weird that *result-var* isn't external in the iterate package, but this idiom is explicitly mentioned in the manual so I suppose it's fine to use.

Finally, we could have written a simpler version of averaging that just returned the result from the loop:

(defmacro-clause (AVERAGING expr)
  (with-gensyms (count total)
    `(progn
      (for ,count :from 1)
      (sum ,expr :into ,total)
      (finally (return (/ ,total ,count))))))

This would work, but doesn't let us see the running average during the course of the loop. iterate's built-in clauses like collect and sum usually allow you to access the "in-progress" value, so it's good for our extensions to support it too.

Debugging

This clause is pretty simple, but more complicated ones can get a bit tricky. When writing vanilla Lisp macros I usually end up writing the macro and then macroexpand-1'ing a sample of it to make sure it's expanding to what I think it should.

As far as I can tell there's no simple way to macroexpand an iterate clause on its own. This is really a pain in the ass when you're trying to debug them, so I hacked together a macroexpand-iterate function for my own sanity. It's not pretty, but it gets the job done:

(macroexpand-iterate '(averaging (* 2 x)))
; =>
(PROGN
 (FOR #:COUNT518 :FROM 1)
 (SUM (* 2 X) :INTO #:TOTAL519)
 (FOR ITERATE::*RESULT-VAR* = (/ #:TOTAL519 #:COUNT518)))

(macroexpand-iterate '(averaging (* 2 x) :into foo))
; =>
(PROGN
 (FOR #:COUNT520 :FROM 1)
 (SUM (* 2 X) :INTO #:TOTAL521)
 (FOR FOO = (/ #:TOTAL521 #:COUNT520)))