2

I'm writing a recursive Lisp macro taking a number n and evaluating the body n times (an exercise from ANSI Lisp). I've tried two ways of doing this -- having the macro call itself in its expansion, and having the macro expand into a local recursive function. Neither works as I want it to.

Here's the first one -- it has a stack overflow, but when I look at its expansion using macroexpand-1 it seems fine to me.

(defmacro n-times (n &rest body)
  (let ((i (gensym)))
    `(let ((,i ,n))
     (if (zerop ,i) nil
         (progn
           ,@body
           (n-times (- ,i 1) ,@body))))))

Here's the second one -- it makes an error, "undefined function #xxxx called with arguments (z)" where #xxxx is the name of the gensym and z is 1 less than the number I call it with. I think there's a problem with the way I use gensyms and flet together, but I'm not sure how to do this correctly.

(defmacro n-times (n &rest body)
  (let ((g (gensym)))
    `(flet ((,g (x)
              (if (zerop x) nil
                  (progn
                    ,@body
                    (,g (- x 1))))))
       (,g ,n))))
Improve this question

2 Answers 2

Reset to default
9

To answer your first question, you have a recursive macro expansion that never stops recursing. The presence of the if doesn't stop the recursive macro expansion, since macro expansion happens at compile-time and your if happens at run-time.

To answer your second question, you can't use flet to specify recursive functions, you have to use labels instead.

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

4 Comments

Thanks, that made it work! Why can't you use flet to specify recursive functions?
flet makes the bindings visible inside the body only. labels makes the bindings visible inside the binding definitions as well.
Got it. Would the first method be OK if I took the if out of the backquote to test (zerop n) at compile-time?
@lightlike Yes---that's basically what Rainer's answer is---but like Rainer said, your macro argument must be a number literal, and not some expression like n or (+ 3 4) (which the macro will see as a symbol and a list, respectively; remember macros are expanded at compile-time and expressions are evaluated at run-time).
7

Since macro expansion in Common Lisp happens kind of before runtime, this is slightly tricky.

Remember, the macro sees source code. This means:

  • the number n must be passed as a number, not a variable, when you use the macro. Thus at macro expansion time the number is known. For such a macro, I would check that in the macro - otherwise you always be tempted to write something like (let ((n 10)) (n-times n ...)) - which won't work.

  • the macro needs to compute the recursive iteration. Thus the logic is in the macro, and not in the generated code. Each macro needs to generate code, which is one step simpler at macro expansion time - until the basic case is reached.

Improve this answer

2 Comments

OK, thank you. Why isn't it OK to call a macro that's supposed to take a number with a variable containing the number? Also, is the first method (having the macro call itself in its expansion) 'wrong' compared to the second method (having the macro expand into the recursive function)?
There's a nice section in Let Over Lambda that covers Rainer's points in this post in more detail: letoverlambda.com/index.cl/guest/chap5.html#sec_5

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.