7

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.

Improve this question
1
  • Which Lisp dialect are you using? Common Lisp? Commented Apr 15, 2012 at 15:54

3 Answers 3

Reset to default
8

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))
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Function is great too. I love your coding. Since I prefer indexes to roll starting from left, I need to replace '(reverse args)' with just 'args', and in the last line 'dimensions' with '(reverse dimensions)'.
If n is the value of a dimension, I would suggest that the loop (in the function) should go either from 0 to n-1 (my choice), or from 1 to n. In the former case you just need to replace 'to' with 'below' in the loop clause.
7

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.

Improve this answer

8 Comments

This is what I was aiming to, but was not able. I'm studying your code. Is there any secret book where you learnt such acrobatic Lisp coding?
It seems that the 1st index miss the last iteration, i.e. in your example variable 'i' takes only the values 0 and 1 missing the value 2. Or, as a better alternative, variables 'j' and 'k' should go from 0 to their value less 1: so that 'counts' meant how many iterations for each variables.
Just a style suggestion; try having the base case when vars and counts are empty. Then the macro-level logic will all come first, and depending on the base case, will generate different code. Then the dotimes code will only be in the non-base-case branch, body will only be in the base-case-branch, and you should have a few less backquoting acrobatics to go through. @mmj Let Over Lambda has a good chapter on writing recursive macros.
@mmj: I'm not used to loops and I didn't realize you were looking for the specific construct. Also normally I loop from 0 to (1- n) (therefore n iterations). Both issues are fixed and now the macro matches your question text (to tell the whole truth I implemented originally it in a Lisp dialect REPL where there is no loop facility).
@claytontstanley: it was my first version, but I didn't like the idea of expanding to a progn form. There is indeed no reason for this so I reverted to a formulation that is clearly simpler to understand. Thanks for pointing that out.
|
2

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?

Improve this answer

1 Comment

I choose the other answer because of conciseness, but I acknowledge that yours is more fexible. I'm impressed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.