Semanticsimplementation

The Annotated AST

Same tree, new fields. Every identifier now points at a declaration and every expression carries a type: `BinaryExpression{type: int, lhs: int, rhs: int}`. This is the artifact semantic analysis produces and the thing lowering consumes, and its defining property is that the shape did not change.

The question

What exactly does the type checker hand to the next phase, and how is it different from what the parser produced?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The parser's tree, unchanged in shape, plus two annotations per relevant node: a symbol on every identifier saying which declaration it refers to, and a type on every expression saying what it evaluates to. Kept either as fields on the node or — more usually in modern frontends — in side tables keyed by node id. The representation exists to answer "is this program well-formed, and what does each part mean", which is the last question askable about the source before the tree stops resembling the source at all.

What this phase may assume or do

Everything downstream is entitled to assume this tree type-checked: that every identifier has a symbol, every expression has a type, and every operation is defined for its operand types. That entitlement is what licenses type-based reasoning in the optimizer — if an int addition cannot be a pointer addition, an alias analysis may rely on it. The obligation on this phase is the mirror image: it must not annotate a node it did not check, and where checking failed it must attach an error type rather than a plausible guess, or a later phase will optimize on a fact that was never established.

Key points

  • The annotated AST is the parser's tree with a symbol on every identifier and a type on every expression. The shape is unchanged.
  • Types propagate upward from leaves, which is why type checking is a post-order traversal.
  • Annotations may live on the node or in side tables keyed by node id; the second keeps the tree immutable and cacheable.
  • This is the last representation that still resembles the source, which is why interpreters, language servers and type-directed lints all stop here.
  • Everything downstream is entitled to assume the program type-checked, and that entitlement is what licenses type-based optimization.
  • Type erasure happens at this handover; what is dropped here is unavailable to every later phase and to the runtime.

Same shape, two more fields

Compare this tree with the one in [[abstract-syntax-tree]]. Node for node, child for child, it is identical. What changed is that x now points at a declaration, and every expression carries the type it evaluates to. That is the whole difference, and the fact that it *is* the whole difference is the point: a semantic pass annotates, it does not restructure. Restructuring is [[lowering]], and it happens after this.

The types propagate upward, which is [[ast-traversal]]'s post-order rule in action. 1 and 2 are int because of their literal form; + is int because both operands are and the language defines int + int -> int; the declaration is int because its initializer is. Nothing here could have been computed on the way down.

The let x = 1 + 2; tree after name resolution and type checking
Typed AST — same shape, with symbols and types attached
VariableDeclaration: int→ decl#4 local `x`— The declaration's type came from its initializer — in a language requiring annotations it would instead have been checked against one.
├── Identifier x: int→ decl#4“x”— The binding site. Later uses of `x` will carry the same `decl#4`, which is how the compiler knows they are the same variable without comparing names.
└── BinaryExpression +: int→ int::add“1 + 2”— The operator itself resolved: in a language with overloading or traits, this records *which* `+`, which is what the code generator will emit a call to or inline.
├── NumberLiteral 1: int“1”
└── NumberLiteral 2: int“2”

Read it asTwo new columns, no new nodes. Every question the next phase asks — what size is this value, which operation is this, does this name refer to a stack slot or a global — is answerable from the annotations, and none of them was answerable before.

On the node, or beside it

Where the annotations live is a real decision with real consequences. Storing them as fields on the node is direct and fast to read, and it means the node grows a field for every phase that wants to record something — a type, a symbol, a constant value, a lint suppression, an inferred effect. In a structure with millions of nodes, most of them never read by most passes, that is memory and cache pressure paid on every compilation.

The alternative is a side table keyed by node id: types: Map<NodeId, Type>, symbols: Map<NodeId, DeclId>. The node stays small and — crucially — stays *immutable*, which is what lets it be shared across versions of the file and cached between compilations. This is where the argument in [[ast-node-design]] about arena indices pays off: node ids exist precisely so that things can be keyed by them.

Frontends that serve editors take the side-table route almost without exception, because they need the syntax tree to be a pure function of the source text. A tree with types written into it is a function of the source *and* of which passes have run, which cannot be cached or shared.

Where annotations livetypical
Fields on the nodeSide table by node id
Read costOne field accessA hash or array lookup
Node sizeGrows with every pass that annotatesConstant
Tree immutabilityLost — annotating mutatesPreserved — the tree never changes
Cacheable across compilationsNo, the tree depends on which passes ranYes, the tree is a function of the text alone
Discarding a pass's resultsRequires clearing fields everywhereDrop the table
Typical homeBatch compilers, teaching implementationsEditor-facing frontends, incremental compilers

What this tree is handed to, and what happens to it

implementationWhat a frontend calls this representation and how long it keeps it differs sharply. Clang keeps one AST with types attached and emits LLVM IR directly from it; rustc lowers AST to HIR, type-checks HIR, then lowers to MIR, so "the annotated tree" is HIR plus separate typeck results tables; the TypeScript compiler keeps the tree and computes types lazily through a checker that is queried rather than run as a pass. All three fit the description in this lesson and none of them shares a data structure with the others.

The annotated AST is the last representation that still looks like the program the user wrote. Everything after it is a transformation into something else: lowering flattens it into [[what-is-an-ir]], evaluation order gets fixed, expression nesting disappears, and by the time there is a control-flow graph the correspondence to source is maintained only by spans deliberately carried along.

That makes this tree the natural stopping point for several things that are not compilation. A tree-walking interpreter executes it directly and never needs an IR at all. A language server answers hover, completion and go-to-definition from exactly these annotations. A documentation generator reads the signatures. Type-directed linting — "this comparison is always true", "this cast is redundant" — needs types and source structure at the same time, and this is the only representation that has both.

It is also where the type information *stops* in some languages. TypeScript type-checks this tree and then erases every annotation, emitting JavaScript; the types never reach a backend because there is no backend. Java erases generic type arguments here, which is why a List<String> and a List<Integer> are the same class at runtime. [[type-erasure]] is a decision made at this handover, and everything a runtime cannot do about types traces back to it.

  • A tree-walking interpreter stops here and executes — see [[tree-walk-interpreter]].
  • A language server serves hover, completion and go-to-definition from exactly these annotations.
  • Type-directed lints need types and source shape together, which only this representation offers.
  • Lowering consumes it and produces an IR; the tree is usually discarded shortly afterwards.
  • Languages that erase types do so at this handover, and nothing downstream can recover what was dropped.

How it works

The steps, in the order the compiler takes them.

  • Name resolution attaches a declaration reference to every identifier occurrence.
  • Type checking walks bottom-up, computing each node's type from its children's types and the resolved symbols, and recording the result.
  • Operator and method uses record *which* overload or implementation was selected, not merely that the operation type-checks.
  • Implicit conversions, if the language has them, are recorded explicitly — usually as inserted coercion nodes — so that lowering does not have to re-derive them.
  • Nodes that failed to check receive an error type that unifies with everything, so one mistake yields one message.
  • The completed tree plus its side tables is handed to lowering, which reads the annotations and produces an IR; the tree is then usually released.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A node is annotated with a type that was never checked — a guess to keep a pass moving — and the optimizer later relies on it. The generated code assumes an integer where a floating-point value arrives, and the result is wrong with no diagnostic anywhere.
  • The selected overload is not recorded, only the fact that some overload matched. Lowering re-derives it with slightly different rules and emits a call to a different function than the one the type checker approved.
  • An implicit conversion is checked but not recorded, so the backend omits it. An int is passed where a double was expected and the callee reads the bit pattern as a float — a silently wrong number, far from the source of the mistake.
  • Annotations are written into nodes and a later pass clones a node without them. Type information is missing for that subtree, and the failure appears as an internal compiler error naming a node that "should have a type".
  • The error type does not unify with everything, so one unresolved name produces a cascade of type errors about it and the real message is the first of forty.
  • A frontend caches the tree with types written in, then reuses it after a dependency changed. Types are stale, the code compiles, and the mismatch surfaces at link time or not at all.

When it helps

  • Every later phase: lowering needs types to pick operations and sizes, and code generation needs symbols to know what to reference.
  • Tree-walking interpreters, which can execute this representation directly with no further transformation.
  • Editor features and type-directed lints, which need types and source structure simultaneously — the only representation that offers both.

When it hurts

  • Optimization. The tree has no control-flow graph, no data-flow facts and no single-assignment property; almost every interesting transformation is easier on an IR.
  • Anything flow-sensitive. "Is this null here" depends on the path taken, and a type on a node is a fact about the expression, not about a program point.
  • Memory, in a frontend that keeps the tree and every annotation alive for a whole session — which is exactly what a language server does, and the reason node size is a live concern there.

What it costs

Every one of these is paid by something.

  • Annotating in place buys a single representation to reason about and costs the tree's immutability, and with it caching, sharing and incremental reuse.
  • Side tables buy an immutable, cacheable tree and cost an indirection on every annotation read, in passes that read them constantly.
  • Recording resolved overloads and inserted coercions buys a backend that never re-derives a decision and costs tree size plus the discipline of keeping the two in sync.
  • Keeping the annotated tree alive after lowering buys diagnostics and tooling that can still speak in source terms, and costs memory for a structure the compiler proper no longer needs.
  • Erasing types at this point buys a simpler runtime and smaller output and costs everything that needs types at runtime — reflection, specialization, precise error messages from a generic — permanently.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Do not annotate the AST at all: lower to an IR first and type-check the IR. Some compilers do this for parts of the language, and it decouples checking from surface syntax at the cost of every diagnostic having to be mapped back to source.
  • A separate typed representation rather than annotations on the untyped one, as rustc does with HIR and its typeck tables. Keeps the surface tree pristine and costs a second tree to build, maintain and lower from.
  • Lazy, demand-driven typing, as the TypeScript checker does: no pass computes types for everything; a checker answers "what is the type of this node" on request and memoises. Excellent for editors, and it means "the annotated tree" is a conceptual view rather than a materialised structure.
  • Keep types only where they are needed for code generation and discard the rest immediately, which minimises memory and makes every later diagnostic worse.

See it for yourself

The flag, dump or tool that shows you this directly.

  • C / C++: clang -Xclang -ast-dump -fsyntax-only file.c prints the type on every expression node, including the implicit conversions Clang inserted as explicit ImplicitCastExpr nodes — the recorded-coercion mechanism, visible.
  • Rust: rustc -Z unpretty=hir-tree for the tree; the typeck results are separate tables, which is exactly the side-table design described here.
  • TypeScript: tsc --noEmit --extendedDiagnostics reports check time separately from parse time, and the language service's hover is this annotation queried directly.
  • Java: javap -c on a compiled class shows what survived erasure — generic type arguments are gone, and the signatures that remain are the erased ones.
  • Our pipeline explorer at /compilers/pipeline shows the AST and the typed AST as adjacent panels over the same program, with each node linked to its counterpart.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The typed AST is a different tree." It is the same tree with more known about it. If the shape changed, that was lowering, not annotation.
  • "Every node has a type." Expressions have types. Statements, declarations and blocks may or may not, depending on the language — in an expression-oriented language like Rust they do, and in C they do not.
  • "If the tree type-checks, the annotations are complete." Only for what was checked. Nodes on error paths carry error types, and a phase that treats an error type as a real one produces confident nonsense.
  • "Types are still there at runtime." Only if the language reifies them. TypeScript erases them entirely, Java erases generic arguments, and what a runtime cannot do about types was decided right here.

Misconceptions

The claim, and what is actually true.

Type checking transforms the program.
It annotates it. The shape is identical before and after; a phase that changes the shape is doing lowering, and conflating the two is how legality conditions get skipped.
The annotated AST is what gets executed.
Only in a tree-walking interpreter. In a compiler it is lowered to an IR and discarded, and by the time anything runs there is no tree.
Adding types to nodes is free.
It grows every node in a structure with millions of them and, worse, makes the tree depend on which passes have run — which is what stops it from being cached or shared.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The type checker does not rewrite your program. It walks the tree the parser built and writes two things onto it: which declaration each name refers to, and what type each expression has. Same nodes, same shape, more known. That annotated tree is what gets handed to the next phase, and it is the last version of the program that still looks like what you wrote.

practical

When a compiler reports a type you did not expect, dump this tree rather than reasoning about the rules. clang -Xclang -ast-dump shows the type on every subexpression and, importantly, shows the implicit conversions the compiler inserted — which is where the surprise usually is. An unexpected ImplicitCastExpr explains far more type puzzles than the specification does.

advanced

This handover is where a frontend decides how much of the source-level story survives. Everything the annotated tree records and lowering carries forward is available to the optimizer and the debugger; everything it drops is gone. Types drive alias analysis and devirtualization; erasure forecloses runtime specialization; whether a coercion was recorded decides whether the backend re-derives it. The cluster of decisions is why two compilers for the same language can differ so much in what they can optimize and what they can tell you when something goes wrong — and why [[information-loss]] is a lesson about design rather than about inevitability.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationWhether the annotated tree is one structure or several is per-compiler. Clang annotates one AST in place and generates LLVM IR from it; rustc keeps HIR plus separate TypeckResults tables indexed by HIR id; the TypeScript compiler materialises no annotated tree at all and computes types on demand through the checker. The lesson's description fits all three at the level of what information exists; it matches none of them as a data structure.
specType erasure is a specified language property, not an implementation shortcut. Java erases generic type arguments — the JLS defines the erasure and it is why List<String> and List<Integer> share a class object and why you cannot write new T[]. TypeScript erases all type annotations by definition, since its output is JavaScript. C# and Rust do the opposite: C# reifies generics in the CLR, and Rust monomorphizes, so both retain information Java discards at this exact point.
typicalRecording the selected overload and inserting explicit coercion nodes is standard in mainstream frontends, and is what stops the backend from re-deriving a decision under slightly different rules. Smaller implementations frequently skip it and re-derive during code generation, which works until the two derivations disagree — a bug class that only appears once the language has enough implicit conversions for the rules to be non-obvious.

If you were asked this in an interview

  • What is different between the AST the parser produces and the one the type checker hands on?
  • Where would you store the type of each expression, and what does each choice cost?
  • Why is this the representation a tree-walking interpreter executes and a language server queries?
  • A backend re-derives an implicit conversion instead of reading one the checker recorded. What can go wrong?

Connections

DSAn-ary-treehash-mapdfs
Domains that do not exist yet
  • Programming Languages & Runtime Internals — What type information survives to runtime — reified generics, boxed values, reflection metadata
    Erasure is decided at this handover and its consequences are felt entirely at runtime: what reflection can see, what a generic collection costs, whether a specialization is possible. This lesson ends at the decision; the runtime owns the consequences.