Beautiful Code [65]
[*]The C Programming Language, Second Edition, Brian W. Kernighan and Dennis M. Ritchie, Prentice Hall, 1988.
Some patterns are less common but may occur frequently in a certain class of programs, or perhaps just within a single program. These patterns may not even be anticipated by a language's designers, who in any case would typically choose not to incorporate syntactic constructs to handle such patterns in the language core.
Yet, recognizing that such patterns do arise and that special-purpose syntactic constructs can make programs both simpler and easier to read, language designers sometimes include a mechanism for syntactic abstraction, such as C's preprocessor macros or Common Lisp[]macros. When such facilities are absent or are inadequate for a specific purpose, an external tool, such as the m4 macro expander,[] may be brought to bear.
[]Common Lisp: The Language, Second Edition, Guy L. Steele Jr., Digital Press, 1990.
[]The M4 Macro Processor, Brian W. Kernighan and Dennis M. Ritchie, 1979.
Syntactic abstraction facilities differ in several significant ways. C's preprocessor macros are essentially token-based, allowing the replacement of a macro call with a sequence of tokens; text passed to the macro call is substituted for the macro's formal parameters, if any. Lisp macros are expression-based, allowing the replacement of a single expression with another expression, computed in Lisp itself and based on the subforms of the macro call, if any.
In both cases, identifiers appearing within a macro-call subform are scoped where they appear in the output, rather than where they appear in the input, possibly leading to unintended capture of a variable reference by a variable binding.
For example, consider the simple transformation of Scheme's or form[§] into let and if in the following example:
[§] "Revised report on the algorithmic language Scheme," Richard Kelsey, William Clinger, and Jonathan Rees, editors, Higher-Order and Symbolic Computation, Vol. 11, No. 1, pp. 7–105, 1998. Also appeared in ACM SIGPLAN Notices, Vol. 33, No. 9, September 1998.
(or e1 e2) (let ([t e1]) (if t t e2))
* * *
Note: Readers unfamiliar with Scheme might want to read the first few chapters of The Scheme Programming Language, Third Edition (R. Kent Dybvig, MIT Press), which is available online at http://www.scheme.com/tspl3.
* * *
An or form must return the value of its first subform, if it evaluates to a true (any non-false) value. The let expression is used to name this value so that it is not computed twice.
The previous transformation works fine in most cases, but it breaks down if the identifier t appears free in e2 (i.e., outside of any binding for t in e2), as in the following expression:
(let ([t #t]) (or #f t))
This should evaluate to the true value #t. With the simple transformation of or specified previously, however, the expression expands to:
(let ([t #t])
(let ([t #f])
(if t t t)))
which evaluates to the false value #f.
Once seen, this problem is easily addressed by using a generated identifier for the introduced binding:
(or e1 e2) (let ([g e1]) (if g g e2))
where g is a generated (fresh) identifier.
As Kohlbecker, Friedman, Felleisen, and Duba observe in their seminal paper on hygienic macro expansion[||]variable capture problems like this are insidious, because a transformation may work correctly for a large body of code only to fail sometime later in a way that may be difficult to debug.
[||] "Hygienic macro expansion," Eugene Kohlbecker, Daniel P. Friedman, Matthias Felleisen, and Bruce Duba, Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, pp. 151–161, 1986.
While unintended captures caused by introduced identifier bindings can always be solved by using generated identifiers, no such simple solution is available for introduced identifier references,