Lisp: can a macro be recursive?

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.

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.

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.