<p>Let's say I've parsed a file of code into an AST, and now I want to walk the AST and type check it. My AST nodes have a signature like this (C++)</p>
<pre class="lang-cpp prettyprint-override"><code>class ASTNode { 
    ...
    virtual void type_check(Scope &amp;scope) = 0;
</code></pre>
<p>The <code>Scope</code> contains the mapping of names to info about variables, other functions, types, etc. Some <code>ASTNode</code> subtypes create nested <code>Scopes</code> or add names and info to existing <code>Scopes</code>.</p>
<p>Now my problem is that names in the target language can be used before they are declared or defined. For example, I can have code like this in my target language:</p>
<pre><code>fun foo(i: Int, t: Thing) { 
    t.doStuff(i, &quot;blah&quot;)
}
class Thing {
    fun doStuff(x: Int, s: String) { 
        bar(x)
        ...
    }
    ...
}
fun bar(num: Int) { ... }
</code></pre>
<p>So if I'm type checking the AST node for <code>foo</code>, I haven't seen <code>Thing</code> yet, and there is nothing in the <code>Scope</code> about it. Same with the uses of <code>t.doStuff</code>, and <code>bar</code>.</p>
<p>My first idea is to add a new pass to my compiler, that will walk the AST and look at declarations, and add names and initial meta-info to the <code>Scopes</code>. I'm not sure what to call this pass.</p>
<pre class="lang-cpp prettyprint-override"><code>class ASTNode {
    virtual void gather_names(Scope &amp;scope) = 0;
    virtual void type_check(Scope &amp;scope) = 0;
    ...
}
</code></pre>
<p>I may remove the scope arguments and have the scopes be properties of the AST nodes, but you get the idea.</p>
<p>Is there a better way to handle this? Is there a typical way that existing compilers handle out of order declarations and definitions? Languages like C and C++ obviously don't handle it, but other languages do (Java, Swift, etc).</p>
<p>One option, instead of a preliminary pass, would be to skip over undefined names and build up a list of incomplete issues to be resolved later, as the type-checking progresses through the file.</p>

<type-checker><declarations>
Is type checking usually preceded by a pass that looks at just names and declarations?
<p>This pass is traditionally called the <strong><a href="https://en.wikipedia.org/wiki/Name_resolution_(programming_languages)" rel="noreferrer">name resolution</a></strong> phase, and it is very common, though not ubiquitous, as part of the semantic analysis stage of the process.</p>
<p>Typically it involves walking entire trees and collecting names that will be in scope according to the language's name resolution rules, and then one of:</p>
<ul>
<li>Annotating the syntax tree with pointers to the declaration of each name attached to the use site;</li>
<li>Producing a replacement tree where all names are fully-qualified;</li>
<li>Or creating a &quot;scope&quot; value to pass along to other phases.</li>
</ul>
<p>Which one of these is most suitable will depend on the specifics of the implementation; in a pure functional system, mutation is unsuitable, while in other systems mutable annotations may be helpful.</p>
<p>Formal descriptions are usually in terms of rewriting, but some interpreters do only build up a chain of scopes with mappings from names to metadata. Large-scale compilers and interpreters often have <em>many</em> phases of iterative rewrites from the source through several intermediate layers, each adding more information, and name resolution is often a fairly early one.</p>
<p>Languages with more complex name resolution rules may need multiple phases of this. For example, there may be a resolution pass that precedes some type checking, and another afterwards for inherited names. Part of the value of an AST is often in making these transformations easy to write and use.</p>

CC BY-SA 4.0
2023-09-11T23:31:53.650Z
2023-09-11T23:31:53.650Z
Michael Homer
CC BY-SA 4.0
2023-09-11T23:50:10.010Z
Good answer especially that name resolution itself may require multiple passes (not necessarily consecutive) when names may be dynamically added to the scope.
Erik Eidt
CC BY-SA 4.0
2023-09-12T09:34:14.113Z
An example of note for "interleaved" name resolution + type checking is when calling a method M on the result of an expression E. First the names in the expression E are resolved, then from that the type of the expression E is deduced from the type of its sub-components and the top-level operator/function/method, and then based on the type of the expression E the scope in which to look-up the method M is known and name resolution proceeds. It's even more involved when type inference is more complicated.
Matthieu M.
CC BY-SA 4.0
2023-09-13T15:38:27.353Z
I'd call it *global* name resolution in contrast to other name resolution phases that might be required and that may follow different rules because they may need to elaborate declaration cycles.
feldentm
CC BY-SA 4.0
2023-09-13T15:59:39.363Z
Is there a difference between *name resolution* and *scope resolution*? AFAIK scope resolution attaches scopes to names, and name resolution attaches defs to uses: they are almost the same, and name resolution requires scope resolution; but scope resolution doesn't look for defs, so it can skip names with explicit or obvious scopes.
tarzh
<blockquote>
<p>My first idea is to add a new pass to my compiler, that will walk the AST and look at declarations, and add names and initial meta-info to the Scopes. I'm not sure what to call this pass.</p>
</blockquote>
<p>I'd call it identifier binding, namely of (usages of) identifiers to their definitions, as within scope.  Logic systems have a notion of free (i.e. global) and bound (i.e. local) variables.</p>
<blockquote>
<p>One option, instead of a preliminary pass, would be to skip over undefined names and build up a list of incomplete issues to be resolved later, as the type-checking progresses through the file.</p>
</blockquote>
<p>Yes, that's like doing a one pass assembler, which resolves forward label references from a list collected during a single pass.  Certainly can be made to work.</p>
<p>However, why bother?  You can't really do everything you want for type checking with unresolved identifiers.  Might as well have a separate identifier binding pass.  And only then move on to do type checking.</p>
<p>Also, you'll know for sure if you have 0, or &gt; 0 unresolved identifiers and maybe limit error messages as a result during type checking / later passes.</p>
<p>While the list approach can certainly be made to work, I think the multi-pass approach might be less error prone as well as easier to code — you'll never have to deal with partially resolved expressions (or re-resolve expressions) except when there really are unresolved identifiers.</p>
<hr />
<p>FYI, C# is a &quot;two pass compiler&quot; ;) as seen in these articles:</p>
<ul>
<li><p>&quot;The impact on the compiler writer is that we have to have a “two pass” compiler. In the first pass, we look for declarations and ignore bodies. Once we have gleaned all the information from the declarations that we would have got from the headers in C++, we take a second pass over the code and generate the IL for the bodies.&quot;</p>
<p><a href="https://learn.microsoft.com/en-us/archive/blogs/ericlippert/how-many-passes" rel="noreferrer">https://learn.microsoft.com/en-us/archive/blogs/ericlippert/how-many-passes</a></p>
</li>
<li><p><a href="https://www.reddit.com/r/programming/comments/ay451/how_many_passes_how_the_c_compiler_works/" rel="noreferrer">https://www.reddit.com/r/programming/comments/ay451/how_many_passes_how_the_c_compiler_works/</a></p>
</li>
</ul>

CC BY-SA 4.0
2023-09-11T23:30:09.017Z
2023-09-11T23:43:39.557Z
2023-09-11T23:43:39.557Z
Erik Eidt
<p>For languages which allow <a href="https://en.wikipedia.org/wiki/Forward_declaration#Forward_reference" rel="noreferrer">forward references</a> to names which are not yet declared, I think it helps to split name resolution up into two separate parts:</p>
<ul>
<li>Identify all the declarations which give meanings to names,</li>
<li>Identify, for each occurrence of a name, which declaration it refers to.</li>
</ul>
<p>I don't know if these two things have proper names, so I'll call them <strong>name-finding</strong> and <strong>name-binding</strong> respectively.</p>
<p>When the language allows forward references, name-finding and name-binding must occur in separate passes, because a single pass can find some names which are not yet bound.</p>
<p>On the other hand, name-binding and type-checking often <em>cannot</em> occur in entirely separate passes, because in an expression like <code>foo.bar()</code>, the method bound to the name <code>bar</code> depends on the type of the variable bound to the name <code>foo</code> ─ that is, the compiler must bind the name <code>foo</code>, check its type, and then bind the name <code>bar</code>.</p>
<p>So yes, generally you do need two separate passes for name resolution and type-checking, but it's like this:</p>
<ol>
<li>Name-finding,</li>
<li>Name-binding and type-checking (together).</li>
</ol>

CC BY-SA 4.0
2023-09-12T17:44:29.423Z
2023-09-12T17:44:29.423Z
kaya3
# Is type checking usually preceded by a pass that looks at just names and declarations?
Posted by: username_0 on 2023-09-11
Let's say I've parsed a file of code into an AST, and now I want to walk the AST and type check it. My AST nodes have a signature like this (C++)
class ASTNode { 
    ...
    virtual void type_check(Scope &scope) = 0;

The Scope contains the mapping of names to info about variables, other functions, types, etc. Some ASTNode subtypes create nested Scopes or add names and info to existing Scopes.
Now my problem is that names in the target language can be used before they are declared or defined. For example, I can have code like this in my target language:
fun foo(i: Int, t: Thing) { 
    t.doStuff(i, "blah")
}
class Thing {
    fun doStuff(x: Int, s: String) { 
        bar(x)
        ...
    }
    ...
}
fun bar(num: Int) { ... }

So if I'm type checking the AST node for foo, I haven't seen Thing yet, and there is nothing in the Scope about it. Same with the uses of t.doStuff, and bar.
My first idea is to add a new pass to my compiler, that will walk the AST and look at declarations, and add names and initial meta-info to the Scopes. I'm not sure what to call this pass.
class ASTNode {
    virtual void gather_names(Scope &scope) = 0;
    virtual void type_check(Scope &scope) = 0;
    ...
}

I may remove the scope arguments and have the scopes be properties of the AST nodes, but you get the idea.
Is there a better way to handle this? Is there a typical way that existing compilers handle out of order declarations and definitions? Languages like C and C++ obviously don't handle it, but other languages do (Java, Swift, etc).
One option, instead of a preliminary pass, would be to skip over undefined names and build up a list of incomplete issues to be resolved later, as the type-checking progresses through the file.
**Tags:** type-checker declarations
---
## 3 answers
### Answer by username_1 on 2023-09-11. Score: 20
This pass is traditionally called the **[name resolution](https://en.wikipedia.org/wiki/Name_resolution_(programming_languages))** phase, and it is very common, though not ubiquitous, as part of the semantic analysis stage of the process.

Typically it involves walking entire trees and collecting names that will be in scope according to the language's name resolution rules, and then one of:

* Annotating the syntax tree with pointers to the declaration of each name attached to the use site;
* Producing a replacement tree where all names are fully-qualified;
* Or creating a "scope" value to pass along to other phases.

Which one of these is most suitable will depend on the specifics of the implementation; in a pure functional system, mutation is unsuitable, while in other systems mutable annotations may be helpful.

Formal descriptions are usually in terms of rewriting, but some interpreters do only build up a chain of scopes with mappings from names to metadata. Large-scale compilers and interpreters often have *many* phases of iterative rewrites from the source through several intermediate layers, each adding more information, and name resolution is often a fairly early one.

Languages with more complex name resolution rules may need multiple phases of this. For example, there may be a resolution pass that precedes some type checking, and another afterwards for inherited names. Part of the value of an AST is often in making these transformations easy to write and use.
> **Comments:**
> **username_2** (2023-09-11): Good answer especially that name resolution itself may require multiple passes (not necessarily consecutive) when names may be dynamically added to the scope.  
> **username_3** (2023-09-12): An example of note for "interleaved" name resolution + type checking is when calling a method M on the result of an expression E. First the names in the expression E are resolved, then from that the type of the expression E is deduced from the type of its sub-components and the top-level operator/function/method, and then based on the type of the expression E the scope in which to look-up the method M is known and name resolution proceeds. It's even more involved when type inference is more complicated.  
> **username_4** (2023-09-13): I'd call it *global* name resolution in contrast to other name resolution phases that might be required and that may follow different rules because they may need to elaborate declaration cycles.  
> **username_5** (2023-09-13): Is there a difference between *name resolution* and *scope resolution*? AFAIK scope resolution attaches scopes to names, and name resolution attaches defs to uses: they are almost the same, and name resolution requires scope resolution; but scope resolution doesn't look for defs, so it can skip names with explicit or obvious scopes.  
---
### Answer by username_6 on 2023-09-12. Score: 7
For languages which allow [forward references](https://en.wikipedia.org/wiki/Forward_declaration#Forward_reference) to names which are not yet declared, I think it helps to split name resolution up into two separate parts:

* Identify all the declarations which give meanings to names,
* Identify, for each occurrence of a name, which declaration it refers to.

I don't know if these two things have proper names, so I'll call them **name-finding** and **name-binding** respectively.

When the language allows forward references, name-finding and name-binding must occur in separate passes, because a single pass can find some names which are not yet bound.

On the other hand, name-binding and type-checking often *cannot* occur in entirely separate passes, because in an expression like `foo.bar()`, the method bound to the name `bar` depends on the type of the variable bound to the name `foo` ─ that is, the compiler must bind the name `foo`, check its type, and then bind the name `bar`.

So yes, generally you do need two separate passes for name resolution and type-checking, but it's like this:

1. Name-finding,
2. Name-binding and type-checking (together).
---
### Answer by username_2 on 2023-09-11. Score: 6
> My first idea is to add a new pass to my compiler, that will walk the AST and look at declarations, and add names and initial meta-info to the Scopes. I'm not sure what to call this pass.

I'd call it identifier binding, namely of (usages of) identifiers to their definitions, as within scope.  Logic systems have a notion of free (i.e. global) and bound (i.e. local) variables.

> One option, instead of a preliminary pass, would be to skip over undefined names and build up a list of incomplete issues to be resolved later, as the type-checking progresses through the file.

Yes, that's like doing a one pass assembler, which resolves forward label references from a list collected during a single pass.  Certainly can be made to work.

However, why bother?  You can't really do everything you want for type checking with unresolved identifiers.  Might as well have a separate identifier binding pass.  And only then move on to do type checking.

Also, you'll know for sure if you have 0, or > 0 unresolved identifiers and maybe limit error messages as a result during type checking / later passes.

While the list approach can certainly be made to work, I think the multi-pass approach might be less error prone as well as easier to code — you'll never have to deal with partially resolved expressions (or re-resolve expressions) except when there really are unresolved identifiers.

---

FYI, C# is a "two pass compiler" ;) as seen in these articles:

* "The impact on the compiler writer is that we have to have a “two pass” compiler. In the first pass, we look for declarations and ignore bodies. Once we have gleaned all the information from the declarations that we would have got from the headers in C++, we take a second pass over the code and generate the IL for the bodies."

  <https://learn.microsoft.com/en-us/archive/blogs/ericlippert/how-many-passes>
* <https://www.reddit.com/r/programming/comments/ay451/how_many_passes_how_the_c_compiler_works/>
---
