content/blog/2016/09/iterate-averaging.html @ bbf39c61e3fe

    {% extends "_post.html" %}

    {% hyde
        title: "Customizing Common Lisp's Iterate: Averaging"
        snip: "Don't loop, iterate!"
        created: 2016-09-20 14:00:00
    %}

    {% block article %}

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 (at least not
*portably*) 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{{ parent_url }}/loop-macro.jpg

[TOC]

## 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

    {% endblock article %}