Lisp macro (or function) for nested loops

问题:

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

That is, something like:

(nested-loops '(2 5 3) '(i j k) whatever_loop_body)

should be expanded 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)))

Follow up

As huaiyuan correctly pointed out, I have to know the parameters to pass to macro at compile time. If you actually need a function as I do, look below.

If you are ok with a macro, go for the recursive solution of 6502, is wonderful.

回答1:

You don't need the quotes, since the dimensions and variables need to be known at compile time anyway.

(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 the dimensions cannot be decided at compile time, we'll 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 to wrap the body in lambda when calling.

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 above version of nested-map was written to more closely reflect the original problem statement. As mmj said in the comments, it's probably more natural to make index range from 0 to n-1, and moving the reversing out of the inner loop should improve efficiency if we don't insist on row-major order of iterations. Also, it's probably more sensible to have the input function accept a tuple instead of individual indices, to be rank independent. Here is a new version with the stated 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))

回答2:

Sometimes an approach that is useful is writing a recursive macro, i.e. a macro that generates code containing another invocation of the same macro unless the 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) (i j k)
  (print (list i j k)))

In the above if the variable list is empty then the macro expands directly to the body forms, otherwise the generated code is a (loop...) on the first variable containing another (nested-loops ...) invocation in the do part.

The macro is not recursive in the normal sense used for functions (it's not calling itself directly) but the macroexpansion logic will call the same macro for the inner parts until the code generation has been completed.

Note that the max value forms used in the inner loops will be re-evaluated at each iteration of the outer loop. It doesn't make any difference if the forms are indeed numbers like in your test case, but it's different if they're for example function calls.

回答3:

Hm. Here's an example of such a macro in common lisp. Note, though, that I am not sure, that this is actually a good idea. But we are all adults here, aren't we?

(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 proposal.

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

expands into

(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~%" i j k)))))

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

(variable upper-bound)

(with a lower bound of 0 implied) or

(variable lower-bound upper-bounds)

With a little more love applied, one could even have something like

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

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