On this page:
Binding as Sets of Scopes
This document is superceded by a later revision.

Binding as Sets of Scopes
Notes on a new model of macro expansion for Racket

Matthew Flatt

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 particular, variables must be renamed to match the mechanisms of lexical scope as variables interact with macros.

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 that the current 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 current one based on renaming, and the implementation avoids bugs that have proven difficult to repair in the current expander. Finally, the new macro expander is able to provide more helpful debugging information when binding resolution fails.

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 current 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.

    1 Background: Scope and Macros

    2 Scope Sets for Pattern-Based Macros

      2.1 Scope Sets

      2.2 Bindings

      2.3 Recursive Macros and Use-Site Scopes

      2.4 Use-Site Scopes and Macro-Generated Definitions

      2.5 Ambiguous References

    3 Scope Sets for Procedural Macros and Modules

      3.1 Identifier Comparisons with Scope Sets

      3.2 Local Bindings and Syntax Quoting

      3.3 Ensuring Distinct Bindings

      3.4 First-Class Definition Contexts

      3.5 Rename Transformers

      3.6 Modules and Phases

      3.7 The Top Level

      3.8 The Syntax-Function Zoo

    4 Implementation and Experience

      4.1 Initial Compatibility Results

      4.2 Longer-Term Compatibility Considerations

      4.3 Benefits for New Macros

      4.4 Debugging Support

      4.5 Scope Sets for JavaScript

    5 Model

      5.1 Single-Phase Expansion

      5.2 Multi-Phase Expansion

      5.3 Local Expansion

      5.4 First-Class Definition Contexts

    6 Defining Hygiene

    7 Other Related Work

    8 Conclusion

    Acknowledgments

    Bibliography