I will be going through the implementation of a simple type checker in JavaScript.
The type checker is divided into four parts:
typescontextprintertypecheck
The type module provides a mapping between the type found in the source and the internal representation of those types. It also exposes a match function which is the actual type matching algorithm (implementation will be detailed later).
It has the following interface:
type type = string
const string: type = 'string';
const bool: type = 'bool';
// Represents an unknow type
const empty = ''
function annotationToType(type: string): type
function match(l: type, r: type): boolean
The context module is a set of utility functions for creating and managing the environment or env for short.
The environment contains all the type informations, every time we declare a new type or need to resolve a type we are going to ask the env. I represented it as a tuple of type: (Name, Type), where both the Name and the Type are strings.
For the sake of simplicity, the env only keeps track of local types from within the current scope.
It has the following interface:
type type = string
type pair = [string, type];
type env = Array;
function make(): env
function find(env: env, name: string): type
function add(env: env, name: string, type: type): env
Before we dive into the type checker, the printer module is just a representation of the internal state for humans.
It has the following interface:
// Directly writes to the console
function printTypes(root: Object)
The module holds the actual type checking logic, but don't worry it really simple.
In order to match types and declare them you need to traverse the AST of your program, I will be using Babel for this example.
First, I want to visit every variable declarations in my program.
This is my sample program:
var a: string
and here is the logic of the type checker:
VariableDeclarator({node}) {
let type = empty
// The type annotation (string in our example)
const typeAnnotation = node.id.typeAnnotation.typeAnnotation
// Search in built-in types
// In that case it will end here since string is a build-in type
type = annotationToType(typeAnnotation.type)
if (type === empty) {
// Continue, search in the env
// Maybe it's a type that we already know
type = context.find(env, node.id.name)
}
// Abort if it's unknown
// In most type system this will result in a empty type in order to infer it or
// to simply show all errros at once
if (type === empty) {
throw 'Unknown type for var'
}
// At this point we know the type of the variable, we can store it into our env
context.add(env, node.id.name, type)
}
Now that we can identify the type of a given variable, we can write our type matching logic.
For the sake of simplicity, I will check all variable assignments. It does work similarly for function calls.
This is my sample program:
var a: string
var b: boolean
// Assignation here
a = b
Let's see if we can catch the error in the program.
AssignmentExpression({node: {left, right}}) {
// left is a
// right is b
// We need to resolve both types
const leftType = context.find(env, left.name)
const rightType = context.find(env, right.name)
// We the case we don't know the types, abort and throw
// This is more a internal failure than a type error, normally we should already
// know every types
if (leftType === empty) {
throw 'Left side has an unknown type'
}
if (rightType === empty) {
throw 'Right side has an unknown type'
}
// Test if the types can match
if (!types.match(leftType, rightType)) {
throw 'Impossible assignment ' + leftType + ' != ' + rightType
}
}
As you would expect when running the type checker against the sample program, we have the following type error: Impossible assignment string != bool.
The matching algorithm was simplified, here is the implementation:
function match(l: type, r: type): boolean {
return l === r
}
In some languages the matching algorithm would be much more complex:
It's common in a type system to be able to declare your own types. Here is an example for type aliases.
This is our sample program:
type maybeTrueOrFalse = boolean
var a: maybeTrueOrFalse
var b: boolean
a = b
and here is the logic:
TypeAlias({node: {right, id}}) {
// Right is boolean
const type = annotationToType(right.type)
if (type === empty) {
throw 'Unknown type in type alias'
}
// Id is maybeTrueOrFalse
context.add(env, id.name, type)
}
It's simple since we only need to add the new type in our environment and add some code to lookup the name into the env.