Lisp: can a macro be recursive?

问题:

I've recently started coding in Lisp, and have already been most impressed with macros - they allowed me to do complex loop-unrolling at compile-time, something I can't do this elegantly in any other language that I know of (i.e. code-generate while keeping the original structure).

On to optimization: I've sprinkled type annotations (lots of "the fixnum") in the same code. Once I've added 3 or 4 of them, I realized I was doing it wrong - this is what macros are for, Dont Repeat Yourself...

; whenever we want to indicate that the result of an operation 
; fits in a fixnum, we macro expand (the fixnum (...))
(defmacro fast (&rest args)
  `(the fixnum ,args))
...
(cond
  (...)
  (t (let* ((forOrange (+ (aref counts 5)
                          (fast * 2 (aref counts 6))
                          (fast * 5 (aref counts 7))
                          (fast * 10 (aref counts 8))))
            (forYellow (+ (aref counts 3)
                          (fast * 2 (aref counts 2))
                          (fast * 5 (aref counts 1))
                          (fast * 10 (aref counts 0))))

...and indeed, this worked: instead of writing lots of "(the fixnum (...))" everywhere, I just quickly prefix the expression with "fast" - and all is well.

But then...

I realized that even this is not where things should stop: in principle, the macro "fast" should... be called at the TOP of the evaluation, in this case:

            (forYellow (fast + (aref counts 3)
                          (* 2 (aref counts 2))
                          (* 5 (aref counts 1))
                          (* 10 (aref counts 0))))

...and it should recursively "plant" "(the fixnum (...))" in all subexpressions.

Can this be done? Can a "defmacro" be recursive?

UPDATE: I faced some really weird problems trying to do this, so I ended up doing what Rord suggested below - i.e. implemented a function, tested it in the repl, and calling it from the macro:

(defun operation-p (x)
  (or (equal x '+) (equal x '-) (equal x '*) (equal x '/)))

(defun clone (sexpr)
  (cond
    ((listp sexpr)
     (if (null sexpr)
       ()
       (let ((hd (car sexpr))
             (tl (cdr sexpr)))
         (cond
           ((listp hd) (append (list (clone hd)) (clone tl)))
           ((operation-p hd) (list 'the 'fixnum (cons hd (clone tl))))
           (t (cons hd (clone tl)))))))
    (t sexpr)))

(defmacro fast (&rest sexpr)
  `(,@(clone sexpr)))

And it works fine under SBCL:

$ sbcl
This is SBCL 1.0.52, an implementation of ANSI Common Lisp.
...
* (load "score4.cl")

T
* (setf a '(+ (1 2) (- 1 (+ 5 6)))
...
* (clone a)

(THE FIXNUM (+ (1 2) (THE FIXNUM (- 1 (THE FIXNUM (+ 5 6))))))

* (macroexpand '(fast + 1 2 THE FIXNUM (- 1 THE FIXNUM (+ 5 6))))

(THE FIXNUM (+ 1 2 THE FIXNUM (THE FIXNUM (- 1 THE FIXNUM (THE FIXNUM (+ 5 6))))))
T

All is well, except for one side-effect: CMUCL works, but no longer compiles the code:

; Error: (during macroexpansion)
; Error in KERNEL:%COERCE-TO-FUNCTION:  the function CLONE is undefined.

Oh well :-)

UPDATE: The compilation failure was addressed and solved in a different SO question.

回答1:

A macro is not just called, but expanded when it is used, so referring to a macro in its own definition can get messy. But you don't have to do that: macros can call regular functions, so you can write a regular function to do the recursive list processing, and then just use that from the macro.

回答2:

Sure. You can write a macro that recursively walks the argument forms and transforms them the way you want, one subform at a time. Since this is slightly more complicated than it sounds, the right way to do it is to use a library for code walking.

Quicklisp includes hu.dwim.walker, which is apparently an improved version of the arnesi code walker.

回答3:

You can definitely write a macro which uses itself in its own expansion. This makes perfect sense, and it is a natural way to write the COND macro, which has a regular, expanding structure due to the arbitrarily long list of cond pairs, that can be expressed by the usual car/cdr or first/rest recursion.

(defmacro new-cond (&rest cond-pairs)
  (cond      ;; you need cond to compile new-cond syntax, LOL!
    ((null cond-pairs) nil)
    ((atom cond-pairs) (error "new-cond: bad syntax!"))
    (t `(if ,(first (first cond-pairs))
           (progn ,@(rest (first cond-pairs)))
           (new-cond ,@(rest cond-pairs))))))


> (macroexpand-1 '(new-cond (1 2) (3 4)))

(IF 1 (PROGN 2) (NEW-COND (3 4)))

This is very analogous to lazy list processing. macroexpand expands just the outer macro, leaving a "promise" object to continue the expansion. That "promise" object is the macro call (NEW-COND (3 4)) at the tail.

Of course the real macro expander will walk the whole form and "force" all these promises (unexpanded macro calls) until no more remain.

I think there are some advantages to this style, such as easy debugging with macroexpand. You get a small expansion. If its recursive nature is obvious, that's a win. If the macro is such that your brain needs to see the whole thing expanded, it's a loss.

Here, I can see that (IF 1 (PROGN 2) (NEW-COND (3 4))) is the correct compile. If 1 is true, evaluate the forms list (2). Otherwise keep going with the other cond pairs. Now we have to verify the one pair case:

> (macroexpand-1 '(new-cond (3 4)))
(IF 3 (PROGN 4) (NEW-COND))

Excellent, and the no-pair case (NEW-COND), by obvious inspection, reduces to nil.