Common Lisp recursive macro expansion

Question

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.

Lattimore

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. – Bureaucrat

Answer 1

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.

Merited

First, I misunderstood the meaning of macro form. HypepSpec explicitly says that it's a form, which first element is a macro name. Second, it turned out that implementation of my choice - SBCL - has it's own code walker. So What I needed was sb-walker:walk-form facility, which gave me desired output: (* 5 (* 4 (* 3 (* 2 (* 1 1))))) – Lattimore

Answer 2

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)))))

Toomey

Answer 3

You can also use sb-cltl2:macroexpand-all

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

Hyperacidity

Answer 4

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)))))

Constriction

What happens if you call one of your dolist variables something like incf, ie the name of a macro? – Fezzan

@DanRobertson good point. Since we recur on the result of the expansion, that shouldn't be a problem, at least for macros. But special operators that expect a variable in the car position of a form (like let) will certainly break. I will edit my answer to address that. – Constriction

The thing I was alluding to when I wrote that is that doing this “properly” requires a code walker. And if you get to a macrolet things are even harder. – Fezzan

@DanRobertson ooh, I get it now... yeah, that was a pretty naïve answer, I’m not very experienced actually – Constriction

The problem is that it is actually impossible to answer in portable Common Lisp as you can’t macroexpand through a defmacro which needs &environment because such values can’t be constructed – Fezzan