Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 61 ยท Semantic Analysis

Type Checking

Learn how a compiler type checker works: static vs dynamic typing, type rules, a checker pass over the AST and clear error messages, with runnable Python.

A parser can tell you that "abc" * true is a well-formed expression. It cannot tell you that the expression is nonsense. Grammar describes shape, not meaning. The job of deciding whether a program that looks right also makes sense belongs to semantic analysis, and its most visible part is type checking: verifying that every operation is applied to values of a kind it can handle.

This lesson builds on the symbol tables and scopes you already have and on the trees from abstract syntax trees. By the end you will have a working checker for a small language that reports several errors at once, in plain language, without ever running the program.

Static versus dynamic typing

Every language must stop you from adding a string to a boolean somewhere. The question is when.

  • Dynamic typing checks at run time. Each value carries a tag, and the operation looks at the tags just before it executes. Python and JavaScript work this way. Errors appear only when execution reaches the bad line.
  • Static typing checks at compile time. The compiler works out the type of every expression from the source text alone and rejects the program before it runs. Java, C, Go and Rust work this way.
Python Dynamic typing finds problems late

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first two calls run, and the second one probably is not what the author meant. The third fails, but only when that line executes, which might be in production after a rare code path is taken. A static checker looks at the function once and can reject every bad call without running any of them.

Static checking is not free. It rejects some programs that would have worked, and it needs type information (written by the programmer or inferred, which is the topic of the next lesson). Many languages mix both: Java checks most types statically but checks array bounds and casts at run time, and Python lets you add optional annotations that tools such as mypy check statically.

A sound type system guarantees that well-typed programs never hit certain kinds of errors. Few real languages are fully sound (casts, unsafe blocks and null make holes), but the aim is always to rule out as many mistakes as is practical.

Types and type rules

A type is a set of values together with the operations allowed on them. In our language the base types are int, bool and str. A function has a type too: a list of parameter types and a result type, written (int) -> int.

The compiler describes legality with type rules. A rule says: if the parts have these types, then the whole has that type. Writing them in the usual inference-rule style (premises above, conclusion below) makes them short:

TEXT
  e1 : int    e2 : int            e1 : str    e2 : str
 ----------------------- (+)     ----------------------- (+ on strings)
     e1 + e2 : int                   e1 + e2 : str

  e1 : int    e2 : int            e : bool    s1, s2 well-typed
 ----------------------- (<)     ---------------------------------- (if)
     e1 < e2 : bool                 if e then s1 else s2 : ok

Each rule maps directly to a branch of code in the checker. Literals have fixed types (3 : int, true : bool), a variable has whatever type the symbol table recorded for it, and a call f(a, b) is legal when f has type (T1, T2) -> R and the arguments have types T1 and T2; its type is then R.

A checker is a tree walk

The type checker is a recursive function over the AST that returns a type for each expression, a bit like the evaluator in syntax-directed translation computed values. Here the "value" of a node is its type. Literals return their type immediately, a binary node asks its children first and then applies a rule, and statements use the results to decide whether to report an error.

flowchart LR
    A["Typed-source AST"] --> B["Checker pass<br/>(walks the tree)"]
    S["Symbol table<br/>(names to types)"] --> B
    B --> C["AST with a type on<br/>every expression"]
    B --> D["List of errors<br/>(line + message)"]

The checker reads the AST and the symbol table, and produces either types for later phases or a list of errors.

There are three design choices worth making deliberately.

Collect errors, do not stop at the first. A programmer wants to see all the mistakes in one compile, so the checker appends each message to a list and keeps walking. Stopping at the first error is simpler but makes people recompile ten times.

Use a poison type to prevent cascades. If missing is an unknown name, then missing - 1 is also wrong, and so is everything built from it. Reporting all of them would bury the real mistake. The trick is a special error type: once an expression has it, every rule that sees it quietly returns error as well and reports nothing new.

Report positions. Each node remembers its source line (the lexer recorded it; see writing a complete lexer). Without it the message "type mismatch" is nearly useless.

A runnable type checker

Below is a complete checker for a small statically typed language: int, bool and str, variables with optional declared types, assignment, if, while, and typed functions. The program being checked is built directly as nodes (a parser would produce the same tree), and it contains seven deliberate mistakes.

Python A type checker with seven errors to find

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output against the program. Line 5 adds a str to an int. Line 7 uses an int where an if needs a bool, and line 8 stores a number in a bool variable. Line 10 passes a string to square, line 11 passes two arguments to a one-parameter function, line 12 uses an unknown name, and line 13 returns from outside any function.

Look at line 12 closely. missing - 1 produced exactly one message, not two. missing returned error, so the - rule saw it and stayed silent. And the Let on that line then stored error as the type of z, which keeps later uses of z quiet as well.

Two details about the structure. First, scopes are a plain stack of dictionaries, the scope chain from the previous lesson. A function pushes a scope holding its parameters, and a block pushes an empty one. Second, expressions return a type while statements check and return nothing, which mirrors the grammar: an expression has a type, a statement is merely allowed or not.

Equality, conversions and subtypes

The checker above demands exact equality: int is only ever compatible with int. Real languages relax this in controlled ways, and each relaxation needs a rule.

  • Widening conversions let a smaller numeric type flow into a larger one (int into float) because no information is lost. The reverse (float into int) usually needs an explicit cast.
  • Mixed arithmetic picks a result type, for example "if either side is float, the result is float".
  • Subtyping lets a value of a more specific type stand in where a general one is expected (a Dog where an Animal is wanted).

The common trick is to replace the equality test by a function called assignable(target, source) and to replace "both sides equal" by a promote(a, b) function that returns the common type or reports failure.

Python Widening conversions as small functions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Dropping these two functions into the checker is all it takes to support floats: Let and Assign would call assignable, and binary would call promote. Where a conversion actually happens, a good compiler also inserts an explicit conversion node into the tree, so the code generator later knows it must emit an int-to-float instruction. That is the "AST with a type on every expression" arrow in the diagram.

Writing good error messages

The checker's messages follow a few habits that are worth copying:

  • Name the operator or construct and the types involved: "operator '+' cannot be applied to str and int" beats "type error".
  • Give the expected and the actual type: "argument 1 of 'square' should be int, got str".
  • Include the position, and when you can, show the offending source line with a caret under it (you will do this for lexer errors in lexical errors and recovery).
  • Report the root cause, not its echoes, which is what the poison type is for.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main difference between static and dynamic type checking?

    A static checker examines the source at compile time and can reject every bad operation without running the program. A dynamic system tags values and checks them only when the operation executes.
  2. 2. In the checker, why does a node with the special error type make parent rules return error without reporting a message?

    One unknown name would otherwise make every expression built from it look wrong too. The poison type lets the compiler report the root cause once.
  3. 3. A type rule reads: if e1 : int and e2 : int then e1 < e2 : bool. What does the checker do for the expression 3 < true?

    The right operand has type bool, so the premise of the rule fails. In our language there is no conversion from bool to int, so the checker reports an error.
  4. 4. What does assignable('float', 'int') return in a language with widening conversions?

    Widening int to float loses no information, so the language allows it. The decision is made from the types alone, never from the run-time value.

Summary

  • Semantic analysis checks meaning that grammar cannot express; type checking is its main job.
  • Static typing checks at compile time and dynamic typing at run time; many languages combine both.
  • Type rules say "if the parts have these types, the whole has that type", and each rule becomes one branch in the checker.
  • A checker is a recursive walk over the AST: expressions return types, statements are checked for validity, and a scope stack supplies names and their types.
  • Collect all errors, use an error type to stop cascades, and always attach a position.
  • Conversions and subtyping replace plain equality with functions such as assignable and promote.

Next: Type Inference and Unification