More code walking

One of the tricky aspects to understanding and writing a code-walker is knowing how and when to expand macros.

When you are walking code, it's necessary to keep track of what is in the current lexical environment so that you know when a symbol names a function or a macro. If it names a macro, you have to call the necessary macro function.

In order to call the macro function, you have to evaluate it when you come to it. Ignoring defmacro and define-symbol-macro for the time being, you still have a bit of a problem with macrolet and symbol-macrolet.

The trouble lies in the evaluation of the macro function. To illustrate, here's an example.

(macrolet ((foo () `(print 1)))
  (foo)
  (macrolet ((bar () (foo) `(print 2)))
    (bar)))

When you walk the macro definition for foo, you have to construct the macro function for it so that it is available to the enclosed body of code. A simple way to do this is to actually call eval on the body of the macro definition, say, by creating a defmacro form and passing it to eval.

Say you do this and keep processing forms. When you get to the (foo) form, you know that foo is a macro so you expand it and substitute (foo) with (print 1). No problem there.

Now you get to the definition for the local macro bar. You still have to walk the macro definition so that you can expand the foo macro. The HyperSpec says that with macrolet, it is undefined if the body of the macro references any local variable or function bindings, but macros (local or global) must be expanded.

When I tried this code out with the arnesi code-walker under ACL and SBCL, it failed. The error it gives me is that it is trying to call a function foo. Using some traces, I found that when the macro function for bar is being defined, the lexical environment is empty. Thus, the macro function produced considers foo to be a function.

Oddly enough, ACL's code-walker (see the symbol excl::walk) gave me the same error! I don't know why yet, but it evaluates and compiles it just fine. SBCL didn't have a problem with it.

Goes to show you that writing these code walkers is tricky. And I didn't even mention anything about environment objects...