Create a simple type checker

I will be going through the implementation of a simple type checker in JavaScript.

The type checker is divided into four parts:

• types
• context
• printer
• typecheck

Types

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
        
      

Context

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
        
      

Printer

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)
        
      

Type checker

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.

Type matching implementation

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:

• OCaml has shape based typing and subtyping of records
• Golang has an automatic interface implementation
• JavaScript has rules to implicit coerce during the matching

Type aliases

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.