Macros That Work

9 pagesThis paper describes a modified form of Kohlbecker's algorithm for reliably hygienic (capture-free) macro expansion in block-structured languages, where macros are source-tos-ource transformations specified using a high-level pattern language. Unlike previous algorithms, the modified algorithm runs in linear instead of quadratic time, copies few constants, does not assume that syntactic keywords ( e.g. if) are reserved words, and allows local (scoped) macros to refer to lexical variables in a referentially transparent manner. Syntactic closures have been advanced as an alternative to hygienic macro expansion. The problem with syntactic closures is that they are inherently low-level and therefore difficult to use correctly, especially when syntactic keywords are not reserved. It is impossible to construct a pattern-based, automatically hygienic macro system on top of syntactic closures because the pattern interpreter must be able to determine the syntactic role of an identifier (in order to close it in the correct syntactic environment) before macro expansion has made that role apparent. may be viewed as a book-keeping technique for deferring such decisions until macro expansion is locally complete. Building on that insight, this paper unifies and extends the competing paradigms of hygienic macro expansion and syntactic closures to obtain an algorithm that combines the benefits of both . Several prototypes of a complete macro system for Scheme have been based on the algorithm presented here