Resolver - Spicery/Nutmeg GitHub Wiki

The resolver has the job of annotating references to identifiers with critical information. The codetree for an identifier might look something like this:

{
    "kind": "id",
    "name": "myexampleid",
    "reftype": "get"
}

The resolver will add extra fields to this to describe the scope, unambiguously label local identifiers, the protection level and whether they are referenced or assigned. These are described in more detail below.

Scope

Scope is one of "local", "captured" or "global". Global scope refers to top level bindings, local scope refers to local-variables that are only referenced by the function/method that declares them. Captured is the interesting case, and refers to local-variables that are also referenced within inner functions. For example, here's the classic K combinator:

def K( x ): 
    fn y =>> x endfn
enddef
  • K has global scope
  • x has captured scope
  • y has local scope

We might expect this to generate annotations like:

{
    "kind": "binding",
    "lhs": { "kind": "id", "name": "K", "reftype": "var", "scope": "global"  },
    "rhs": {
        "kind": "lambda",
        "parameters": { "kind": "id", "name": "x", "reftype": "var", "scope": "captured", "label": 0 },
        "body": {
            "kind": "lambda",
            "parameters": { "kind": "id", "name": "y", "reftype": "var", "scope": "local", "label": 1 },
            "body": { "kind": "id", "name": "x", "reftype": "get", "scope": "captured", "label": 0 }
        }
    }
}

N.B. Captured variables are eliminated entirely by the simplifier via a process analogous to lambda-lifting.

label

With the introduction of block-scope, determination of shadowing is noticeably more complicated. The resolver helps later phases of the compiler by allocating all local identifiers a numerical label. Different identifiers receive different labels and the same identifiers receive the same labels.

The labelling algorithm is based on a recursive scan of the codetree, passing down a linked-list of scopes. Scopes can either be a normal lexical scope or a block-scope.

  • When a binding is encountered, the left-hand-side is assigned a new label. The association between the identifier and label is then entered into the relevant scope: for a block-local variable that is the scope at the head of the chain (which must be a block scope); for a non-local variable that is the nearest lexical scope.
  • When a reference is encountered, the scopes are linearly searched for a matching name and the associated label is used.

Protection Level

The resolver propagates any protection that variables enjoy. For example, variables are, by default, "readonly" which means they are protected from assignment. The resolver will annotate every occurrence of a readonly variable (say) foo with the property "protection": ["readonly"] - and incidentally raise an error during compilation if there is an attempt to assign to it. If a variable is declared as 'const' then it would have the property "protection": ["readonly", "immutable"].

Note that variables that are potentially assignable but never actually assigned are also automatically marked as "readonly".

In our example of the combinator "K", this would lead to the following additional declarations.

{
    "kind": "binding",
    "lhs": { "kind": "id", "name": "K", "reftype": "var", "scope": "global", "protection": ["readonly", "immutable"] },
    "rhs": {
        "kind": "lambda",
        "parameters": { "kind": "id", "name": "x", "reftype": "var", "scope": "captured", "protection": ["readonly"], "label": 0 },
        "body": {
            "kind": "function",
            "parameters": { "kind": "id", "name": "y", "reftype": "var", "scope": "local", "protection": ["readonly"], "label": 1 },
            "body": { "kind": "id", "name": "x", "reftype": "get", "scope": "captured", "protection": ["readonly"], "label": 0 }
        }
    }
}

Unused and Unassigned

It also marks variables that have no references as "discard": true. Note that variables that have no references will generate warning messages unless their name starts with an underbar (e.g. _notUsed). Variables whose name starts with an underbar will generate a warning if they are even used. So our definition of K should be written like this:

def K( x ): 
    fn _ =>> x endfn
enddef
{
    "kind": "binding",
    "lhs": { "kind": "id", "name": "K", "reftype": "var", "scope": "global", "protection": ["readonly", "immutable"] },
    "rhs": {
        "kind": "lambda",
        "parameters": { "kind": "id", "name": "x", "reftype": "var", "scope": "captured", "protection": ["readonly"], "label": 0 },
        "body": {
            "kind": "lambda",
            "parameters": { "kind": "id", "name": "_", "reftype": "var", "scope": "local", "protection": ["readonly"], "discard": true },
            "body": { "kind": "id", "name": "x", "reftype": "get", "scope": "captured", "protection": ["readonly"], , "label": 0 }
        }
    }
}