Source Transformation for Fun and Profit (by alaric)
Hygiene
Now, of course, the meta construct does nothing to give you hygiene. The two ways of implementing macros I defined above both work like Common Lisp macros; the macro function itself inherits the lexical environment it was defined in, but anything it outputs ends up in the lexical environment of the macro invocation.
Certainly, you could implement a hygienic macro system using a whole-program transformation, as I suggested; while you're partially evaluating, you need to build up lexical environments as you walk the tree anyway, in order to replace symbols with their values. So you could define a hygienic macro expansion system, using this extra information.
But while thinking about this, it struck me that it sucked how much the macro expander partial evaluator was similar to the one that implements meta itself. So much duplication of effort. What if, I thought, we had a generic code walker system that recursed over a source code tree, collecting lexical bindings on the way down and reducing constructs on the way up, but with the handling of any particular type of syntax overrideable? One could then define the macro expander in terms of this, by just overriding the handling of applications. If we hooked into the process just after the symbol at the head of the application had been resolved, and the resulting application matched the pattern [apply: *macro* to: ((body env) ...)]], where *macro* is the tag value bound to the symbol macro:body: - note that, like Scheme, we try and avoid having "special symbols" like lambda and if; instead, these symbols, in the toplevel environment, are bound to special values that trigger the behaviour, so they can be rebound and renamed at will. Such spoor of an attempt to create a macro could then be rewritten as [make-macro [fun: (body env) body: ...]] and partial evaluation recursively continued on that (make-macro just being a function that wraps a closure to make it into a macro object). Otherwise, if the application is of a macro object m to argument list args, we can replace it with [meta [apply: [get-macro-func m] to: ([' args] env)]], where env is the lexical environment the code walker has accumulated thus far. Our macro functions, passed explicit bodies and environments, can then function like syntactic-closure macros in Scheme, with syntactic closures being generated form a form and an environment by partially evaluating the form in that environvment to resolve all symbols to their values, and/or a bit of renaming.
Most, if not all, full-program translation functions that need to worry about lexical scoping could (and probably should) just hook into the partial evaluation process like so. This will enable them to be hygienic in themselves, as far as they wish to be, and will enable them to provide features like hygienic macro expansion, without too much extra effort.
I'll have to think on this a bit more, though. Particularly the fine details of the partial evaluation system, and where it should allow hooking, and how.
Also, I wonder in hindsight, could it be applied to Scheme? Although Scheme allows mutation of bindings, it doesn't allow aliasing of them, so the partial evaluator could perhaps statically detect bindings that are never mutated and treat them as constants. Then it'd just have to be careful not to try and partially evaluate built-in functions with side effects, such as display. Might be worth doing. I'll have to think about it.
Thu 19th Jul 2007 1:39 pm 
Subscribe