Recursive Lisp Macros
Let’s imagine that I have a set of items represented by a list.
(defparameter items '(A B C D))
I would like to take some action with all possible lists of a particular length, composed of members of this set (with replacement). For example, with length five:
'(A A A A A)
'(A A A A B)
'(A A A A C)
...
'(C B A D A)
...
'(D D D D C)
'(D D D D D)
What I really want is to have a macro that will let me operate on each member of such a list, without necessarily having to generate a huge list and then loop through it. In my idealized little world, I would like to have a macro that looks like this:
(do-enumerations (var items len)
; Do something with the list stored in var
...
)
var is the variable you wish to contain the current enumeration (I’m using the word “enumeration” here, for lack of a better word. “Permutation” is definitely the wrong word.), items is the set of possible members, as exemplified above, and len is the desired length of the enumeration. It is quite tempting to implement this with something like this:
(defmacro do-enumerations ((var items len) &body body)
(if (= len 0) `@body
`(dolist (i items)
,(do-enumerations var items (- len 1) body))))
But this is WRONG and it will crash your compiler, because you don’t have access to len at compile time, so it recurses off to infinity. So in my search for greater Lisp wisdom I am thinking about better ways to solve this problem. Comments and suggestions are greatly appreciated. There must be some relatively elegant macro solution.
In any case, what I’ve come up with isn’t particularly elegant and doesn’t use recursion in the macro. It basically just takes advantage of the fact that what we’re really doing is counting in a radix that is the size of the item set.
(defmacro do-enumerations ((var items len) &body body)
(let ((num-items (gensym))
(item-vec (gensym))
(indices (gensym))
(next-enum (gensym))
(loopvar (gensym)))
`(let ((,num-items (length ,items))
(,item-vec (coerce ,items 'vector))
(,indices (make-list ,len :initial-element 0)))
(labels ((,next-enum (cur)
(cond ((null cur) ())
((= (car cur) (- ,num-items 1))
(cons 0 (,next-enum (cdr cur))))
(t (cons (+ (car cur) 1) (cdr cur))))))
(dotimes (,loopvar (expt ,num-items ,len))
(let ((,var (mapcar #'(lambda (x) (aref ,item-vec x)) ,indices)))
,@body
(setf ,indices (,next-enum ,indices))))))))
One thing that can be improved here for sure is that the entire list of items is regenerated every time from the original item list. I use a vector for faster random access, but most of the time, only the first element changes, so that mapcar could be replaced with something that didn’t iterate over the entire list.
Slightly more concise code might use the with-gensyms macro:
(defmacro with-gensyms (syms &body body)
`(let ,(mapcar #'(lambda (s) `(,s (gensym))) syms)
,@body))
(defmacro do-enumerations ((var items len) &body body)
(with-gensyms (num-items item-vec indices next-enum loopvar)
`(let ((,num-items (length ,items))
(,item-vec (coerce ,items 'vector))
(,indices (make-list ,len :initial-element 0)))
(labels ((,next-enum (cur)
(cond ((null cur) ())
((= (car cur) (- ,num-items 1))
(cons 0 (,next-enum (cdr cur))))
(t (cons (+ (car cur) 1) (cdr cur))))))
(dotimes (,loopvar (expt ,num-items ,len))
(let ((,var (mapcar #'(lambda (x) (aref ,item-vec x))
,indices)))
,@body
(setf ,indices (,next-enum ,indices))))))))