Qi Compiler Sync Nov 18 2022

Expansion Continuations and Other Creeping Things

Qi Compiler Sync Nov 18 2022

Adjacent meetings: Previous | Up | Next

Summary

We discussed some options for scoping rules for the as binding form, and ways to declare that in the syntax-spec (the artist formerly known as bindingspec) meta-DSL.

Background

Last time, we completed an initial implementation of bindings in the compiler (with remaining issues noted). It remained to declare the scoping rules at the expander level so that some inappropriate uses of bindings or references to bindings can be caught at compile time.

Declaring Scoping Rules

There were a few different options:

1. Take a conservative approach to binding downstream flows so that they are always disallowed if there is a possibility that the form in the current position may not bind the variable (e.g. (~> (or (as v) something-else) (+ v))). That is, we disallow any references that cannot be guaranteed statically to be bound. This approach could be implemented entirely in the expander by notating the scoping rules in syntaxspec. It would treat all of these cases as compile-time errors.
2. Take a liberal approach where the binding syntax is always allowed, and if the variable ends up being unbound when used, a runtime error is raised. That is, we allow all references and only dynamically check whether they are bound. This would be implemented entirely in the compiler as transformations that check to see if the variable is undefined? before attempting to use it. This approach would result in only runtime errors.
3. A hybrid approach where employing the binding in some cases is treated as a compile-time error (e.g. in something like (~> (or (as v) (+ v)) ...), and as a runtime error in other cases (e.g. downstream variable references that may be unbound (as in the example in (1)), which is impossible to know at compile-time unless we unilaterally treat it as an error as in (1)). That is, we disallow those references that we can statically guarantee will not be bound, and dynamically check other references.

For comparison, Racket does something like (3), where in some cases it raises a "variable referenced before definition" (runtime) error vs an "unbound identifier" (compile-time) error in other cases. It does the former if a variable is accessed before its definition in the same scope, and the latter if the variable is referenced in a nested scope (e.g. inside a lambda).

We decided to start with option (1) while prototyping and explore (3) down the line. We will likely need to define such rules for many other forms of the language, in addition to the or form that we used as an example.

With the addition of bindings, a flow expression would entail scoping rules. These rules can be declared in the expander in the form of nested scopes, similar to Racket's nested lexical scopes that define the precedence of binding identifiers in a tree structure. By declaring these rules, we enable the expander to check these rules at compile time. To do this, we first modified the declaration of the floe (flow expression) nonterminal to be a "nesting nonterminal." The nesting-nonterminal form receives a compile-time argument which is the "rest of the expansion" that will be undertaken subsequent to expansion of the present form. We can think of this as an "expansion continuation," as it is analogous to the runtime notion of a continuation.

We can place the continuation in the expansion to indicate its position and therefore its precedence in the nested scopes. For the threading form, for instance, we would declare the continuation to be nested innermost in relation to the present expression position, so that the variable would be bound in subsequent positions in the form.

Next Steps

• Address the unbounded nesting problem (discussed in previous meetings - see notes).
• Adopt some initial scoping rules to validate handling of bindings at the expander and compiler level.

Attendees

Hans, Michael, Sid