On this page:
5.1 Single-Phase Expansion
5.2 Multi-Phase Expansion
5.3 Local Expansion
5.4 First-Class Definition Contexts

5 Model

We present a formal model of set-of-scope expansion following the style of Flatt et al. (2012). Complete models, both in typeset form and executable form using PLT Redex, are available as model.zip.As a first step, we present a model where only run-time expressions are expanded, and implementations of macros are simply parsed. As a second step, we generalize the model to include phase-specific scope sets and macro expansion at all phases. The third step adds support for local expansion, and the fourth step adds first-class definition contexts. The model does not cover modules or top-level namespaces.

5.1 Single-Phase Expansion

Our macro-expansion model targets a language that includes with variables, function calls, functions, atomic constants, lists, and syntax objects:This model is "core-model.rkt" in model.zip.

image

Since the model is concerned with macro expansion and programmatic manipulation of program terms, we carefully distinguish among
  • names, which are abstract tokens;

  • variables, which correspond to function arguments and references in an AST and are formed by wrapping a name as image;

  • symbols, which are values with respect to the evaluator and are formed by prefixing a name with a quote; and

  • identifiers, which are also values, are formed by combining a symbol with a set of scopes, and are a subset of syntax objects.

For a further explanation of the distinctions among these different uses of names, see Flatt et al. (2012, section 3.2.1).

The model’s evaluator is standard and relies on a image function to implement primitives:

image

Interesting primitives include the ones that manipulate syntax objects,

image

where image extracts the content of a syntax object, and image creates a new syntax object with a given content and the scopes of a given existing syntax object:

image

Macro expansion takes a program that is represented as as a syntax object and produces a fully expanded syntax object. To evaluate the program, the syntax object must be parsed into an AST. The parser uses a image metafunction that takes an identifier and a binding store, image. The names image, image, and image, represent the core syntactic forms, along with the implicit forms of function calls and variable reference:

image

The image metafunction extracts an identifier’s name and its binding context. For now, we ignore phases and define a binding context as simply a set of scopes. A binding store maps a name to a mapping from scope sets to bindings, where bindings are represented by fresh names.

image

The image metafunction uses these pieces along with a image helper function to select a binding. If no binding is available in the store, the identifier’s symbol’s name is returned, which effectively allows access to the four primitive syntactic forms; the macro expander will reject any other unbound reference.

image

Finally, we’re ready to define the image metafunction. In addition to a syntax object (for a program to expand) and a binding store, the expander needs an environment, image, that maps bindings to compile-time meanings. The possible meanings of a binding are the three primitive syntactic forms recognized by image, the image primitive form, a reference to a function argument, or a compile-time value—where a compile-time function represents a macro transformer.

image

The process of macro expansion creates new bindings, so the image metafunction produces a tuple containing an updated binding store along with the expanded program. For example, the simplest case is for the image form, which leaves the body of the form and the store as-is:

image

Since we are not yet dealing with expansion of compile-time terms, no scope pruning is needed for image, and it can be essentially the same as image.

image

Expansion of a image form creates a fresh name and fresh scope for the argument binding. Adding the new scope to the formal argument (we define the image metafunction later) creates the binding identifier. The new binding is added to the store, image, and it is also recorded in the compile-time environment, image, as a variable binding. The body of the function is expanded with those extensions after receiving the new scope, and the pieces are reassembled into a image form.

image

When the generated binding is referenced (i.e., when resolving an identifier produces a binding that is mapped as a variable), then the reference is replaced with the recorded binding, so that the reference is bound-identifier=? to the binding in the expansion result.

image

A local macro binding via image is similar to an argument binding, but the compile-time environment records a macro transformer instead of a variable. The transformer is produced by using image and then image on the compile-time expression for the transformer. After the body is expanded, the macro binding is no longer needed, so the body expansion is the result.

image

Finally, when the expander encounters an identifier that resolves to a binding mapped to a macro transformer, the transformer is applied to the macro use. Fresh scopes are generated to represent the use site, image, and introduced syntax, image, where the introduced-syntax scope is applied using image to both the macro argument and result, where image corresponds to an exclusive-or operation to leave the scope intact on syntax introduced by the macro (see below).

image

The only remaining case of image is to recur for function-call forms, threading through the binding store using an accumulator-style image helper:

image

For completeness, here are the image and image metafunctions for propagating scopes to all parts of a syntax object, where image adds image to image if is not already in image or removes it otherwise:

image

To take a program from source to value, use image, then image, then image.

5.2 Multi-Phase Expansion

To support phase-specific scope sets, we change the definition of image so that it is a mapping from phases to scope sets:This model is "phases-model.rkt" in model.zip.

image

With this change, many metafunctions must be indexed by the current phase of expansion. For example, the result of image depends on the current phase:

image

Phase-specific expansion allows image to expand the compile-time expression for a macro implementation, instead of just parsing the expression. Note that the uses of image and image on the transformer expression are indexed by image:

image

In addition to carrying a phase index, the revised image takes a set of scopes created for bindings. Those scopes are the ones to be pruned from quoted syntax by the revised image expansion:

image

The image metafunction recurs through a syntax object to remove all of the given scopes at the indicated phase:

image

5.3 Local Expansion

Environment inspection via syntax-local-value and local expansion via local-expand are accommodated in the model essentially as in Flatt et al. (2012), but since local expansion can create bindings, the image metafunction must consume and produce a binding store. The image metafunction also must be index by the phase used for syntax operations.

Local expansion needs the current macro expansion’s introduction scope, if any. In addition, local expansions that move identifiers into binding positions need syntax-local-identifier-as-binding, which requires information about scopes in the current expansion context. Local expansion, meanwhile, can create new such scopes. To support those interactions, image and image must both consume and produce scope sets for the current use-site scopes, and binding scopes must also be available for local expansion of image forms. To facilitate threading through all of that information, we define image as an optional current scope and image as an extended store:This model is "local-model.rkt" in model.zip.

image

The second part of a image tuple is a set of scopes to be pruned at image forms. The third part is a subset of those scopes that are the current expansion context’s use-site scopes, which are pruned by syntax-local-identifier-as-binding. The different parts of a image tuple vary in different ways: the image part is consistently threaded through evaluation and expansion, while the scope-set parts are stack-like for expansion and threaded through evaluation. In the case of a macro-application step, the scope-set parts of the tuple are threaded through expansion, too, more like evaluation.

In the model, the image, image, and image primitives represent syntax-local-value, local-expand, and syntax-local-identifier-as-binding, respectively:

image

The implementation of image uses a new image transformer to make an identifier a stopping point for expansion while remembering the former image mapping of the identifier. The image helper function strips away a image constructor:

image

The expander must recognize image transformers to halt expansion at that point:

image

The revised macro-application rule for image shows how the use-site scopes component of image is updated and how the current application’s macro-introduction scope is passed to image:

image

In contrast, the revised image rule shows how the pruning scope set is extended for expanding the body of the function, the use-site scope set is reset to empty, and all extensions are discarded in the expansion’s resulting store tuple.

image

5.4 First-Class Definition Contexts

Supporting first-class definition contexts requires no further changes to the image metafunction, but the image metafunction must be extended to implement the image and image primitives, which model the syntax-local-make-definition-context and syntax-local-bind-syntaxes functions. This model is "defs-model.rkt" in model.zip.

The image primitive allocates a new scope to represent the definition context, and it also allocates a mutable reference to a compile-time environment that initially references the current environment. The two pieces are combined with a image value constructor:

image

The image primitive works in two modes. In the first mode, it is given only a definition context and an identifier, and it creates a new binding for the identifier that includes the definition context’s scope. The new binding is mapped to variable in an updated environment for definition context:

image

When image is given an additional syntax object, it expands and evaluates the additional syntax object as a compile-time expression, and it adds a macro binding to the definition context’s environment:

image

Note that image in this mode defines a potentially recursive macro, since the definition context’s scope is added to compile-time expression before expanding and parsing it.

Finally, a definition context is used to expand an expression by providing the definition context as an extra argument to image. The implementation of the new case for image is similar to the old one, but the definition context’s scope is applied to the given syntax object before expanding it, and the definition context’s environment is used for expansion.

image