John Fremlin's blog: Portable Common Lisp code walking with macroexpand-dammit

Nowadays Common Lisp is rather a niche language, so there is small interest in best practices. This is a shame because the language standard was quite carefully thought out in many areas. However, in the late eighties and early nineties lisp was widely adopted among AI researchers and there was more interest in its intricacies. I repeatedly came across a set of papers from this time by Richard C. Waters, including Macroexpand-All: An Example of a Simple Lisp Code Walker (1993).

As far as I know all existing portable code walkers for Common Lisp are similar to this one and have a small non-portable kernel called augment-environment, or something like that, which actually does the hard work of deciding whether or not a new lexical definition shadows another one. This means that the code walker described by Waters cannot operate on modern Lisp environments (unless this small kernel is adapted to call into the host Lisp's environment augmenter).

The requirement for porting is obviously rather undesirable. Why should it be so hard to write a code walker that is portable across standard-conformant Common Lisp implementations? I guess Waters was writing at a time when full ANSI compliance was still a little sketchy. Maybe I was suffering a little from Scheme envy, but I became curious about the challenge.

Now my first idea was to create a structure describing the lexical environment as witnessed by the code walker, which would only fall back to the host's treatment of a binding if the binding was unknown to the walker. This would work for most simple code.

However, macros themselves can control the order of macroexpansion by explicitly calling macroexpand or macroexpand-1. They would do so without knowledge of the walker's portable environment and therefore get incorrect results. To solve this, one might think that it would suffice to override the *macroexpand-hook*. That, however, opens up a new subtlety, as the hook would have to deal with the fact that a macro might explicitly macroexpand a form that itself explicitly macroexpanded another form in a new augmented environment. It should be possible, but would be a little fiddly.

Then it occurred to me that, by analogy with the trick of implementing the functionality of compiler-let with macrolet, it should be possible to get the host environment to do all the expansion by itself, without meddling with the *macroexpand-hook*. In essence, the code would be transformed to return a quoted, macroexpanded version of itself. The work is much simpler than building up a portable representation of the lexical environment, and the result is equally (or even more) powerful.

I also wanted to strip out all the irritating macrolets that tend to clutter up the output of most non-portable macroexpands and to do compiler-macroexpansion. Thus macroexpand-dammit was born — the first really portable macroexpand-all for Common Lisp? I'd be very interested to hear about others.

For example,

(macroexpand-dammit:macroexpand-dammit 
 '(symbol-macrolet ((m (random))) 
   (macrolet ((m (m &optional; (b m)) `(+ ,b ,m))) 
     (defun m (n) (m m n)))))
 
=> (DEFUN M (N) (+ N (RANDOM)))

UPDATE 20090809 — fixed a few annoying compiler warnings by eliding more details of the flets and labels emitted in the expansion that generates the quoted result.

UPDATE 20100301 — fixed the utterly broken macrolets as reported by mathrick, and added ccl:compiler-let for Clozure CL.