CSE411: Introduction to Compilers

Type Checking 2

Jooyong Yi (UNIST)

Type Derivation

-----------------   --------------------
Γ[x:int] ⊢ x:int     Γ[x:int] ⊢ 10:int
-------------------------------------------
         Γ[x:int] ⊢ x = 10;
    ------------------------------
         Γ ⊢ int x; x = 10;

Type Rules

-----------------
  Γ ⊢ n: int        # n is an integer constant

--------------
 Γ[x:τ] ⊢ x:τ

      Γ[I:int] ⊢ S
----------------------
      Γ ⊢ int I; S            

   Γ ⊢ I:τ  Γ ⊢ E:τ       # premises
----------------------
      Γ ⊢ I = E           # conclusion  

• Γ: A typing environment

Review: Visitor Pattern

public class PrettyPrinter implements TreeVisitor {
    @Override
    public boolean visit(ReturnStatement node) { 
        this.buffer.append("return");//$NON-NLS-1$
        if (node.getExpression() != null) {
            this.buffer.append(" ");//$NON-NLS-1$

            // visit(node.getExpression()); cannot perform what we want
            node.getExpression().accept(this); // perform dynamic dispatch

        }
        this.buffer.append(";\n");//$NON-NLS-1$
        return false;
    }
    ...
}

Review: Visitor Pattern

public class BinaryExpression extends Expression {

    @Override
    void accept(TreeVisitor visitor) {
        visitor.visit(this); // Note: the static type of this: BinaryExpression
    }
}

public class PrettyPrinter implements TreeVisitor {
    ...
    public boolean visit(BinaryExpression node) { ... }
    ...    
}

Type Rule via Visitor Pattern

-----------------
  Γ ⊢ n: int        # n is an integer constant

class Visitor extends ASTVisitor {
    ...
    public boolean visit(final NumberLiteral node) {
      setResult(node, this.tf.Int);
      return false;
    }

    public boolean visit(final Assignment node) {
      ...
      node.getRightHandSide().accept(this);
      final Type rhsType = getResult();
      ...      
    }
    ...
}

Type Rule via Visitor Pattern

   Γ ⊢ I:τ  Γ ⊢ E:τ       # premises
----------------------
      Γ ⊢ I = E           # conclusion  

class Visitor extends ASTVisitor {
  ...
  public boolean visit(final Assignment node) {
    node.getLeftHandSide().accept(this);
    final Type lhsType = getResult();
    node.getRightHandSide().accept(this);
    final Type rhsType = getResult();
    if (lhsType != rhsType) {
      throw new Error(node, "Type mismatch in \"" + node + "\": " + lhsType + " = " + rhsType);
    }
    return false;
  }
  ...
}  

Looking Up Typing Environment

--------------
 Γ[x:τ] ⊢ x:τ

class Visitor extends ASTVisitor {
    ...
    public boolean visit(final SimpleName node) {
      ...
      final Object o = this.symbolMap.get(node); // Consult the typing environment
      if (o instanceof SingleVariableDeclaration) {
        setResult(node, convertType(node, svd.getType()));
      }
      ...
    }

    public boolean visit(final Assignment node) {
      ...
      node.getLeftHandSide().accept(this);
      final Type lhsType = getResult();
      ...      
    }
    ...
}

Typing Environment: Symbol Table

• The typing environment is often called a symbol table.
• A mapping from identifiers to their types (and also program locations).

Symbol Table Construction via Visitor Pattern

      Γ[I:int] ⊢ S
----------------------
      Γ ⊢ int I; S            

// Visitor to construct a symbol table
class Visitor extends ASTVisitor {
  ...
  public boolean visit(final VariableDeclarationStatement node) { // e.g., node: int x;
    final VariableDeclarationFragment vdf = (VariableDeclarationFragment) node.fragments().get(0); // e.g., vdf: x
    final String name = vdf.getName().getIdentifier();
    if (this.nameMap.containsKey(name)) {
      // duplicate declaration
      throw new Error(...);
    }
    this.nameMap.put(name, node);
    return false;
  }

  public boolean visit(final SimpleName node) {
    final String varName = node.getIdentifier();
    if (this.nameMap.containsKey(varName)) {
      this.result.put(node, this.nameMap.get(varName)); // result: symbol table
    } else {
      throw new Error(...);
    }      
    return false;
  }
  ...
}  

Scope

  static void foo() {
    int x;
    boolean y;
    // Symbol Table: {x ↦ int, y ↦ boolean}
    x = 10;
    y = true;
  }

  static void bar() {
    boolean x;
    int y;
    // Symbol Table: {x ↦ boolean, y ↦ int}
    x = true;
    y = 10;
  }

Considering Scope

// Visitor to construct a symbol table
class Visitor extends ASTVisitor {
  ...
  public boolean visit(final MethodDeclaration node) {
    ...
    node.getBody().accept(this);

    for (final String name : this.localNames) {
      this.nameMap.remove(name); // remove local variables from the current context
    }
    this.localNames.clear();
    return false;
  }

  public boolean visit(final VariableDeclarationStatement node) { // e.g., node: int x;
    final VariableDeclarationFragment vdf = (VariableDeclarationFragment) node.fragments().get(0); // e.g., vdf: x
    final String name = vdf.getName().getIdentifier();
    ...
    this.localNames.add(name); // ADDED
    this.nameMap.put(name, node);
    return false;
  }
  ...
}  

Nested Scope

// 𝜎_0={𝑚1↦…}
static void m1() {
    int x;
    boolean y;
    // 𝜎_1= 𝜎_0 + {x ↦int, y ↦ boolean}
    x = 1;
    y = true;
    {
       int y; boolean x;
       // 𝜎_2 = 𝜎_1 + {y ↦int, x ↦ boolean}
       y = 2;
       x = false;
    }
    // 𝜎_1
    x = 10;
}

Static Nested Scope Rules

Static Nested Scope Rules

• A2 shadows A1
• A3 shadows A2, A1

Symbol Table with Chaining

Symbol table acts like a stack

Try this

#include <iostream>

int main()
{
    std::cout << "The sum of 3 and 4 is: " << add(3, 4) << '\n';
    return 0;
}

int add(int x, int y)
{
    return x + y;
}

Why Error?

#include <iostream>

int main()
{
    std::cout << "The sum of 3 and 4 is: " << add(3, 4) << '\n';
    return 0;
}

int add(int x, int y)
{
    return x + y;
}

Test.cpp: In function ‘int main()’:
Test.cpp:5:47: error: ‘add’ was not declared in this scope
    5 |     std::cout << "The sum of 3 and 4 is: " << add(3, 4) << '\n';
      |                                               ^~~

How to Fix?

• First declare the function before using it. Why does it work?

#include <iostream>

int add(int x, int y)
{
    return x + y;
}

int main()
{
    std::cout << "The sum of 3 and 4 is: " << add(3, 4) << '\n';
    return 0;
}

Another Way to Fix

• Forward declaration

#include <iostream>

int add(int, int); // forward declaration

int main()
{
    std::cout << "The sum of 3 and 4 is: " << add(3, 4) << '\n';
    return 0;
}

int add(int x, int y)
{
    return x + y;
}

Multi-Pass Compilation

• Languages like Java do not need forward declaration.
• Multi-pass compilation
  • Process the source code or AST multiple times.

Multi-Pass Compilation

• Languages like Java do not need forward declaration.
• Multi-pass compilation
  • Process the source code or AST multiple times.
• Downside: slower than a one-pass compilation.