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

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 the variables interact with macros.

A specification of hygiene in terms of renaming accommodates simple binding forms well enough, 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. The resulting implementation is simpler than one based on renaming, and it avoids bugs that have proven too difficult to repair in the current macro expander.The bugs manifest most commonly as failures of submodules within typed/racket modules.

The change to the expander’s underlying model of binding potentially affects existing Racket macros, since the expander exposes many hygiene-bending operations. All purely pattern-based macros work as before,Or so I think. I’m hopeful that the claim can be formulated and proved as a theorem. however, and experiments indicate that the vast majority of other macros continue to work, too.

1 Macro Scope via Scope Sets

Lexical scope corresponds to scope sets that are constrained to a particular shape: For any given set, there’s a single scope s that implies all the others (i.e., the ones around s in the program). As a result, s by itself (along with a symbolic name) is enough information to identify a binding. We normally describe lexical scope in terms of the closest such s for some notion of “closest.” Given scope sets instead of individual scopes, we can define “closest” as the largest relevant set.

More generally, we can define binding based on subsets: A reference’s binding is found as one whose set of scopes is a subset of the reference’s own scopes (in addition to having the same symbolic name). The advantage of using sets of scopes is that macro expansion creates scope sets that overlap in more general ways; there’s not always a s that implies all the others. Absent a determining s, we can’t identify a binding by a single scope, but we can identify it by a set of scopes.

If arbitrary sets of scopes are possible, then two different bindings might have overlapping scopes, neither might be a subset of the other, and both might be subsets of a particular reference’s scope set. In that case, the reference is ambiguous.

Ambiguous bindings can happen only if the macro system provides unusual operations. They will not show up with syntax-rules, and they will not show up with just syntax-case and syntax unless state or compile-time binding is used to communicate between macro invocations.

Our notion of “scope” is related to and insprired by the concept of “mark” in other descriptions of Scheme macros (Dybvig et al. 1993; Flatt et al. 2012).

2 Bindings

A free-identifier=? comparison on identifiers checks whether the two identifiers have the same binding. A bound-identifier=? comparison checks that two identifiers have exactly the same scope sets, independent of the binding table.

Note that (bound-identifier=? x y) does not completely answer the question “would x bind y?”A #t result answers that question in the affirmative, but x might bind y even if the result is #f. The same is currently true in definition contexts for Racket and Chez Scheme, which (like the set-of-scopes macro system) print #f but produce 1 for this example:

(let ()

(define-syntax (m stx)

(syntax-case stx ()

[(_ a b)

(begin

(printf "~s\n" (bound-identifier=? #'a #'b))

#'(begin

(define a 1)

b))]))

(define-syntax n

(syntax-rules ()

[(_ id) (m id x)]))

(n x))

In practice, bound-identifier=? is used to check whether two identifiers would conflict as bindings in the same context. It continues to work for that purpose with set-of-scopes binding.

The binding table can grow forever, but when a particular scope becomes unreachable (i.e., when no reachable syntax object includes a reference to the scope), then any mapping that includes the scope becomes unreachable. This weak mapping can be approximated by attaching the mapping to the scope, instead of using an actual global table. Any scope in a scope set can house the binding, since the binding can only be referenced using all of the scopes in the set. Attaching to the most recently allocated scope is a good heuristic, because the most recent scope is likely to be maximally distinguishing and have the shortest lifetime.

When a syntax object is serialized, the serialization must pull along the fragment of the binding table that is relevant for the syntax object’s scopes. Again, that extraction happens more or less automatically when the binding-table entries are implemented by attaching them to scopes, but an explicit “garbage collection” of the scopes is useful in practice to make serialized syntax more compact. Deserializing a syntax object creates fresh representations for every serialized scope, but preserving sharing ensures that binding relationships are preserved among identifiers in the syntax object—or more generally, among syntax objects within a module.

3 Macros, Scopes, and Definitions

The expansion of a macro use creates two new scopes: one scope for forms that are introduced by the macro, and one scope for forms that are present at the use site. The need for a use-site scope may not be apparent, particularly for readers who are familiar with existing, mark-based approaches to macros.

To support macros that expand to definitions of given identifiers, a definition context must keep track of scopes created for macro uses, and it must remove those scopes from identifiers that end up in binding positions. In the define-identity and define-five examples, the use-site scope is removed from the binding identifiers x and f, so they are treated the same as if their definitions appeared directly in the source.

As an optimization, a use-site scope is needed only when a macro is expanded in a definition context where the macro’s definition is in the same definition context. (Otherwise, the use is in a more nested scope, and thus already distinguished from introduced identifiers.) That combination happens regularly in a module body, but it is much less common than macro uses generally (since almost every form in a Racket source program is a macro use). This “optimization” is visible if the macro system provides certain operations, such as forcing the expansion of a sub-form, but it is invisible to pattern-based macros and to typical syntax-case macros.

To adapt to the use-site scopes added by a set-of-scopes expander, Racket’s syntax-local-introduce must flip both the macro-introduction scope and the use-site scope (if any) of the current macro expansion.

4 Local Bindings and Syntax Quoting

It’s tempting to think that the compile-time let should introduce a phase-specific scope that applies only for compile-time references, in which case it won’t affect x as a run-time reference. That adjustment doesn’t solve the problem in general, since a macro can generate compile-time bindings and references just as well as run-time bindings and references.

A solution is for the expansion of quote-syntax to discard certain scopes on its content. The discarded scopes are those from binding forms that enclosed the quote-syntax form up to a phase crossing or module top-level, as well as any use-site scopes recorded for macro invocations within those binding forms. In the case of a quote-syntax form within a macro binding’s right-hand side, those scopes cover all of the scopes introduced on the right-hand side of the macro binding.

Note: Racket’s macro system matches Dybvig et al. (1993), where both free-identifier=? and bound-identifier=? produce #f for the above arguments, and bound-identifier=? always implies free-identifier=?. The current psyntax implementation, as used by Chez Scheme and other implementations and as consistent with Adams (2015), produces #t and #f for free-identifier=? and bound-identifier=?, respectively; as the example illustrates, bound-identifier=? does not imply free-identifier=?. The set-of-scopes system produces #t and #t for free-identifier=? and bound-identifier=?, respectively, and bound-identifier=? always implies free-identifier=?.

If quote-syntax did not prune scopes, then not only would the result above be #f, it would also be #f with (let ([y 1]) #'x) instead of (let ([x 1]) #'x). That similarity reflects the switch to attaching identifier-independent scopes to identifiers instead of attaching identifier-specific renamings.

Arguably, the issue here is the way that pieces of syntax from different local scopes are placed into the same result syntax object, with the expectation that all the pieces are treated the same way. In other words, Racket programmers have gotten used to an unusual variant of quote-syntax, and most macros could be written just as well with a non-pruning variant. Then again, the pruning variant of quote-syntax tends to discard information about local bindings that is usually unwanted but preserved by the current quote-syntax.

There’s precedent for a variant of syntax-case that does not support assembling pieces as in the example. An early version of van Tonder’s macro expander (van Tonder 2007) had that property as a result of making the evaluation of syntax generate a fresh context.

5 First-Class Definition Contexts

A Racket macro can implement a new kind of definition context, including one that mixes variable and macro definitions, by allocating a first-class (at compilation time) definition context. The syntax-local-make-definition-context function creates such contexts. A macro can force expansion of forms in the definition context, it can add variable bindings to the definition context, and it can add compile-time bindings and values that are referenced by further macro expansion within the definition context.

To a first approximation, a first-class definition context corresponds to a scope that is added to any form expanded within the definition context and that houses the definition context’s bindings. A definition context also has a compile-time environment frame (extending the context of the macro use) to house the mapping of bindings to variables and compile-time values.

Even if a macro does not create a first-class definition context, some care is needed if a macro forces the expansion of subforms and moves pieces of the result into binding positions. Such a macro probably should not use syntax-local-identifier-as-binding, but it should first ensure that the macro use is in an expression context before forcing any subform expansions. Otherwise, the subform expansions could interact in unexpected ways with the use-site scopes of an enclosing definition context.

Use-site scopes associated with a first-class definition context are not stored directly in the compile-time environment frame for the definition context. Instead, they are stored in the closest frame that is not for a first-class definition context, so that the scopes are still tracked when the definition context is discarded (when the macro returns, typically). The scope for the definition context itself is similarly recorded in the closest such frame, so that quote-syntax can remove it, just like other binding scopes.

6 Rename Transformers

Racket’s macro API includes support for binding aliases through rename transformers. A compile-time binding to the result of make-rename-transformer is similar to a binding to a macro transformer that replaces the binding’s identifier with the aliased identifier. In addition, however, binding to a rename transformer causes free-identifier=? to report #t for the original identifier and its alias.

With set-of-scopes binding, a binding alias is supported through an extension of the binding table. The mapping from a ⟨symbol, scope set⟩ pair is to a ⟨binding, maybe-aliased⟩ pair, where an maybe-aliased is either empty or another identifier (i.e., a symbol and scope set) to which the mapped identifier should be considered free-identifier=?. When a transformer-binding form such as define-syntax or letrec-syntax detects that the value to be installed for a binding as a rename transformer, it updates the binding table to register the identifier within the transformer as an optional-alias.

The implementation of free-identifier=? must follow alias chains. Cycles are possible, and they cause the aliased identifier to be treated as unbound.

7 Modules and Phases

The module form creates a new scope for its body. More precisely, a module form creates two new scopes: one that roughly reflects “outside edge” of the module, covering everything that is originally in the module body, and one for the “inside edge” of the module, covering everything that appears in the module through macro expansion for forms in the module’s top level. The “inside edge” scope is the one that’s like any definition context, while the “outside edge” scope distinguishes identifiers that had no scopes before being introduced through macro expansion.

A (module* name #f ....) submodule form, where #f indicates that the enclosing module’s bindings should be visible, creates an additional scope in the obvious way. For other module* and module submodule forms, the macro expander prevents access to the enclosing module’s bindings by removing the two scopes of the enclosing module.

Among the possibilities for distinguishing phases, having per-phase sets of scopes on an identifier makes the phase-shifting operation most natural. A local binding or macro expansion can add scopes at all phases, while module adds a distinct inside-edge scope to every phase (and the same outside-edge scope to all phases); since every binding within a module is forced to have that module’s phase-specific inside-edge scopes, bindings at different scopes will be appropriately distinguished.

Racket constrains operations that inspect and adjust scopes on syntax objects to those that add, remove, or flip sets of scopes relative to some other syntax object. As a result, all of the phase-specific scopes for a modules inside edge are added to or removed from a syntax object together.

8 The Top Level

A namespace in Racket is a top-level evaluation context. Each call to eval uses a particular namespace (either the current namespace or one supplied to eval), and each read–eval–print loop works in a particular namespace. Namespaces are first-class values in Racket. A namespace can be created as fresh, or it can be extracted from a module instantiation to simulate further evaluation in the module’s body.

As the connection to modules may suggest, a top-level namespace corresponds to a pair of scopes in the same way that a module has a scope. Each top-level namespace has the same outside-edge scope, but a distinct inside-edge scope where bindings reside.

The interactive and incremental nature of a top-level context poses certain semantic challenges when macro and variable definitions and re-definitions are allowed. For example, a reference to an unbound identifier within a function cannot be rejected out-of-hand, because it might be defined later within the namespace before the function is called. Similarly, a reference might be resolved as a variable when a function is created, but a later definition could change the identifier’s binding to a macro, so the function must either continue to refer to a variable or be somehow reinterpreted to have a macro use. These challenges are compounded when macros expand to a mixture of variable and macro definitions. Overall, the top level is hopeless: it cannot provide a treatment of binding that is as consistent as module while also performing its job as an interactive, exploratory evaluation context. In Racket, we accept top-level compromises and put all “real” code in modules.

Fortunately, top-level compromises pose little for set-of-scopes binding. Supporting an incremental and redefinition-capable top-level context requires only that the binding table allow updates of existing bindings, which is straightforward.

An more troublesome aspect of top-level namespaces in Racket is that a form might be captured (via quote-syntax), expanded, or compiled in one namespace, and then evaluated in another namespace. Historically, top-level bindings have been equated with “unbound,” so that expanded and compiled forms originating in a top-level context could move freely among namespaces. This treatment as “unbound” has been fuzzy, however, and forms that originate from module namespaces have been treated differently from forms that originate in a non-module namespace.

To accommodate top-level namespaces with as much consistency (of binding treatment) and convenience (of moving forms among top-level namespaces) as possible, we introduce one more dimension to syntax objects. Instead of having a single set of scopes per phase, each syntax object has a sequence of scope sets per phase. When a syntax object is introduced to a top-level context that is not already included in its scope set (at a gven phase), the current scope set is cloned as a new first item of the list of sets; all further scope-set manipulations affect that first item. When looking up an identifier’s binding, however, the sequence is traversed until a binding is found. In other words, all but the first item in the list act as fallbacks for locating a binding. In practice, this fallback mechanisms is consistent with most existing code without otherwise interfering with scope management (since the fallbacks apply only when an identifier is otherwise unbound).

9 The Syntax-Function Zoo

Compared to Dybvig et al. (1993) or even Flatt et al. (2012), Racket adds many functions for manipulating syntax objects during macro expansion in ways that are sensitive to the expansion context. We have mentioned first-class definition context and rename transformers, but Racket provides many more tools:

• The syntax-local-introduce function lets a macro explicitly toggle the introduction status of a syntax object by flipping the mark (specific to the current macro invocation) that distinguishes use-site and macro-introduced identifiers.

  With the set-of-scopes expander, the mark is replaced by a scope, and syntax-local-introduce flips both the introduction scope and the use-site scope (if any) of the current expansion.

• The make-syntax-introducer function generates a function that works like syntax-local-introduce, but for a fresh mark/scope.

  As a new feature, and unlike syntax-local-introduce, the generated function accepts an additional argument to select the mode: 'flip (the default) to flip the scope’s presence, 'add to add the scope if not present already, and 'remove to remove the scope if it is currently present.

• The make-syntax-delta-introducer function accepts two arguments, and it creates a function similar to the one produced by make-syntax-introducer, but instead of operating on a fresh mark/scope, it operates on all marks/scopes on the first syntax object that are not present on the second syntax object.

  With the set-of-scopes expander, the generated function accepts a 'flip, 'add, or 'remove mode. This operation gives macro implementors relatively fine-grained control over scopes, but without exposing individual scopes, so the macro expander still can perform certain optimizations and make certain representation choices (e.g., due to the fact that the phase-specific “inside” scopes of a module are added or removed together).

• The questionable syntax-local-make-delta-introducer function, which finds the difference between a reference and its binding so that the difference can be applied to another syntax object, is no longer needed, because it can be implemented with make-syntax-delta-introducer.

  Since make-syntax-delta-introducer for the previous macro expander manipulated only marks, and not renamings, it was insufficient for certain kinds of scope transfer. Unifying all binding through scopes makes make-syntax-delta-introducer sufficient.

• The syntax-local-get-shadower function in the current expander acts as an especially heavy hammer for non-hygienic binding. It synthesizes an identifier like a given one that will capture any identifiers that are original to the current expansion context.

  The main use of syntax-local-get-shadower is to implement syntax parameters (Bazilay et al. 2011). In the Racket set-of-scopes expander, syntax-local-get-shadower has been simplified so that it effectively serves only as a hook for implementing syntax parameters, while other former uses are better and more consistently implemented through make-syntax-delta-introducer.

  Implementing syntax parameters as a core feature of the macro expander would be sensible and slightly cleaner. We maintain the syntax-local-get-shadower approach only because it’s simpler with our current infrastructure.

As mentioned in First-Class Definition Contexts, a first-class definition context is difficult to specify in terms of renamings. In that case, an internal-definition context is backed by a renaming on syntax objects, but the renaming can refer to itself or other renamings, and so the binding-resolution process must handle a complex form of cycles. With set-of-scopes binding, an internal-definition context is backed by a scope for the context; an internal-definition context doesn’t create cyclic syntax-object structures, and it needs no special rules for resolving references to bindings.

10 Compatibility with the Current Racket Expander

The documentation for Racket’s current macro expansion attempts to avoid references to the underlying mark-and-rename model. As a result, it is often too imprecise to expose differences created by a change to set-of-scope binding. One goal of the new model is to allow the specification and documentation of Racket’s macro expander to be tightened; scope sets are precise enough for specification, but abstract enough to allow high-level reasoning.

Most Racket programs expand and run the same with a set-of-scope expander as before. Hygienic, pattern-based macros are always unaffected (but in the current macro system, a pattern-based macro that expands to a submodule can be effectively non-hygienic; see below). Meanwhile, macros that are intended to manipulate scope in complex ways can expose the difference between the macro systems. For example, the Racket implementations of the splicing forms in racket/splicing must change, and some internal details of the unit, class, and define-generics forms must also change.

11 Debugging Support

Binding resolution in Racket’s current macro expander is completely opaque to macro implementers. When something goes wrong, the expander can report little more than “unbound identifier” or “out of context”, because the process of replaying renamings and the encodings used for the renamings are difficult to unpack and relate to the programmer.

A set-of-scopes expander is more frequently in a position to report “unbound identifier, but here are the identifier’s scopes, and here are some bindings that are connected to those scopes.” In the case of ambiguous bindings, the expander can report the referencing identifier’s scopes and the scopes of the competing bindings. These details are reported in a way similar to stack traces: subject to optimization and representation choices, and underspecified as a result, but invaluable for debugging purposes.

The #<module-path-index:()>s in the error correspond to the binding, and they mean “in this module.” Overall, the message shows that x has scopes corresponding to two different macro expansions, and it’s bound by definitions that were produced by the expansions separately.

12 Model

Below is a model in the style of Flatt et al. (2012). The model is comparable to a model that includes support for internal-definition contexts, but the resolve metafunction is dramatically simplified, even compared to a model without internal-definition contexts.

Although this model includes pruning within syntax, that pruning is not so interesting, since compile-time code is parsed directly instead of macro-expanded.

Acknowledgments

Thanks to Matthias Felleisen, Robby Findler, Sam Tobin-Hochstadt, Jay McCarthy, Ryan Culpepper, Michael Adams, Michael Ballantyne, Tim Disney, Simon Peyton Jones, Shriram Krishnamurthi, and Eelco Visser for discussions about set-of-scopes binding.

Bibliography