content/blog/2016/09/iterate-averaging.markdown @ fdf01e99fd51

+++
title = "Customizing Common Lisp's Iterate: Averaging"
snip = "Don't loop, iterate!"
date = 2016-09-20T13:45:00Z
draft = false

+++

When I first started learning Common Lisp, one of the things I learned was the
[loop macro][loop].  `loop` is powerful, but it's not extensible and [some
people find it ugly][lol].  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 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.

[loop]: http://www.gigamonkeys.com/book/loop-for-black-belts.html
[iterate]: https://common-lisp.net/project/iterate/
[lol]: /media/images/blog/2016/09/loop-macro.jpg

<div id="toc"></div>

## End Result

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

```lisp
(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:

```lisp
(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][man]
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][ink] and [you
type fast (right?)][typing] 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:

```lisp
(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.

[man]: https://common-lisp.net/project/iterate/doc/Rolling-Your-Own.html#Rolling-Your-Own
[ink]: http://www.bash.org/?105201
[typing]: https://steve-yegge.blogspot.is/2008/09/programmings-dirtiest-little-secret.html

## 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][mxi] a `macroexpand-iterate` function for my own sanity.
It's not pretty, but it gets the job done:

```lisp
(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)))
```

[mxi]: https://github.com/sjl/cl-losh/blob/55de0419a9b97a35943ce4884b598dbd99cc5670/losh.lisp#L1105-L1151