<p>I have been working on a custom programming language for a bit, and keep coming back to the fact that I am not easily visualizing in my mind how the compiler will work past the step of creating the AST. Here is what I have written down (the compiler will convert the custom language into JavaScript, for this example):</p>
<p>The compiler works in a few rough phases currently:</p>
<ol>
<li><strong>Parse the text into the AST</strong>, the &quot;tree&quot;. This is the main data
structure we use for the rest of compiling.</li>
<li><strong>Resolve variable references</strong>. This makes sure all the variables
have been figured out (even if at this point they are incorrectly
typed). Example here would be that you referenced a class you extend, it needs to be resolved at this point or so.</li>
<li><strong>Check variable lifetime</strong> to make sure variables are defined in the
right spots. (Rust lifetimes? Does it happen yet?)</li>
<li><strong>Infer types</strong> to figure out the implied and intended types.</li>
<li><strong>Verify type soundness</strong> to make sure the inferred types are
correctly managed.</li>
<li><strong>Check variable mutability</strong> to make sure variables that can't be
modified aren't.</li>
<li><strong>Verify borrowing/ownership</strong> to make sure only one owner exists per
variable.</li>
<li><strong>Generate target language output code AST</strong> (JS).</li>
<li><strong>Write to string</strong> and save to output file.</li>
</ol>
<p>I am fuzzy on everything in between step 1, maybe 2, and step 8. I can go from step 1 to step 8 no problem, now I have to figure out how to do the actual typechecking part. These links were helpful too:</p>
<ul>
<li><a href="https://rustc-dev-guide.rust-lang.org/type-inference.html" rel="noreferrer">Type Inference in Rust Compiler</a></li>
<li><a href="https://sdleffler.github.io/RustTypeSystemTuringComplete/" rel="noreferrer">https://sdleffler.github.io/RustTypeSystemTuringComplete/</a></li>
<li><a href="http://sinelaw.github.io/infernu.org/s/posts/type-system.html" rel="noreferrer">http://sinelaw.github.io/infernu.org/s/posts/type-system.html</a></li>
<li><a href="https://jaked.org/blog/2021-09-15-Reconstructing-TypeScript-part-1" rel="noreferrer">https://jaked.org/blog/2021-09-15-Reconstructing-TypeScript-part-1</a></li>
</ul>
<p>Particularly the last one, it is one of the only <em>imperative language</em> typechecking examples I have come across on the web through Google, pretty much everything typechecking related (all the research) is about functional languages and/or uses Type Theory math or the lambda calculus, which is quite hard to apply to an imperative object-oriented Rust-like language (or JS-like, since in an ideal world it will be like Haxe and compile to Rust or JS). That last TypeScript link goes into some good pseudocode, like the <code>synthObject</code> (type inference) and <code>checkObject</code> (typechecking) functions.</p>
<p>Could you help clarify what order of operations (generally speaking) I should perform in between the first and last steps? Or at a somewhat high level, how it should be accomplished, with maybe a sentence or two explaining how each part is done in an imperative language at a somewhat practical level (so I can get back to trying to implement this thing!).</p>

<compilers><type-inference>
What are the key steps to compiling a custom programming language that is similar to Rust (typechecking, type inference, and borrow checking)?
<h1>Pipeline overview</h1>
<p>This is an exceedingly broad question—some might say too broad. Entire books are written on many of the individual steps in your list, and the tradeoffs involved in choosing how to architect a compiler are far too vast to fit in a single answer on this website. However, from a sufficiently high level, a compiler pipeline for a Rust-like language would generally consist of the following steps:</p>
<ol>
<li><p><strong>Parse.</strong> This step reads source files into an AST.</p>
</li>
<li><p><strong>Resolve names.</strong> This means resolving imports and assigning unique identifiers to local variables. If you have macros, macroexpansion is likely interleaved with this step. If you have type-directed name resolution, this step sets things up for the typechecker to finish.</p>
</li>
<li><p><strong>Check.</strong> This step consists of a smattering of static analyses designed to guarantee static properties:</p>
<ul>
<li><p><strong>Typecheck and borrow check.</strong> There are many techniques for doing this, which can range from fairly simple to extremely complex. In a system with type inference and Rust-like traits, a common strategy is to further split typechecking into two phases:</p>
<ul>
<li><p><strong>Generate constraints.</strong> This step walks the program and emits a bag of constraints like “these two types must be the same” or “this type must belong to this trait”. Unknown type information that must be inferred is represented by “metavariables”, which are like holes in place of types to be filled in later.</p>
</li>
<li><p><strong>Solve constraints.</strong> The solver iteratively processes the constraints, resolving metavariables as it goes. It stops when either all the constraints have been solved or it reaches a contradiction, which is presented to the user as a type error.</p>
</li>
</ul>
<p>Algorithms for doing this process in a way that can, support fancy type system features, execute relatively efficiently, and provide useful error diagnostics can be quite complicated. Usually they’re tailored to each language, since different type systems have different needs, and different approaches come with lots of tradeoffs.</p>
<p><strong>Note that borrow checking is a part of typechecking.</strong> Indeed it must be, because lifetimes appear in types, and they must be inferred and checked as part of the typechecking process. From an implementation perspective, Rust’s lifetime system is part of its type system.</p>
</li>
<li><p><strong>Check pattern exhaustiveness.</strong> This ensures that all pattern matches cover all cases.</p>
</li>
<li><p><strong>Trait coherence check.</strong> This enforces Rust’s <a href="https://rust-lang.github.io/chalk/book/clauses/coherence.html" rel="nofollow noreferrer">orphan rule</a>.</p>
</li>
</ul>
<p>There may be others as well. In practice, many of these checking steps may be interleaved, either out of necessity (because two checks each depend on the information the other produces) or for performance or convenience.</p>
</li>
<li><p><strong>Lower.</strong> Now that the program is known to be valid, the next step is to translate the source language into a simpler and more regular <a href="https://en.wikipedia.org/wiki/Intermediate_representation" rel="nofollow noreferrer">intermediate representation</a> (IR).</p>
</li>
<li><p><strong>Optimize.</strong> The compiler iteratively analyzes and transforms the program into an equivalent program that hopefully performs better. Really fancy compilers even lower and optimize the program through several different IRs, each progressively lower level than the last.</p>
</li>
<li><p><strong>Generate code.</strong> Finally, the optimized IR is translated to code according to the target backend. This may involve performing additional backend-specific optimizations.</p>
</li>
</ol>
<p>This provides the basic sketch, but real compilers vary significantly in how precisely they operate, and there are many, many extensions to this basic design.</p>
<h1>Some notes on typechecking</h1>
<p>In your question, you write this:</p>
<blockquote>
<p>Particularly the last one, it is one of the only imperative language typechecking examples I have come across on the web through Google, pretty much everything typechecking related (all the research) is about functional languages and/or uses Type Theory math or the lambda calculus, which is quite hard to apply to an imperative object-oriented Rust-like language (or JS-like, since in an ideal world it will be like Haxe and compile to Rust or JS).</p>
</blockquote>
<p><strong>This is simply not true.</strong></p>
<p>The theory of type systems is often grounded in the lambda calculus because the <a href="https://en.wikipedia.org/wiki/Simply_typed_lambda_calculus" rel="nofollow noreferrer">simply typed lambda calculus</a> (STLC) is an exceptionally simple typed programming language. It is therefore quite useful as an illustration of the essential concepts. However, those concepts apply just as well to an imperative language as they do to functional ones, even if functional ones may resemble the STLC more directly.</p>
<p>To prove this point, take a look at <a href="https://dl.acm.org/doi/abs/10.1145/3158154" rel="nofollow noreferrer">the RustBelt paper</a>. Figure 1 on page 15 include <a href="https://en.wikipedia.org/wiki/Typing_rule" rel="nofollow noreferrer">typing rules</a> written in precisely the same notation you’ll see used to describe the STLC, including the rules for lifetimes. Here’s an excerpt of a few of them:</p>
<p><a href="https://i.sstatic.net/K3jKv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/K3jKv.png" alt="Screenshot of the typechecking rules for reading and writing and typing of instructions." /></a></p>
<p>This notation is undeniably very dense, and to someone unfamiliar with type systems, it can be quite impenetrable. But do not dismiss it out of hand: such figures are actually an extremely concise way of representing a typechecking algorithm, and once you understand the notation, they communicate the details enormously more clearly than a computer program would.</p>
<p>Algorithms for checking simple type systems can be relatively straightforward, so if you want to implement a simple type system, there is no need to learn this notation. After all, plenty of languages with type systems were developed before the modern notation even existed, and many more have been developed in ad-hoc ways since then.</p>
<p>However, <strong>Rust’s type system is very far from simple</strong>: it implements numerous complex ideas developed over several decades of programming language research, plus some entirely novel ones layered on top. If you are serious about implementing a type system of this sophistication (and you want to have any hope of it being correct), I would urge you to familiarize yourself with the notation people who work on type systems use.</p>
<h2>Where to start?</h2>
<p>For a basic introduction, <a href="https://langdev.stackexchange.com/a/2693/861">How should I read type system notation?</a> provides a good start. I can also recommend two books on the subject, <a href="https://www.cis.upenn.edu/%7Ebcpierce/tapl/" rel="nofollow noreferrer">Types and Programming Languages</a> and <a href="https://www.cs.cmu.edu/%7Erwh/pfpl/2nded.pdf" rel="nofollow noreferrer">Practical Foundations for Programming Languages</a>, both of which cover imperative languages. (PFPL is free, and TAPL is available via Libgen.) Both texts are quite good, but they are also very dense, and I suspect you may find them a little intimidating (I certainly did when I was first teaching myself type systems). You may find <a href="https://cs.brown.edu/courses/cs173/2012/book/types.html" rel="nofollow noreferrer">the relevant chapter of PLAI</a> to be somewhat more accessible, though it does still use a potentially unfamiliar notation (Lisp).</p>
<p>Give some of them a go, and try implementing some typecheckers for simpler languages first. Come back here and ask questions when they come up. Start with the STLC, add polymorphism and imperative features, implement <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system" rel="nofollow noreferrer">Hindley–Milner type inference</a>, and then work your way from there towards something like Rust. There is likely significantly more direct conceptual sharing than you think.</p>

CC BY-SA 4.0
2023-07-05T20:58:57.837Z
2024-11-23T07:14:31.827Z
2024-11-23T07:14:31.827Z
Alexis King
# What are the key steps to compiling a custom programming language that is similar to Rust (typechecking, type inference, and borrow checking)?
Posted by: username_0 on 2023-07-05
I have been working on a custom programming language for a bit, and keep coming back to the fact that I am not easily visualizing in my mind how the compiler will work past the step of creating the AST. Here is what I have written down (the compiler will convert the custom language into JavaScript, for this example):

The compiler works in a few rough phases currently:

1. **Parse the text into the AST**, the "tree". This is the main data
   structure we use for the rest of compiling.
2. **Resolve variable references**. This makes sure all the variables
   have been figured out (even if at this point they are incorrectly
   typed). Example here would be that you referenced a class you extend, it needs to be resolved at this point or so.
3. **Check variable lifetime** to make sure variables are defined in the
   right spots. (Rust lifetimes? Does it happen yet?)
4. **Infer types** to figure out the implied and intended types.
5. **Verify type soundness** to make sure the inferred types are
   correctly managed.
6. **Check variable mutability** to make sure variables that can't be
   modified aren't.
7. **Verify borrowing/ownership** to make sure only one owner exists per
   variable.
8. **Generate target language output code AST** (JS).
9. **Write to string** and save to output file.

I am fuzzy on everything in between step 1, maybe 2, and step 8. I can go from step 1 to step 8 no problem, now I have to figure out how to do the actual typechecking part. These links were helpful too:

* [Type Inference in Rust Compiler](https://rustc-dev-guide.rust-lang.org/type-inference.html)
* <https://sdleffler.github.io/RustTypeSystemTuringComplete/>
* <http://sinelaw.github.io/infernu.org/s/posts/type-system.html>
* <https://jaked.org/blog/2021-09-15-Reconstructing-TypeScript-part-1>

Particularly the last one, it is one of the only *imperative language* typechecking examples I have come across on the web through Google, pretty much everything typechecking related (all the research) is about functional languages and/or uses Type Theory math or the lambda calculus, which is quite hard to apply to an imperative object-oriented Rust-like language (or JS-like, since in an ideal world it will be like Haxe and compile to Rust or JS). That last TypeScript link goes into some good pseudocode, like the `synthObject` (type inference) and `checkObject` (typechecking) functions.

Could you help clarify what order of operations (generally speaking) I should perform in between the first and last steps? Or at a somewhat high level, how it should be accomplished, with maybe a sentence or two explaining how each part is done in an imperative language at a somewhat practical level (so I can get back to trying to implement this thing!).
**Tags:** compilers type-inference
---
## 1 answers
### Answer by username_1 on 2023-07-05. Score: 9 | Accepted answer
# Pipeline overview

This is an exceedingly broad question—some might say too broad. Entire books are written on many of the individual steps in your list, and the tradeoffs involved in choosing how to architect a compiler are far too vast to fit in a single answer on this website. However, from a sufficiently high level, a compiler pipeline for a Rust-like language would generally consist of the following steps:

1. **Parse.** This step reads source files into an AST.
2. **Resolve names.** This means resolving imports and assigning unique identifiers to local variables. If you have macros, macroexpansion is likely interleaved with this step. If you have type-directed name resolution, this step sets things up for the typechecker to finish.
3. **Check.** This step consists of a smattering of static analyses designed to guarantee static properties:

   * **Typecheck and borrow check.** There are many techniques for doing this, which can range from fairly simple to extremely complex. In a system with type inference and Rust-like traits, a common strategy is to further split typechecking into two phases:

     + **Generate constraints.** This step walks the program and emits a bag of constraints like “these two types must be the same” or “this type must belong to this trait”. Unknown type information that must be inferred is represented by “metavariables”, which are like holes in place of types to be filled in later.
     + **Solve constraints.** The solver iteratively processes the constraints, resolving metavariables as it goes. It stops when either all the constraints have been solved or it reaches a contradiction, which is presented to the user as a type error.

     Algorithms for doing this process in a way that can, support fancy type system features, execute relatively efficiently, and provide useful error diagnostics can be quite complicated. Usually they’re tailored to each language, since different type systems have different needs, and different approaches come with lots of tradeoffs.

     **Note that borrow checking is a part of typechecking.** Indeed it must be, because lifetimes appear in types, and they must be inferred and checked as part of the typechecking process. From an implementation perspective, Rust’s lifetime system is part of its type system.
   * **Check pattern exhaustiveness.** This ensures that all pattern matches cover all cases.
   * **Trait coherence check.** This enforces Rust’s [orphan rule](https://rust-lang.github.io/chalk/book/clauses/coherence.html).

   There may be others as well. In practice, many of these checking steps may be interleaved, either out of necessity (because two checks each depend on the information the other produces) or for performance or convenience.
4. **Lower.** Now that the program is known to be valid, the next step is to translate the source language into a simpler and more regular [intermediate representation](https://en.wikipedia.org/wiki/Intermediate_representation) (IR).
5. **Optimize.** The compiler iteratively analyzes and transforms the program into an equivalent program that hopefully performs better. Really fancy compilers even lower and optimize the program through several different IRs, each progressively lower level than the last.
6. **Generate code.** Finally, the optimized IR is translated to code according to the target backend. This may involve performing additional backend-specific optimizations.

This provides the basic sketch, but real compilers vary significantly in how precisely they operate, and there are many, many extensions to this basic design.

# Some notes on typechecking

In your question, you write this:

> Particularly the last one, it is one of the only imperative language typechecking examples I have come across on the web through Google, pretty much everything typechecking related (all the research) is about functional languages and/or uses Type Theory math or the lambda calculus, which is quite hard to apply to an imperative object-oriented Rust-like language (or JS-like, since in an ideal world it will be like Haxe and compile to Rust or JS).

**This is simply not true.**

The theory of type systems is often grounded in the lambda calculus because the [simply typed lambda calculus](https://en.wikipedia.org/wiki/Simply_typed_lambda_calculus) (STLC) is an exceptionally simple typed programming language. It is therefore quite useful as an illustration of the essential concepts. However, those concepts apply just as well to an imperative language as they do to functional ones, even if functional ones may resemble the STLC more directly.

To prove this point, take a look at [the RustBelt paper](https://dl.acm.org/doi/abs/10.1145/3158154). Figure 1 on page 15 include [typing rules](https://en.wikipedia.org/wiki/Typing_rule) written in precisely the same notation you’ll see used to describe the STLC, including the rules for lifetimes. Here’s an excerpt of a few of them:

[![Screenshot of the typechecking rules for reading and writing and typing of instructions.](https://i.sstatic.net/K3jKv.png)](https://i.sstatic.net/K3jKv.png)

This notation is undeniably very dense, and to someone unfamiliar with type systems, it can be quite impenetrable. But do not dismiss it out of hand: such figures are actually an extremely concise way of representing a typechecking algorithm, and once you understand the notation, they communicate the details enormously more clearly than a computer program would.

Algorithms for checking simple type systems can be relatively straightforward, so if you want to implement a simple type system, there is no need to learn this notation. After all, plenty of languages with type systems were developed before the modern notation even existed, and many more have been developed in ad-hoc ways since then.

However, **Rust’s type system is very far from simple**: it implements numerous complex ideas developed over several decades of programming language research, plus some entirely novel ones layered on top. If you are serious about implementing a type system of this sophistication (and you want to have any hope of it being correct), I would urge you to familiarize yourself with the notation people who work on type systems use.

## Where to start?

For a basic introduction, [How should I read type system notation?](https://langdev.stackexchange.com/a/2693/861) provides a good start. I can also recommend two books on the subject, [Types and Programming Languages](https://www.cis.upenn.edu/%7Ebcpierce/tapl/) and [Practical Foundations for Programming Languages](https://www.cs.cmu.edu/%7Erwh/pfpl/2nded.pdf), both of which cover imperative languages. (PFPL is free, and TAPL is available via Libgen.) Both texts are quite good, but they are also very dense, and I suspect you may find them a little intimidating (I certainly did when I was first teaching myself type systems). You may find [the relevant chapter of PLAI](https://cs.brown.edu/courses/cs173/2012/book/types.html) to be somewhat more accessible, though it does still use a potentially unfamiliar notation (Lisp).

Give some of them a go, and try implementing some typecheckers for simpler languages first. Come back here and ask questions when they come up. Start with the STLC, add polymorphism and imperative features, implement [Hindley–Milner type inference](https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system), and then work your way from there towards something like Rust. There is likely significantly more direct conceptual sharing than you think.
---
