Common Lisp recursive macro expansion

9
votes

Once upon a time I was playing with macros and came up with this:

(defmacro my-recursive-fact (n)
  (if (= 0 n) '1
    (let ((m (1- n)))
      `(* ,n (my-recursive-fact ,m)))))

And it worked.

CL-USER> (my-recursive-fact 5)
120

So then I thought it could be a nice way to show students an example of recursion, if I expand this macro using macroexpand:

CL-USER> (macroexpand '(my-recursive-fact 5))
(* 5 (MY-RECURSIVE-FACT 4))
T

That is, no difference between macroexpand-1 and macroexpand in this case. I'm sure that I'm missing some crucial point in understanding macroexpand, and HyperSpec says nothing special about recursive macros.

And also I'm still curious to know if there is a way to expand such kind of macro to it's end.

4
macroscommon-lisp
This seems like an inappropriate example for teaching students about macros. You could remove every apostrophe, comma and backtick in that macro, change it to a function, and it would evaluate exactly the same. (And in fact, you should.) I intend no disrespect, and I understand the desire for a simple example, but showing people asinine macros seems like a quick way not only to muddy their understanding of the concepts but to turn them off to the language as a whole. - Mr. Lavalamp

4 Answers

8
votes

MACROEXPAND takes a form and expands it. It does it multiple times until the form is no longer a macro form.

In your example, the top level call to my-recursive-fact is a macro form. The result form with the multiplication in front is not a macro form, since * is not a macro. It is a function. The form has an argument, which is a macro form. But MACROEXPAND does not look at those.

If you want to expand code on all levels, you need to use a code walker. Some Lisps have it in the IDE directly accessible, like Lispworks.

10
votes

Slime has a code-walking slime-macroexpand-all command: http://common-lisp.net/project/slime/doc/html/Macro_002dexpansion.html

This is probably undocumented and/or unsupported, but maybe you can call it from the REPL:

CL-USER> (swank-backend:macroexpand-all '(my-recursive-fact 5))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
2
votes

You can also use sb-cltl2:macroexpand-all

CL-USER> (sb-cltl2:macroexpand-all '(my-recursive-fact 5))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
1
votes

Edit: this will break if there is any variable whose name is the same as a macro's in car position of a form, in a special operator construct. E.g.: (let ((setf 10)) (print setf))

This is pretty old, but if anyone who stumbled upon this question wished there was a somewhat portable way to recursively expand macros:

(defun recursive-macroexpand (form)
  (let ((expansion (macroexpand form)))
    (if (and (listp expansion) (not (null expansion)))
      (cons (car expansion) (mapcar #'recursive-macroexpand (cdr expansion)))
      expansion)))

E.g. (tested in SBCL and CLISP):

(recursive-macroexpand '(my-recursive-fact 5))))

 => (* 5 (* 4 (* 3 (* 2 (* 1 1)))))

An uglier example (the regular macroexpand would leave the second dolist untouched):

(recursive-macroexpand
  '(dolist (x '(0 1))
    (dolist (y '(0 1))
      (format t "decimal: ~a binary: ~a~a~%" (+ (* x 2) (* y 1)) x y))))

 => (block nil
     (let* ((#:list-8386 '(0 1)) (x nil)) nil
      (tagbody #:loop-8387 (if (endp #:list-8386) (go #:end-8388)) (setq x (car #:list-8386))
       (block nil
        (let* ((#:list-8389 '(0 1)) (y nil)) nil
         (tagbody #:loop-8390 (if (endp #:list-8389) (go #:end-8391)) (setq y (car #:list-8389)) (format t "decimal: ~a binary: ~a~a~%" (+ (* x 2) (* y 1)) x y)
          (setq #:list-8389 (cdr #:list-8389)) (go #:loop-8390) #:end-8391 (return-from nil (progn nil)))))
       (setq #:list-8386 (cdr #:list-8386)) (go #:loop-8387) #:end-8388 (return-from nil (progn nil)))))