Binding as Sets of Scopes
Notes on a new model of macro expansion for Racket
This is an extended version of a POPL’16 paper. Executable models from the paper are available as model.zip. The POPL’16 artifact provides additional supporting material, including archived implementations of the old and new expanders.
Racket supports a family of languages—
Racket’s representation of syntax builds on a long line of work on macros in Lisp and Scheme (Kohlbecker et al. 1986; Kohlbecker and Wand 1987; Clinger and Rees 1991; Dybvig et al. 1993). A result of that line of work is often referenced by the shorthand of hygienic macro expansion, meaning that macros can both introduce bindings and refer to binding from the macro’s definition context, and macro expansion will not trigger accidental name capture in the way that naive textual expansion would. Although Racket does not restrict language extension to forms that can be expressed as hygienic macros, a representation of syntax fragments that supports hygienic expansion is an essential ingredient to more general, composable language extensions.
Roughly, hygienic macro expansion is desirable for the same reason as lexical scope: both enable local reasoning about binding so that program fragments compose reliably. The analogy suggests specifying hygienic macro expansion as a kind of translation into lexical-scope machinery. In that view, variables must be renamed to match the mechanisms of lexical scope as macro expansion proceeds. A specification of hygiene in terms of renaming accommodates simple binding forms well, but it becomes unwieldy for recursive definition contexts (Flatt et al. 2012, section 3.8), especially for contexts that allow a mixture of macro and non-macro definitions. The renaming approach is also difficult to implement compactly and efficiently in a macro system that supports “hygiene bending” operations, such as datum->syntax, because a history of renamings must be recorded for replay on an arbitrary symbol.
In a new macro expander for Racket, we discard the renaming approach and start with a generalized idea of macro scope, where lexical scope is just a special case of macro scope when applied to a language without macros. Roughly, every binding form and macro expansion creates a scope, and each fragment of syntax acquires a set of scopes that determines binding of identifiers within the fragment. In a language without macros, each scope set is identifiable by a single innermost scope. In a language with macros, identifiers acquire scope sets that overlap in more general ways.
Our experience is that this set-of-scopes model is simpler to use than the old macro expander, especially for macros that work with recursive-definition contexts or create unusual binding patterns. Along similar lines, the expander’s implementation is simpler than the old one based on renaming, and the implementation avoids bugs that were difficult to repair in the old expander. Finally, the new macro expander is able to provide more helpful debugging information when binding resolution fails. All of these benefits reflect the way that scope sets are precise enough for specification but abstract enough to allow high-level reasoning.
This change to the expander’s underlying model of binding can affect the meaning of existing Racket macros. A small amount of incompatibility seems acceptable and even desirable if it enables easier reasoning overall. Drastic incompatibilities would be suspect, however, both because the old expander has proven effective and because large changes to code base would be impractical. Consistent with those aims, purely pattern-based macros work with the new expander the same as with the old one, except for unusual macro patterns within a recursive definition context. More generally, our experiments indicate that the majority of existing Racket macros work unmodified, and other macros can be adapted with reasonable effort.