How do recursive macro definitions get evaluated

Question

This recursive definition of a macro does what it should (sum integers from 1 to n):

(defmacro sum-int-seq (n)
  `(cond
     ((equal 0 ,n) 0)
     (t (+ ,n (sum-int-seq (- ,n 1))))))

For example (sum-int-seq 5) gives 15.

But why does it work? When the macro gets expanded i get this:

(macroexpand '(sum-int-seq 5))
(IF (EQUAL 0 5) 0 (+ 5 (SUM-INT-SEQ (- 5 1))))

But because sum-int-seq is a macro the macro evaluation should become an infinite loop. Does the compiler create a recursive function instead? If this definition creates a recursive function is there any way to define macros recursively?

(This is a silly example for the sake of brevity, a function would of course work better for this)

Answer 1

Your example does not work.

It may work in an interpreter. But with a compiler you'll see an endless loop during compilation.

CL-USER 23 > (defun test (foo)
                (sum-int-seq 5))
TEST

Let's use the LispWorks interpreter:

CL-USER 24 > (test :foo)
15

Let's try to compile the function:

CL-USER 25 > (compile 'test)

Stack overflow (stack size 15997).
  1 (continue) Extend stack by 50%.
  2 Extend stack by 300%.
  3 (abort) Return to level 0.
  4 Return to top loop level 0.

Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.

So, now the next question: why does it work in the interpreter, but the compiler can't compile it?

Okay, I'll explain it.

Let's look at the interpreter first.

• it sees (sum-int-seq 5).
• it macroexpands it to (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• it then evaluates above form. It determines that it needs to compute (+ 5 (SUM-INT-SEQ (- 5 1))). For that it needs to macroexpand (SUM-INT-SEQ (- 5 1)).
• eventually it will expand into something like (cond ((EQUAL 0 (- (- (- (- (- 5 1) 1) 1) 1) 1)) 0) .... Which then will return 0 and the computation can use this result and add the other terms to it.

The interpreter takes the code, evaluates what it can and macroexpands if necessary. The generated code is then evaluated or macroexpanded. And so on.

Now let's look at the compiler.

• it sees (sum-int-seq 5) and macroexpands it into (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• now the macroexpansion will be done on the subforms, eventually.
• the compiler will macroexpand (SUM-INT-SEQ (- 5 1)). note that the code never gets evaluated, only expanded.
• the compiler will macroexpand (SUM-INT-SEQ (- (- 5 1) 1)) and so forth. finally you'll see a stack overflow.

The compiler walks (recursively compiles / expands) the code. It may not execute the code (unless it does optimizations or a macro actually evaluates it explicitly).

For a recursive macro you'll need to actually count down. If you eval inside the macro, then something like (sum-int-seq 5) can made work. But for (defun foo (n) (sum-int-seq n)) this is hopeless, since the compiler does not know what the value of n is.

Answer 2

One other thing to add: in your example, the occurrence of sum-int-seq inside the macro is inside a quoted expression, so it doesn't get expanded when the macro is evaluated. It's just data until the macro is called. And since it is nested inside a cond, at run-time the inner macro only gets called when the condition is true, same as in a regular function.

Answer 3

Expanding a macro generates Lisp code that is then evaluated. Calling a function diverts the execution flow to a copy of pre-existing lisp code which is then run. Other than that, the two are pretty similar, and recursion works in the same way. In particular, macro expansion stops for the same reason that a properly written recursive function stops: because there is a termination condition,and the transformation between one call and the next has been written so that the this condition is actually reached. If it weren't reached, the macro expansion would enter a loop, just like an improperly written recursive function.