8
$\begingroup$

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:

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!).

$\endgroup$
0

1 Answer 1

6
$\begingroup$

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.

    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 (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 (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. Figure 1 on page 15 include typing rules 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.

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 to read typing rules? on CS.SE provides a good start. It also recommends two books on the subject, Types and Programming Languages and Practical Foundations for Programming Languages, 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 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, and then work your way from there towards something like Rust. There is likely significantly more direct conceptual sharing than you think.

$\endgroup$

You must log in to answer this question.

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