Lisp: can a macro be recursive?

Question

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.

Answer 1

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.

Secondly, a macro can also invoke itself in its own code. So, for instance, if we are Lisp implementors trying to define cond, there is a way we can actually get away with:

(defmacro 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))))))

How can cond be used in a macro which is defining it? The answer is bootstrapping. The cond being expanded in the macro is an existing cond that we somehow already have. This new definition expands just fine with that existing cond, and then replaces it.

This process can be repeated. We can evaluate the above defmacro form again and again; the cond which the previous evaluation has just installed is used for expanding the cond which occurs in the new evaluation.

If we are boostrapping one Lisp compiler with an existing one, we may be able to start this process using the host Lisp's cond, so we never require a second, boostrapping version of the cond macro that doesn't rely on cond.

Note that for this to work, the body of our replacement cond macro has to be fully expanded before being installed as the new definition of cond. This cannot work if the bodies of macro definitions are left unexpanded; then it becomes a recursive call. In other words, this isn't recursion. Recursion cannot work; a macro cannot need itself to expand itself. At best it can need an existing macro which is not itself, but which happens to have the same name.

Answer 2

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.