Let’s Write a Type Checker

If you’ve ever wondered how your favourite compiler actually verifies your programs for type errors or how you might add type inference to a language like Java, then you will probably enjoy this session.

We will be showing how to write a type checker for a simple, hypothetical language using Scala. In order to save time, we will not define a syntax for the vehicle language, but rather work directly on its Abstract Syntax Tree (AST).

The language will support numbers, strings, records, arrays, variables and recursive functions.

Familiarity with Scala is not required. We will use a limited subset of Scala and explain its constructs as we use them. Knowing what anonymous functions or pattern matching are is a prerequisite though.

Audience Learnings

How a compiler performs type verifications, what are some common approaches and when it gets harder.

Structure

1. What’s a type checker
2. Introduce the small vehicle language that we’ll write a type checker for
3. Write the type checker
   3.1 Type check basic variables
   3.2 Type check functions
   3.3.Type check records
4. Closing remarks

Prerequisites

Knows what anonymous functions and pattern matching are.