Lisp macro (or function) for nested loops

Question

Is it possible to write a general Lisp macro that takes a list of dimensions and variables, a body (iterations), and creates code consisting of many nested loops specified in the list?

That is, something like:

(nested-loops '(2 5 3) '(ijk) whatever_loop_body) 

should expand to

 (loop for i from 0 below 2 do (loop for j from 0 below 5 do (loop for k from 0 below 3 do whatever_loop_body))) 

Following actions

As huaiyuan correctly pointed out, I need to know the parameters that need to be passed to the macro at compile time. If you really need a feature like me, see below.

If you're fine with a macro, go for recursive solution 6502, that's great.

Answer 1

You do not need quotes, as sizes and variables must be known at compile time.

 (defmacro nested-loops (dimensions variables &body body) (loop for range in (reverse dimensions) for index in (reverse variables) for x = body then (list y) for y = `(loop for ,index from 0 to ,range do ,@x) finally (return y))) 

Edit:

If sizes cannot be determined at compile time, we will need a function

 (defun nested-map (fn dimensions) (labels ((gn (args dimensions) (if dimensions (loop for i from 0 to (car dimensions) do (gn (cons i args) (cdr dimensions))) (apply fn (reverse args))))) (gn nil dimensions))) 

and wrap the body in lambda when called.

 CL-USER> (nested-map (lambda (&rest indexes) (print indexes)) '(2 3 4)) (0 0 0) (0 0 1) (0 0 2) (0 0 3) (0 0 4) (0 1 0) (0 1 1) (0 1 2) (0 1 3) (0 1 4) (0 2 0) (0 2 1) ... 

Edit (2012-04-16):

The aforementioned version of the nested map was written to better reflect the original statement of the problem. As mmj said in the comments, it may be more natural to make the range of indices from 0 to n-1, and moving the inverse of the output from the inner loop should increase efficiency if we do not insist on row-wise iteration orders. In addition, it is probably more reasonable that the input function accepts a tuple instead of individual indices in order to be rank independent. Here is the new version with the indicated changes:

 (defun nested-map (fn dimensions) (labels ((gn (args dimensions) (if dimensions (loop for i below (car dimensions) do (gn (cons i args) (cdr dimensions))) (funcall fn args)))) (gn nil (reverse dimensions)))) 

Then

 CL-USER> (nested-map #'print '(2 3 4)) 

Answer 2

Sometimes an approach that is useful is to write a recursive macro, that is, a macro that generates code containing another call to the same macro, unless this case is simple enough to be solved directly:

 (defmacro nested-loops (max-values vars &rest body) (if vars `(loop for ,(first vars) from 0 to ,(first max-values) do (nested-loops ,(rest max-values) ,(rest vars) ,@body)) `(progn ,@body))) (nested-loops (2 3 4) (ijk) (print (list ijk))) 

In the above example, if the list of variables is empty, the macro extends directly to the body shapes, otherwise the generated code is (loop...) for the first variable containing another call (nested-loops ...) in the do part.

A macro is not recursive in the usual sense used for functions (it does not call itself directly), but macro expansion logic will call the same macro for the internal parts until the code generation is complete.

Note that the maximum value forms used in the inner loops will be reevaluated at each iteration of the outer loop. It doesn’t matter if the forms are really numbers, as in your test case, but they are different if they are, for example, function calls.

Answer 3

Hm. Here is an example of such a macro in general lisp. Note, however, that I'm not sure if this is actually a good idea. But we are all adults here, right?

 (defmacro nested-loop (control &body body) (let ((variables ()) (lower-bounds ()) (upper-bounds ())) (loop :for ctl :in (reverse control) :do (destructuring-bind (variable bound1 &optional (bound2 nil got-bound2)) ctl (push variable variables) (push (if got-bound2 bound1 0) lower-bounds) (push (if got-bound2 bound2 bound1) upper-bounds))) (labels ((recurr (vars lowers uppers) (if (null vars) `(progn ,@body) `(loop :for ,(car vars) :upfrom ,(car lowers) :to ,(car uppers) :do ,(recurr (cdr vars) (cdr lowers) (cdr uppers)))))) (recurr variables lower-bounds upper-bounds)))) 

The syntax is slightly different from your suggestion.

 (nested-loop ((i 0 10) (j 15) (k 15 20)) (format t "~D ~D ~D~%" ijk)) 

expands in

 (loop :for i :upfrom 0 :to 10 :do (loop :for j :upfrom 0 :to 15 :do (loop :for k :upfrom 15 :to 20 :do (progn (format t "~d ~d ~d~%" ijk))))) 

The first argument to the macro is a list of the form list.

 (variable upper-bound) 

(with a lower limit of 0 implied) or

 (variable lower-bound upper-bounds) 

With less love applied, you can even something like

 (nested-loop ((i :upfrom 10 :below 20) (j :downfrom 100 :to 1)) ...) 

but then, why bother if the loop already has all these functions?