Sequence 3.4 – Types verification and inference

Pablo Oliveira & Samuel Tardieu

Typing operations in the compiler

let var a : int := 3  /* Explicit type: int */
    var b := a + 4    /* Implicit type: int */
    var c := "Hello"  /* Implicit type: string */
in
  a + b + strlen(c)   /* Implicit type: int */
end

The types in Tiger

In our Tiger implementation, three types are used:

For example, function f below returns void (no value):

let var a := 0
    function f() = a := a + 1
in
  f(); f(); f(); a  /* Returns 3 */
end

The type checker

Type checking examples: expressions

Type checking examples: if/then/else

In Tiger, everything is an expression, including if/then/else.

if test then something else something_else

For example, the following expression returns the smallest value of a and b, a and b having the same type (int or string):

if a < b then a else b

Type checking examples: if/then

It is possible to omit the else part.

if test then something

In this case:

Note that in Tiger, () is of type void, so omitting the else part is equivalent to using else (). This substitution (adding else ()) can even be done in the parser to reduce the complexity of the various visitors.

Summarizing tests

Tiger is simple to type check

Tiger is a simple language to type check while walking the AST:

Example: type checking of assignment (:=)

void TypeChecker::visit(Assign &assign) {
  // Recursively type check left hand side of :=
  // (which is necessarily an identifier)
  assign.get_lhs().accept(*this);
  // Recursively type check right hand side of :=
  assign.get_rhs().accept(*this);
  // Check that both sides of := have the same type
  // and exit with an error otherwise.
  if (assign.get_lhs().get_type() !=
      assign.get_rhs().get_type())
    error(assign.loc, "Type mismatch in assignment");
  // The assignment itself returns no value,
  // you cannot do a := (b := c).
  assign.set_type(t_void);
}

Some languages are harder to type check

Conclusion