algorithm is essentially a lazy variant of the KFFD algorithm that
operates on an abstract representation of the input expression rather
than on the traditional s-expression representation. The abstract
representation encapsulates both a representation of an input form and a
wrap that enables the algorithm to determine the
scope of all identifiers within the form. The wrap consists of
Marks are like KFFD timestamps and are added to the portions of a macro's output that are introduced by the macro.
Substitutions map identifiers to bindings with the help of a compile-time environment.
Substitutions are created whenever a binding form, such as
lambda, is encountered, and they are added to
the wraps of the syntax objects representing the forms within the scope of
the binding form's bindings. A substitution applies to an identifier
only if the identifier has the same name and marks as the substituted
Expansion operates in a recursive, top-down fashion. As the expander encounters a macro call, it invokes the associated transformer on the form, marking it first with a fresh mark and then marking it again with the same mark. Like marks cancel, so only the introduced portions of the macro's output—i.e., those portions not simply copied from the input to the output—remain marked.
When a core form is encountered, a core form in the output language of the expander (in our case, the traditional s-expression representation) ...