Tuesday, March 15, 2005

Lazy Macro Expansion

Macro expansion could be called "lazy" when macro invocations are expanded without expanding their arguments, analogous to call-by-name or call-by-need lambda calculus. In CBN, arbitrary expressions can be passed as arguments to functions, not just values, which means that it isn't necessary to evaluate an argument to a value before the function can be invoked. Similarly with macros: if we define values in macro expansion as expressions that have no macro invocations left, then a strict, or "expand-by-value" macro semantics would be forced to fully expand a subexpression in a macro invocation before expanding the macro. A non-strict macro semantics passes subexpressions to a macro untouched.

We can demonstrate the non-strictness property in the usual way:
(define-syntax Ω
(syntax-rules ()
[(_) (Ω)]))
(define-syntax constant-3
(syntax-rules ()
[(_ exp) 3]))
(constant-3 (Ω))
=>
3

This non-strictness is critical to Scheme in a couple of ways--and the reason is always that we need to see the original syntactic structure of an expression. The first case is for uses of quote: if (foo exp) expands to (quote exp), then (foo (or a b)) should expand to (quote (or a b)), not (quote (let ((tmp a)) (if tmp tmp b))). The second is for macro-defining macros. If a macro expands into a definition of a new macro that needs to pattern match on one of the original macro's arguments, then new macro should see that argument as it originally appeared, not some expansion thereof.

I believe that the latter would not be an issue in so-called generative macro systems, where macros are not allow to deconstruct their argument expressions.

No comments: