Beautiful Code [66]
(let ([if (lambda (x y z) "oops")]) (or #f #f))
With the second transformation for or, this expression expands into:
(let ([if (lambda (x y z) "oops")])
(let ([g #f])
(if g g #f)))
where g is a fresh identifier. The value of the expression should be #f, but will actually be "oops" because the locally bound procedure if is used in place of the original if conditional syntax.
Limiting the language by reserving the names of keywords such as let and if would solve this problem for keywords, but it would not solve the problem generally. For instance, the same situation can arise with the introduced reference to the user-defined variable add1 in the following transformation of increment:
(increment x) (set! x (add1 x))
Kohlbecker et al. invented the concept of hygienic macro expansion to solve both kinds of capturing problems, borrowing the term "hygiene" from Barendregt.[#] Barendregt's hygiene condition for the λ-calculus holds that the free variables of one expression substituted into another are assumed not to be captured by bindings in the other, unless such capture is explicitly required. Kohlbecker et al. adapted this into the following hygiene condition for macro expansion:
[#] "Introduction to the lambda calculus," H. P. Barendregt, Nieuw Archief voor Wisenkunde, Vol. 4, No. 2, pp. 337–372, 1984.
Generated identifiers that become binding instances in the completely expanded program must only bind variables that are generated at the same transcription step.
In practice, this requirement forces the expander to rename identifiers as necessary to avoid unintended captures. For example, with the original or transformation:
(or e1 e2) (let ([t e1]) (if t t e2))
the expression:
(let ([t #t]) (or #f t))
expands into the equivalent of:
(let ([t0 #t])
(let ([t1 #f])
(if t1 t1 t0)))
which properly evaluates to #t. Similarly, the expression:
(let ([if (lambda (x y z) "oops")]) (or #f #f))
expands into the equivalent of:
(let ([if0 (lambda (x y z) "oops")])
(let ([t #f])
(if t t #f)))
which properly evaluates to #f.
In essence, hygienic macro expansion implements lexical scoping with respect to the source code, whereas unhygienic expansion implements lexical scoping with respect to the code after expansion.
Hygienic expansion can preserve lexical scope only to the extent that the scope is preserved by the transformations it is told to perform. A transformation can still produce code that apparently violates lexical scoping. This can be illustrated with the following (incorrect) transformation of let:
(let ((x e)) body) (letrec ((x e)) body)
The expression e should appear outside the scope of the binding of the variable x, but in the output it appears inside, due to the semantics of letrec.
The hygienic macro expansion algorithm (KFFD) described by Kohlbecker et al. is both clever and elegant. It works by adding a timestamp to each variable introduced by a macro, and then uses the timestamps to distinguish like-named variables as it renames lexically bound variables. KFFD has some shortcomings that prevent its direct use in practice, however. The most serious are a lack of support for local macro bindings and quadratic overhead resulting from the complete rewrite of each expression as timestamping and renaming are performed.
These shortcomings are addressed by the syntax-rules system, developed by Clinger, Dybvig, Hieb, and Rees for the Revised Report on Scheme.[**] The simple pattern-based nature of the syntax-rules system permits it to be implemented easily and efficiently.[] Unfortunately, it also limits the utility of the mechanism, so that many useful syntactic abstractions are either difficult or impossible to write.
[**] "Revised report on the algorithmic language Scheme," William Clinger and Jonathan Rees, editors, LISP Pointers, Vol. 4, No. 3, pp. 1–55, July–September 1991.
[] "Macros