Lisp macro that does loop "unrolling"

Question

My first steps with Lisp macros...

(defconstant width 7)
(defconstant height 6)
...
; board is a 2D array of width x height
; and this is my first ever macro:
(defmacro at (y x)
  `(aref board ,y ,x))
; "board" must be available wherever the macro is used.

(defun foo (board ...)
  ...
  (loop for y from 0 to (1- height) do
    ; thanks to the "at" macro, this is cleaner:
    (let ((score (+ (at y 0) (at y 1) (at y 2))))
      (loop for x from 3 to (1- width) do
        (incf score (at y x))
        ; ...do something with score
        (decf score (at y (- x 3)))))))

The code uses my first ever macro, the "at" one. It emits "access instructions" to read from board[y][x], so it can only be used in places where "board" exists, like the function "foo" above.

This worked - and then I realized that... I can go further.

The two nested loops are "statically" constrained: from 0 to height-1 for y, from 3 to (width-1) for x... so in theory, I can create a macro that emits (unrolls!) the exact incf and decf instructions done in the loops' code!

I tried this:

(defmacro unroll ()
  (loop for y from 0 to (1- height) do
    `(setf score (+ (at ,y 0)  (at ,y 1) (at ,y 2)))
    (loop for x from 3 to (1- width) do
     `(incf score (at ,y ,x))
     `(decf score (at ,y (- ,x 3))))))

...but failed - "(macroexpand-1 '(unroll))" shows me NIL.

What am I doing wrong?

In case it is not clear, I want to use two nested loops and emit "code" at the beginning of the outer loop, and for each iteration of the inner loop.

Any help most appreciated (I am a LISP newbie).

UPDATE: After @larsmans' kind advice, I succeeded in applying this change to my code - and to my immense satisfaction, I watched the Lisp version of my Score4 algorithm become the 2nd fastest implementation, behind only C and C++ (and faster than OCaml!).

Fred Foo Fred Foo · Accepted Answer · 2011-11-05T17:57:55

You should collect the statements you generate inside the macro's loop, not pretend to execute them with do:

(defmacro unroll ()
  (loop for y from 0 to (1- height)
        collect
          `(begin (setf score (+ (at ,y 0)  (at ,y 1) (at ,y 2)))
                  ,@(loop for x from 3 to (1- width)
                          collect `(begin (incf score (at ,y ,x))
                                          (decf score (at ,y (- ,x 3))))))))

Lisp macro that does loop "unrolling"

1 Answers