Extending the ITERATE macro
Posted in Uncategorized on October 26th, 2008- Table of contents
- 1. Generators
- 2. Writing a new gathering clause
- 3. Writing a new driver
- Appendix: Extending the LOOP macro
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:
- Gatherers, like
collectingorsumming, for accumulating or reducing an expression; - Drivers, introduced with
fororgenerate, 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 makesin-treecompatible with bothgenerateandfor. - The form introduced by the symbol
nextis the code that will run on each iteration offoror on occurrence of theNEXToperator withgenerate. - 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.
TERMINATEis 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.
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:
Thanks to Sam Freilich for his comments and suggestions.