Re: Macros -- what's happening?

[William Clinger <will@skinner.cs.uoregon.edu>]

 1. What turned out to be wrong with syntactic closures?

When Chris Hanson constructed a pattern-based macro language
on top of syntactic closures, he found that the pattern
interpreter had to be able to determine the syntactic role
of an identifier (to know whether to close over it) before
macro expansion had made that role apparent.

 2. What the "modified Kohlbecker" repainting algorithm is?

The modified Kohlbecker algorithm is a linear-time algorithm
similar to Kohlbecker's original algorithm for hygienic macro
expansion.  (Kohlbecker's algorithm is quadratic-time, mainly
because it performs a naive expansion and then scans the
expanded code to find and paint the newly introduced identifiers.
The modified algorithm finds and paints the newly introduced
identifiers as they are introduced.)

You can think of the modified Kohlbecker algorithm as a
book-keeping technique for deferring decisions that involve
the syntactic roles of identifiers.

The algorithm works by allocating a new color for every macro
expansion, and by painting every new identifier introduced by
that macro expansion with the new color.  It also keeps track
of the bindings between the newly painted identifiers and the
unpainted identifiers that they will eventually be seen to
refer to (provided no intervening bindings surface to break
the connection).  As the algorithm proceeds by recursive
descent, it will eventually scan each identifier after macro
expansion is (locally) complete.  At that time it uses the
environments that it has constructed to replace the identifier
by the identifier that it refers to.  The ultimate result is a
completely alpha-converted and macro-expanded source program
with no inadvertant captures of bound variables.

Will