Extending the ITERATE macro

Published October 26th, 2008

In a previous article I gave an overview of ITERATE but punted on showing its best feature, the ability to extend it to support new iteration constructs. These can be separated into two groups:

  1. Gatherers, like collecting or summing, for accumulating or reducing an expression;
  2. Drivers, introduced with for or generate, for changing a value in a pattern or looping over a data structure.

The generate driver type didn’t appear in the article comparing LOOP and ITERATE (it’s wholly a feature of ITERATE), so here first is a short introduction.

1. Generators

A generate clause is like a lazy for; its named variable will only update its value when told with NEXT. An example:

;; First, the regular `for`:
(iter (for el in '(a b c))
      (for i from 10)
      (when (primep i)
        (collect (list i el) into primes))
      (collect el into letters)
      (finally (return (values letters
                               primes))))
=> (A B C)
   ((11 B))
 
;; Now, using `generate` for el instead:
(iter (generate el in '(a b c))
      (for i from 10)
      (when (primep i)
        (collect (list i (next el)) into primes))
      (collect el into letters)
      (finally (return (values letters
                               primes))))
=> (NIL A A B B B B C C)
   ((11 A) (13 B) (17 C))

With these semantics, generate can appear anywhere for can appear:

(generate i upfrom 0)
(generate c in-string "black")
(generate form in-file "sexp.lisp")
(generate sym in-package :ITERATE)

2. Writing a new gathering clause

In the previous article I wrote a quick dividing clause:

(defmacro dividing (num &keys (initial-value 0))
  `(reducing ,num by #'/ initial-value ,initial-value))
 
(iter (for i in '(10 5 2))
      (dividing i :initial-value 100))
=> 1

This was easy, but it’s not fully idiomatic; :initial-value must be specified as a keyword, and I can’t collect the value into a variable without modifying the macro. Updating the macro with this functionality makes it noticeably more complex:

(defmacro dividing (num &key (initial-value 0) into)
  `(reducing ,num by #'/
             initial-value ,initial-value
             ,@(when into
                 `(into ,into))))

We can solve both problems cleanly by using instead ITERATE’s DEFMACRO-CLAUSE:

(defmacro-clause (DIVIDING expr
                  &optional
                  INTO var
                  FROM start)
  "Divide into a variable"
  `(reducing ,expr by #'/ into ,var initial-value ,start))
 
;; Now this works:
(iter (for i in '(10 5 2))
      (dividing i from 100 into quotient)
      (multiplying i into product)
      (finally (return (values product quotient))))
=> 100
   1

DEFMACRO-CLAUSE takes care of setting up support for both keyword and regular symbol syntax, provides more informative error messages when the clause is misused, and adds the clause to DISPLAY-ITERATE-CLAUSES:

(display-iterate-clauses 'dividing)
DIVIDING &OPTIONAL INTO FROM  Divide into a variable

Lastly, to continue the LOOP idiom of naming clause actions in both their infinitival and present-participle form, we can use DEFSYNONYM:

(defsynonym divide dividing)

3. Writing a new driver

The easiest way to write new for clauses is with DEFMACRO-DRIVER. ITERATE offers in, on, in-vector, in-string, the more general in-sequence, in-hashtable, and more. Say we want to write a driver to iterate over the leaves of a tree. This is a little tricky since tree traversal is usually written recursively. To start us off, here’s a function which will return all leaves:

(defun collect-leaves (tree)
  "Return all leaf nodes in depth-first order."
  (iter (with stack = (list tree))
        (while stack)
        (for node = (pop stack))
        (if (consp node)
            (destructuring-bind (l . r) node
              (unless (endp r)
                (push r stack))
              (push l stack))
            (collect node))))
 
(collect-leaves '(((a b) (c) d) e (f (g (h)) i) j))
=> (A B C D E F G H I J)

We need only splice this into a macro, with some modifications:

(defmacro-driver (FOR leaf IN-TREE tree)
  "Iterate over the leaves in a tree"
  (let ((gtree (gensym))
        (stack (gensym))
        (kwd (if generate 'generate 'for)))
    `(progn
       (with ,gtree = ,tree)
       (with ,stack = (list ,gtree))
       (,kwd ,leaf next
             (let ((next-leaf
                    (iter (while ,stack)
                          (for node = (pop ,stack))
                          (if (consp node)
                              (destructuring-bind (l . r)
                                  node
                                (unless (endp r)
                                  (push r ,stack))
                                (push l ,stack))
                              (return node)))))
               (or next-leaf (terminate)))))))
  • The (if generate 'generate 'for) bit makes in-tree compatible with both generate and for.
  • The form introduced by the symbol next is the code that will run on each iteration of for or on occurrence of the NEXT operator with generate.
  • Here we’ve slipped an ITERATE call inside the driver, effectively nesting ITERATE loops. This wasn’t necessary; DO or LOOP could also have been used.
  • TERMINATE is a special form in an ITERATE driver to indicate completion.

Finally, bringing it all together:

(iter (for leaf in-tree '(((2 3) (5) 1) 8 (4 (1 (2)) 2) 3))
      (collecting leaf into leaves)
      (multiplying leaf into product)
      (dividing leaf into quotient initial-value 2000)
      (finally (return (values leaves
                               product
                               quotient))))
=> (2 3 5 1 8 4 1 2 2 3)
   11520
   25/144

Appendix: Extending the LOOP macro

SBCL developer Richard Kreuter showed me an implementation-specific way to incorporate new syntax into LOOP. The linked code adds a for clause for binding multiple value returns (functionality that exists in ITERATE, but not the standard LOOP macro). This is meant less as a point of comparison than as proof that LOOP can indeed be extended.

loop-values-path.lisp

Usage:

(loop for dividend in '(1 2 3 4 5)
      for (quotient remainder) being the values of
          (floor dividend 2)
      do (format t "~D ~D~%" quotient remainder))
0 1
1 0
1 1
2 0
2 1

See also this file from CLSQL which provides LOOP extensions for iterating over records and supports seven Common Lisp compilers:

loop-extension.lisp

Further discussion on the programming reddit

Published October 26th, 2008.


One Response to “Extending the ITERATE macro”

  1. items.sjbach.com » Comparing LOOP and ITERATE Says:
    November 17th, 2008 at 00:48

    […] extensibility is discussed in-depth in a second article. Through some means, LOOP can apparently be extended, but it is not done often or easily. SBCL, at […]