This paper describes a modified form of Kohlbecker's algo­rithm for reliably hygienic (capture-free) macro expansion in block-structured languages, where macros are source to ­source transformations specified using a. high-level pattern language. Unlike previous algorithms, the modified algo­rithm 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 syn­tactic 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.

Kolilbecker's algorithm may he viewed as a book-keeping technique for deferring such decisions until macro expansion is locally complete. Building on that insight, this paper uni­fies and extends the competing paradigms of hygienic macro expansion and syntactic closures to obtain an algorithm that combines the benefits 0f both.

Several prototypes of a complete macro system for Scheme have been based on the algorithm presented here.