9

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)

Improve this question

5 Answers 5

Reset to default
14

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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.

Improve this answer

1 Comment

Thanks, exactly the kind of info I was looking for
2

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.

Improve this answer

Comments

2

To the answer of Kilan I'd add, that macroexpand doesn't have to produce a full expansion of all macros in your form, until there's no macro left :) If you look at Hyperspec, you'll see, that it evaluates the whole form until it's not a macro (in your case it stops at if). And during compilation all the macros are expanded, as if macroexpand was applied to each element of the source tree, not only to its root.

Improve this answer

Comments

2

Here's an implementation that does work:

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

It is possible to write a recursive macro, but (as was mentioned), the expansion must be able to hit the base case at compile time. So the values of all arguments passed to the macro must be known at compile time.

(sum-int-seq 5)

Works, but

(sum-int-seq n)

Does not.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.