nomlisp syntax model.md

TODO: Things like %app? Also, the explanations of scope sets and phases are not especially useful unless you already have some familiarity with the subject.

---

Nomlisp syntax model

Contents

1. Introduction
2. S-expressions, reading, and syntax objects
3. Phases
4. Overview of syntactic extension
5. Synspaces
6. Scopes and sets of scopes
7. Notation templates
8. The expansion algorithm
9. Expanding normal s-expressions

Introduction

Nomlisp code undergoes several stages of processing before elaboration and evaluation. Initially, the code is a linear string of characters usually read from a file. These characters are parsed, according to the grammar of s-expressions, into a concrete syntax tree (CST). Then the CST undergoes expansion, where syntactic extensions are removed and names are resolved; the resulting manipulated CST is parsed into an abstract syntax tree (AST), which is much simpler in structure than the CST and more amenable to further processing.

The first parsing step, going from text to a CST, is known as “reading”. The last step, going from an expanded CST to an AST, is known as “parsing”. Therefore the pipeline looks like

reading → expansion → parsing → elaboration → evaluation

S-expressions, reading, and syntax objects

The following grammar, over characters, generates textual representations of Nomlisp s-expressions.

sx:
  ambient
  name
  label
  string
  integer
  real
  ' sx
  ` sx
  , sx
  (sx …)
  [sx …]
  sx . sx
  # name sx
  delimited

ambient:
  white-space …+
  ; any-character … new-line
  #; sx

name:
  name-element …+

name-element:
  \ any-character
  ⟨any character that isn't . or : or another delimiter⟩

label:
  : name

delimited:
  open_i sx … close_i

open_i: ⟨the ith opening Unicode bracket⟩
close_i: ⟨the ith closing Unicode bracket⟩

integer: ⟨basically as in Scheme⟩
real: ⟨basically as in Scheme⟩

string:
  “ pretty-string-element … ”
  " boring-string-element … "

pretty-string-element:
  “ pretty-string-element … ”
  \ any-character
  ⟨any character that isn't “ or ” or \⟩

boring-string-element:
  \ any-character
  ⟨any character that isn't " or \⟩

The ambient rule produces strings that are ignored by Nomlisp, and we will assume that such text is filtered out during reading.

We represent CSTs as Nomlisp values using the Syntax type, whose definition follows.

(define/data (SX m) ; m for metadata
  (Name String m)
  (Label String m)
  (String String m)
  (Integer Integer m)
  (Real String m)
  (Quote (SX m) m)
  (Quasiquote (SX m) m)
  (Unquote (SX m) m)
  (List (List (SX m)) m)
  (Bracketed (List (SX m)) m)
  (Dotted (SX m) (SX m) m)
  (Prefixed String (SX m) m)
  (Delimited String (List (SX m)) m))

(define/type Syntax (S-Expression Syntax-Metadata))

(define/type Syntax-Metadata
  (record :context %Context ; scope stuff
          :span Span ; source location
          :id %Id)) ; unique identifier for the s-expression

Values of type Syntax are called “syntax objects”, for terminological compatibility with Scheme. Besides the “datum”, i.e., the actual s-expression, syntax objects store some metadata:

• the “context”, an opaque value that holds information about lexical scope, so that names in the syntax object can be resolved correctly
• the source location, for use e.g. in error reporting
• another opaque value that uniquely identifies this syntax object, which can be used as a key in tables if you need to associate arbitrary information with syntax

The %Context type has one accessible constructor, Empty-Context, which can be used to determine whether a syntax object has any scope information, or to construct fresh, disembodied syntax objects. After code is first read, the resulting syntax objects have Empty-Context in :context.

Unlike Scheme or Racket, the heterogenous trees underlying syntax objects are not typical, generic forms of data in Nomlisp. There is thus no reason to support syntax->datum or similar operations, and datum->syntax is replaced by copy-context : (→ Syntax Syntax Syntax).

As an example of reading, the text (define x 1) would become (eliding metadata)

(List (Cons (Name “define” …)
            (Cons (Name “x” …)
                 (Cons (Integer 1 …) Nil)))
          …)

Phases

Sometimes code must be evaluated during expansion, namely when syntactic extensions are created or used. Such code may itself employ syntactic extensions, meaning that their code will have to be expanded and evaluated as well. For example, a macro definition may use if, another macro.

It is important that expansion-time code and runtime code do not mix: A macro can't refer to a value binding that won't be available until runtime. In order to enforce this restriction, we introduce the concept of phases, which are integers denoting “when” code is run or a binding is accessible. Phase 0 corresponds to runtime; phase 1 is for code needed to expand the phase 0 code; phase 2 is for code needed to expand the phase 1 code; and so on. Phase 0 code is executed “after” phase 1 code, which is executed “after” phase 2 code, etc.

Phase is a property of both code and bindings. In general, user code doesn't need to worry about phasing; for example, modules don't need to be explicitly phase-shifted. However, you can add bindings to a higher-phase environment by enclosing declarations in (for-syntax …).

Overview of syntactic extension

Nomlisp divides the syntax of forms into declarations, types, terms, and patterns. The grammar of the language specifies when each category is expected, which means that they can have distinct namespaces. For example, we know everywhere a type could appear, so there is no issue with a type variable and a term variable sharing a name. These namespaces can also include “bindings” for the built-in constructs (like define, λ), which explains the purpose of a namespace for declarations.

So we have a system of namespaces, each tied to a particular syntactic category; the language is also set up so that different namespaces/categories are expected at specific places. One last feature is that macros and notations are permitted in each one. Term macros, pattern macros, type macros, and declaration macros are all allowed.

We call these namespaces/syntactic categories/expansion contexts “synspaces”. These will be described in much more detail in a later section. For now, know that new synspaces can be introduced and macro writers can add forms into their expansion that tell the expander what synspaces to use to interpret subforms.

Nomlisp syntax can be extended by defining macros and notations. Both categories are based on “transformers”: expansion-time functions over syntax objects. The transformer is applied to the original syntax object that led to its invocation, and its output is re-examined for further expansion.

The association of a macro/notation with a transformer is the only place where a binding involving higher-phase code can be referred to in lower-phase code. That is, macros and notations act like “bridges” between the current phase and the next phase up.

When a macro is defined, by define/syntax or let/syntax, a normal identifier is associated with a transformer, making uses of the macro blend in with built-in constructs. Nomlisp allows bare identifiers to expand, like Common Lisp's symbol macros.

When a notation is defined, a “template” is associated with a transformer, and the transformer is applied to any syntax object that matches the template as long as it appears in a context where macros would be expanded. For example, giving [] a special meaning via notations wouldn't affect macros/syntax that allow […] as a synonym for (…), such as let or case, because they do not cause such subforms to be expanded.

Transformers actually take two arguments, the syntax object and a representation of the expander's state, and they return a tuple of the output syntax object and a new state. This allows them to make changes to the environment without true, language-level side effects.

Synspaces

As just mentioned, Nomlisp has a system of “synspaces” to organize bindings and guide expansion. A synspace is an opaque, expansion-time value that represents a distinct namespace. You can think of the expander's environment as a map

identifier → phase → synspace → meaning

where the synspace value is used as a key in the last level.

Now, this raises the question of where the synspace values come from. When code adds a syntactic binding to a particular synspace, it must mention the synspace by name, and it has to be looked up somewhere. As such, Nomlisp has a built-in synspaces synspace. We will use the metanotation ⟨terms⟩ to denote the value of the synspaces binding of terms.

Here is an example of some unfortunate code:

(define/type define Integer)
(define define : define 1)
(define/syntax define (patterns)
  (λ (s e) '1))

Eliding scope information and phases, we would obtain the following environment after the above declarations have been installed:

terms → ⟨synspaces⟩ → ⟨terms⟩
types → ⟨synspaces⟩ → ⟨types⟩
patterns → ⟨synspaces⟩ → ⟨patterns⟩
…
define → ⟨terms⟩ → variable
         ⟨types⟩ → type
         ⟨patterns⟩ → macro

The expander maintains a stack of synspaces. During normal expansion, identifiers are looked up under all the synspaces in the stack until a match is found. This provides the effect of trying multiple synspaces while enforcing a priority order in cases of ambiguity. Implicitly, at the bottom of the synspace stack, is the “universal” synspace *, which is supposed to be used for constructs that have a purely syntactic function, such as the built-in let/syntax or the popular nest macro.

Most synspaces are implicitly determined by the syntax of the language. The expander knows “I should expect a term here, so I'll expand it in the terms synspace”. In order to adjust the built-in behavior, there are two primitive syntactic forms (permissible in any context where expansion happens—bound in the universal synspace):

• (in-synspaces (synspace …) sexpr) expands sexpr using the given list of synspaces as its synspace stack; the universal namespace is not implicitly added
• (add-synspaces (synspace …) sexpr) expands sexpr with the given synspaces added to the synspace stack (so that the first listed synspace is at the top)

The choice of synspaces used in expanding a particular form depends only on the synspace stack at the time of expansion. The only way a macro can control the interpretation of its expansion is by wrapping it in in-synspaces or add-synspaces.

Here is the complete lineup of built-in synspaces. First are those that correspond to major syntactic categories in the language.

• terms
• patterns
• declarations
• types Some synspaces are more like traditional namespaces.
• modules is for module names
• keywords is for names that sometimes have special meaning but only in restricted contexts, like :, @, or rename (in module export lists)
• synspaces is for synspace names Finally, the universal synspace * is for context-independent syntax.

Scopes and sets of scopes

Macro expansion is hygienic in Nomlisp: Identifiers introduced in the expansion of a macro are kept distinct from those bound at the place where the macro is used, even if they share a name. A macro may freely bind a temporary variable ostensibly named x without fear that the expansion will shadow a different x that the user of the macro hoped to refer to. Let's be clear and define “identifier” as a syntax object holding a Name, a Label, or a notation template.

The expander uses a strategy for implementing hygiene developed by Matthew Flatt for Racket, based around “sets of scopes”. Syntax objects can be tagged with “scopes”, opaque expansion-time values that correspond to particular ranges of code or expansion steps. There are typically multiple scopes, forming a set.

An identifier is looked up both by name (or structure, for templates) and by the set of scopes in the syntax object. The result with the largest subset of scopes is considered to be the identifier's binding. (Actually, this is shorthand. The result with the largest subset still needs to be further indexed by phase and synspace.)

Notation templates

Nomlisp's notation mechanism permits a transformer to be associated with a template that describes a subset of s-expressions. Templates are themselves s-expressions, and they are generated by the following grammar:

template:
  _
  0
  0.0
  “”
  ""
  ()
  []
  empty-delimiters
  ' template
  ` template
  , template
  template . template
  # name template

where empty-delimiters generates pairs of Unicode brackets like {}, ⟨⟩, etc.

A template is said to match an s-expression based on the following recursive definition.

• _ matches any s-expression
• 0 matches any integer
• 0.0 matches any real
• “” or "" matches any string
• () matches any parenthesized list (List syntax object)
• [] matches any bracketed list (Bracketed syntax object)
• empty-delimiters matches any list delimited by the specified brackets (Delimited syntax object)
• ' template matches any quoted s-expression (Quoted syntax object) provided that template matches the subexpression
• ` template matches any quasiquoted s-expression (Quasiquoted syntax object) provided that template matches the subexpression
• , template matches any unquoted s-expression (Unquoted syntax object) provided that template matches the subexpression
• template₁ . template₂ matches a dotted s-expression (Dotted syntax object), provided that template₁ matches the subexpression to the left of . and template₂ matches the subexpression to the right
• # name template matches a prefixed s-expression (Prefixed syntax object), provided that the prefix string has the same characters as name and template matches the s-expression being prefixed

(The main reason I'm not defining this formally, by the way, is that I don't want to devise a metatheory/metanotation for dealing with syntax objects.)

A template is deemed “more specific” than another template, if the first template has any non-_ sub-templates where the second template has _. If a template is more specific than another, it matches a subset of the s-expressions matched by the other one.

Three constraints are imposed on templates, which should reign in potential confusion caused by notations.

1. A template may not consist only of _
2. A template may not match a superset of the s-expressions matched by any template presently defined as a notation; for example, you can't define #format _ if #format “” has been defined
3. If a template is more specific than any existing template, it must not match nested uses of existing templates; for example, you can't define ' ' _ if ' _ already exists, but you can define ' #p _

To see if an s-expression represents a use of a notation, the templates in the environment are searched to find the most specific template that matches the present s-expression.

The expansion algorithm

With all of the above pieces in place, the expansion algorithm is not too complicated.

Initially, the expander's environment contains bindings for primitive syntax—all the built-in constructs of Nomlisp. These bindings behave almost identically to macros, and if macros allowed arbitrary environment modifications (and could be designated as primitive constructs) they could be written as such. The “primitive transformers” generally update the environment and map the expander over their subforms.

Expanding normal s-expressions

A given syntax object is expanded by case analysis on its structure. The first step is looking for a matching notation, and if found its transformer is invoked. If there is no such notation, then we proceed with the following cases.

• name: if name is bound to a transformer, apply it to the syntax object; otherwise resolve it
• (name sx …): if name is bound to a transformer, apply it to the syntax object; otherwise expand name and proceed to subsequent subexpressions, leaving the form otherwise unchanged
• (sx …): expand all the subforms
• sx.sx, where the first sx is a tree of dotted s-expressions containing only names (e.g., the first sx is x.y.z or just x): look up the module designated by the name(s); if the second sx is a name, resolve it and continue expanding, otherwise perform the effect of importing the designated module and expand it
• a number or a string: leave it alone
• otherwise, error

Resolving a syntax object entails replacing an identifier with an “internal name” that is unique per binding, so that details of name, scopes, phase, and synspace no longer matter.

Expanding bodies

The body nonterminal occurs frequently in Nomlisp's grammar, denoting a possibly-empty sequence of declarations followed by a term. We follow Scheme/Racket and allow forward references to macros defined later in the body, provided that they don't occur at the top level. Thus

(begin
  (m …)
  (define/syntax m …))

is forbidden, but

(begin
  (define x (m))
  (define/syntax m …))

is fine.

In order to handle this, the expander makes an initial pass over the body, expanding each form (with declarations and terms at the top of the synspace stack) until it becomes a primitive construct, installing all syntactic bindings (and making entries for other bindings). Then the forms are expanded fully in the resulting environment.

Expanding modules

The top-level entry point to the expander expands a module. There are two paths, depending on the presence of a mutual expression.

Mutually-recursive modules

The expander gathers the modules in the mutually-recursive group by following the mutual expressions. In doing this it can collect all exported syntactic bindings. Each module in the group is then partially expanded like the first pass in a body, with the exported syntactic bindings forbidden at the top level in addition to forward references to macros within the same module. Finally, the modules are fully expanded in an unspecified order.

Non-recursive modules

The declarations in the module are expanded just like a body, except that no terms are allowed.