Type Inference, written in TypeScript

Representing types

We need a language to describe types, just like ESTree is a language to describe programs. So we need a meta-type, to distinguish the different types. Let us call these meta-types kinds. All types collectively are considered members of Type.

• Primitive types:

{ "kind" : "primitive",
  "name" : "number"
}

{ "kind" : "primitive",
  "name" : "integer"
}

Type inferencers are allowed and encouraged to infer integer types whenever possible.

{ "kind" : "primitive",
  "name" : "bool"
}

{ "kind" : "primitive",
  "name" : "undefined"
}

• Type variables:

{ "kind" : "variable",
  "name" : string
 }

• Function types:

{ "kind" : "function",
  "argumentTypes" : Type []
  "resultType" :  Type
}

• List types:

{ "kind" : "list",
  "elementType" : Type
}

• Pair types:

{ "kind" : "pair",
  "headType" : Type,
  "tailType" : Type
}

Representing syntax trees

To represent inferred types, let's put them on the "inferredType" field:

1 + 1

represented as

{
"type": "BinaryExpression",
"inferredType": { "kind" : "primitive", "name" : "number" },
"start": 0,
"end": 5,
"left": {
  "type": "Literal",
  "inferredType": { "kind" : "primitive", "name" : "number" },
  "start": 0,
  "end": 1,
  "value": 1,
  "raw": "1"
},
"operator": "+",
"right": {
  "type": "Literal",
  "inferredType": { "kind" : "primitive", "name" : "number" },
  "start": 4,
  "end": 5,
  "value": 1,
  "raw": "1"
}
}