7
$\begingroup$

In my language that is similiar to Java, one type from a program's package block can rely on the type of another program's package block. Other things also mix on, such as import, namespace aliases and use namespace directives.

E.g. this can be resolved in one pass:

package q.b {
    public type N = Number
}
package {
    import q.b.N
}

But one package block can rely on the other in different ways:

package q.b {
    public namespace N1 = q.b.N2
    public namespace N2 {
    }
}

The problem here is that N2 is defined after N1 is assigned as an alias of N2, where N2 does not even exist yet. Clearly more than one verification pass is necessary. What strategy can I use?

Also worthy noting type can have a complex right-hand side, like a function type. import can be an alias, e.g., import y = q.x and use namespace can have a constant expression. Although for use namespace the expression is generally simple.

$\endgroup$
0

3 Answers 3

5
$\begingroup$

In my compiler, I simply collected what could not be resolved in one pass and resolved in multiple times until a limit.

E.g. regarding type:

  • First pass:
    • If the right-hand side produces a diagnostic, e.g., a VerifyError, collect the type definition and defer its resolution.
  • Another pass (repeats until no unresolved item is remaining or until a limit)
    • If the right-hand side does not produce a diagnostic, remove the type definition from the collection of unresolved definitions.
  • Visit all unresolved definitions and resolve them by the last time.

This is also done similiarly to import, namespace and use namespace.

Note that things like classes, enums and interfaces are resolved partially across passes, so they aren't resolved similiarly to these items above.

$\endgroup$
4
$\begingroup$

One elegant solution would involve making the compilation process asynchronous. Whenever the compilation routine encounters a name that has to be resolved, it awaits the resolution result. Under the hood, that results in the task suspending its execution and giving way to other compilation tasks, while perodically being woken up by the scheduler, checking if the expected object has become available, and if not, going to sleep again. On the other hand, whenever the compilation has to process an unordered scope (i.e. the body of a file, a namespace or a class - anything but a function, pretty much), instead of going over the contained elements in order, it introduces the containing object and then spawns new compilation tasks for every contained element and awaits them in total ('gather'). If at some point a complete deadlock is encountered (i.e. all tasks are awaiting some definitions), you give a compilation error about a bad recursive reference. (This won't happen for allowable recursion as long as you introduce a 'partial' definition for every element prior to processing all of its subelements. For instance, to process a function call you don't need its contents, so an incomplete function definition should exist before its body is handled). When there are no tasks left, you're done.

(Note that asynchronousness here has nothing to do with threads and parallelism. It's just a way to express segmentable tasks with complicated dependencies).

I'm not sure if this approach has been implemented before, and there might be caveats I haven't considered, but it seems like it would work quite well

$\endgroup$
3
$\begingroup$

In the A Theory of Name Resolution paper late Eelco Visser developed a Scope Graphs model that encompasses almost all name binding semantics from programming languages, including let, let rec, function parameters and imports.

Purely descriptive model of Scope Graphs is augmented with a declarative constraint-based language to specify the name resolution rules. As long as the language is pure and declarative, it admits optimized search strategies with lazy caching and parallel execution, see recent papers from TU Delft PL Group.

As a fun aside, for the "Go to definition" feature GitHub implemented Stack Graphs based on Visser's Scope Graphs. :)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .