The Surprising Difficulty of Name Binding - kvverti/rusty-lavender GitHub Wiki

Name binding in Lavender is done at the semantic analysis stage as part of constructing the intermediate AST from the output of the parser. Currently, name binding is not finalized.

Difficulties

Type variable names must be bound to the appropriate scope. Consider the following declaration.

def const: 'a -> (for b. b -> 'a)

The above should produce the following names

  • value/::const for the occurrence of const, which is bound to the global scope.
  • type/(->) for both occurrences of ->, which is left unbound (but will later be resolved to the global scope).
  • type/const::a for both occurrences of 'a, which are bound to the scope of the type.
  • type/const::0::b for both occurrences of b, which are bound to the scope of the type lambda.

Note that the second occurrence of 'a is inside a nested expression, but is bound to the outer scope because type variables may be implicitly declared.

Consider next the following definition.

def uncurry f (a, b) => f a b

The above should produce the following names

  • value/::uncurry for the occurrence of uncurry.
  • value/f for the occurrences of f, which may be bound to the scope of the definition.
  • value/(,) for the occurrence of ,, which is left unbound.
  • value/a for the occurrences of a, which may be bound to the scope of the definition.
  • value/b for the occurrences of b, which may be bound to the scope of the definition.

Note that, in this case, the scopes of a and b are bound to the definition, despite being similarly placed within a nested subexpression. The case of patterns complicates things further because names in an argument position may either be a declaration of a pattern binding or a reference to a value in an external scope.

Algorithm

These examples imply, in general, that name binding must follow two steps.

  1. Collect names from the parse tree and determine whether those names are definitely declarations. Declarations are always placed into a well-defined scope, some of which are as follows.

    • The scope of a type variable declaration 'a is the type of the enclosing definition.
    • The scope of a pattern binding a is that of the enclosing definition body.
    • The scope of a definition name f is the enclosing scope.
    • The scope of a lambda parameter a is the body of the lambda.

    Names which are not definitely declarations are collected but not bound, but are tagged with the scope in which they appear. These names will be resolved later.

  2. Unbound names are resolved statically using the closest enclosing scope rule. Unbound pattern names which are not found in any enclosing scope are promoted to declarations and are assigned a declaring scope as in step 1.

Implementation

The implementation uses a trait of the following form.

trait Extract {
  fn extract(&self, data_storage: &mut DataStorage, ctx: &ParentContext);
}

The trait is implemented on each relevant node of the parse tree. The data_storage parameter is an out parameter where the bound and unbound names are stored (and later where the algorithm for name resolution looks). The ctx parameter is context from the parent nodes of the parse tree, containing such things as the enclosing scope and closest enclosing definition.