Skip to main content
Logo image

An Introduction to Imperative Programming

Sebastian Hack

Section 9.2 Type Checking

We have discussed the static semantics of C0 in Section 6.6. The static semantics for expressions is modelled as a relation that relates a type environment with expressions and a type. The static semantics for statements relates the type environment with statements. The static expression semantics is deterministic (or functional) which means that each type environment and each expression are related to exactly one type. This means that we can easily implement it as a method (in the interface Expression) that takes a type environment (here implemented by a class Scope which we will discuss below), an expression and delivers a type. Statements can be handled similarly: we implement the static statement semantics as a method (in the interface Statement) that takes a type environment as a parameter and check if a statement is well-typed. Both methods generate an error (using a Diagnostic object) that is shown to the user if the statement/expression is not well-typed. 
public interface Expression {
  Type checkType(Diagnostic d, Scope d);
}
The following code shows how type checking looks like for a simple add expression. It effectively implements rule [TArith] in Section 6.6. The code determines the types of the sub-expressions and computes the type of the expression based on this information.
public class Arith implements Expression, Locatable {
  // ...
  public Type checkType(Diagnostic d, Scope s) {
    Type l = getLeft().checkType(d, s);
    Type r = getRight().checkType(d, s);
    if (!l.isIntType())
      d.printError(this, "...");
    if (!r.isIntType())
      d.printError(this, "...");
    return Types.getIntType();
  }
}

Scope.

The type environment is implemented by the class Scope that maps an identifier to the AST node of its declaration in the current scope. Scope objects are created during the type checking process: Whenever we enter a new block, we create a new scope to collect the variable declarations in that scope (see rule [TBlock] in Section 6.6). To access the declarations of variables in outer scopes, a scope also links to its parent scope via a reference, making it effectively a stack of scopes. When type checking for this block is finished, we can pop the scope of the block from the scope stack. This corresponds naturally to the scope nesting of the programming language. The following code shows the handling of scopes when type checking a block:
public class Block implements Statement, Locatable {
  private final <Statement> body;

  public void checkType(Diagnostic d, Scope parent) {
    Scope scope = parent.newNestedScope();
    // local variables are added by declaration statements
    // in the statement list that constitutes the block's body
    for (Statement s : body)
      s.checkType(d, scope);
  }
}
When looking up the type of an identifier we have to consult the top scope if it has a declaration for that identifier. If so, we return it, if not, we look in the parent scope and repeat the process until we reach the root scope. If we do not find a definition for the identifier there, we have to signal an error because it means that an identifier is used without being declared.
{ // Scope 1
  int x; 
  int y;
  x = 1;
  y = 1;
  { // Scope 2
    int z;
    z = x + y;
  }
  { // Scope 3
    int y;
    y = x + 1;
  }
}
Run
Figure 9.2.1. A C0 with multiple nested blocks. For each block there is a type environment / scope. The nesting of the blocks corresponds to a tree of scopes. The type environment of a block only lists the innermost variable declarations and points to the next outer scope via a pointer. Note that each scope maps the declared identifier to the AST node of the declaration (which is not shown in the figure).
The following code shows a sample implementation for the class Scope.
public class Scope {
  private final Map<String, Declaration> table;
  private final Scope parent;

  public Scope() {
    this(null);
  }

  private Scope(Scope parent) {
    this.parent = parent;
    this.table  = new HashMap<String, Declaration>();
  }

  public Scope newNestedScope() {
    return new Scope(this);
  }

  public void add(String id, Declaration d)
    throws IdAlreadyDeclared {
    if (table.contains(id))
      throw new IdAlreadyDeclared(id);
    table.put(id, d);
  }

  public Declaration lookup(String id) throws IdUndeclared {
    // ...
  }
}
When visiting an AST node during type checking, it is advisable to store references to the significant declaration in the AST node that represents the using occurrence of an identifier. By this reference, the type can later on be looked up again. This may be important for successive passes like code generation which we discuss in the next section. In general, the AST node of the declaration stands for the variable itself and the compiler may want to associate other information with variables in later stages. The following code shows an example implementation of the AST node that represents the using occurrence of a variable.
public class Var implements Expression, Locatable {
  private String id;
  private Declaration decl = null;

  public Type checkType(Diagnostic d, Scope s) {
    try {
      this.decl = s.lookup(id);
      return this.decl.getType();
    }
    catch (IdUndeclared e) {
      d.printError(this, "Variable " + id + " not declared");
      return Types.getErrorType();
    }
  }
}
<Prev^TopNext>