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

Posted 2009-07-29 00:23:00 GMT

3 watching live

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.

hi,

I found (probably) a bug in macroexpand-dammit and I ported another version in github. Please take a look.

https://github.com/guicho271828/macroexpand-dammit

Attached a test case in test.lisp.

https://github.com/guicho271828/macroexpand-dammit/blob/master/test.lisp

The first test case passes in both the original version and mine. In the second case however, `eval`, `m-list` cause a problem and the test does not pass.

When `e` finds a macrolet in the given form, it wraps the body of macrolet with `m-list`, but it doesn't macroexpand the body. so the *env* given to macroexpand-dammit is ignored here once.

The code generated by `e` will be passed to `eval` afterward, but since `eval` does not recognize the environment, *env* is ignored again during the expantion of the body of `m-list`.

This behavior is not important under the light use because the remaining unexpanded code will be expanded again outside of macroexpand-dammit. However, if someone, like me, try to signal a condition by expanding the code within the dynamic-extent of macro definition or macrolet bindings, then it becomes a problem.

I spent about whole-one day for this issue, and struggled to understand the behavior of dynamic variable *env*, and finally reached a simple but dirty answer which ascertains that the body is expanded.

waiting for a positive feedback! :)

Posted 2013-05-12 09:24:42 GMT by Anonymous from 115.165.95.14

Post a comment