Type Checking

Reading

Files

The archive hw6.zip contains all the supporting files you need for this assignment. It is much more sparse than the previous two assignments, reflecting a greater development responsibility on your part.

Overview

Your job in this assignment is to implement a type checker for Tiger, by completing the Env and SemantV classes.

Setting Up the Project

Download the file hw6.zip [link], and unpack it in the src/tigerc directory of your project. You should have the following additions to the project:

tigerc
  --> src
        --> tigerc
               --> semant
                    -- Entry.java
                    -- Env.java      (partial)
                    -- SemantV.java  (partial)
                    -- Table.java
                    --> Types
                        -- ARRAY.java
                        -- ERROR.java
                        -- INT.java
                        -- NAME.java
                        -- NIL.java
                        -- PrimTy
                        -- RECORD.java
                        -- STRING.java
                        -- Type.java
                        -- VOID.java

Your Job

Complete the implementation of the SemantV and Env classes. Most of Env is done, but you should complete the bindings for the types and functions defined in the global environment.

No test file is included with this project distribution. You should construct your own (it's pretty easy to modify the parser test class for this).

Notes on the Design

Rules

Everything needed to implement the typechecker is given in Stephen Edward's brief language document. Here is a summary of the important details:

Simple Expressions

Integer and string constants have the obvious types. Statements that return no value have VOID type. The nil expression has an unspecified record type, NIL, as discussed above. All NIL types must ultimately be coerced to an actual record type.

Control flow

The break statement has VOID type, but the statement must be lexically enclosed in a loop body.

A sequencing expression, such as (f();g(y);x+y) has the type of the last expression in its sequence. The empty sequencing- expression, (), has type VOID.

An "if/then" statement "if (abc) then def" requires that abc have type INT and def have type VOID. The resulting type is VOID.

In a "if/then/else" expression, "if abc then def else xyz", abc must have type INT. The type of def must "match" the type of xyz. The result-type is the type of def (and xyz) after any nil- expressions have been "coerced".

In the indefinite loop expression, "while xxx do yyy", xxx must have type INT and yyy must have type VOID. The result-type is VOID

In the definite loop expression, "for xx := yy to zz do www", xx is implicity declared to have type INT. Inside of the body www, xx is in scope, but it may not be the target of an assignment expression. The expressions yy and zz must both have type INT. The body www must have type VOID. The result-type is VOID.

Variables

A variable declaration can be given with or without an explicit type ("var x : tt := hhh" or "var x := ggg"). The type of hhh must "match" tt. The result is that x is declared to have type tt (a binding of x to type tt is added to the environment). In the implicitly-typed form, ggg must not be nil, and it must not be of VOID type. The result is that x is declared to have the type of ggg

When a variable is used, its type is the type that it was declared to have (either implicitly or explicitly). This should be the most recent binding of the variable in the environment (venv, in the Env class).

Named type declaration

In the type alias declaration, "type a = b", the result is that a and b are declared to be the same type (i.e. a binding for a of type b is added to the environment).

In an array type declaration, "type A = array of bbb", type A is declared to be a unique ARRAY type (i.e. only one per let expression), whose base type is bbb.

In a record type declaration, "type R = {a:int,b:string,c:R}" type R is declared to be a (unique) RECORD type. The component names (a, b, c, in this example) must be unique within the record-type.

Types can be declared in mutual recursion, but each mutual recursion cycle must include a record or array type. For example,

type tree = { x:int, children:treelist }
type treelist = { head: tree, tail:treelist}

is legal, but

type a = b
type b = a

is not.

Assignment

The LHS-type must "match" the RHS-type, and must not be a for- loop index. The assignment expression itself has VOID type.

Operators in expressions

The binary operators +, -, *, /, & and | require their operands to have type INT. The result-type is also INT. The unary operator - requires its operand to have type INT; its result-type is INT.

The binary operators <, >, <= and >= require either that both operands be INT or that both operands be STRING. The result-type is INT.

The binary operators = and <> can be applied to any operands that "match" (including array and record types). The result-type is INT.

Arrays

In the array creation expression "A [i] of E", A must be an ARRAY type, i must have type INT, and E's type must "match" the base type of A. The result-type is that of A.

In array access "xyz[aaa]", xyz must have an ARRAY type and aaa must have type INT. The result is the base type of xyz's type

Records

In the record creation expression, "R {a = e1, b = e2, jj = e3}", R must be a RECORD type, and the declared components of R must be a, b and jj, in that order. R cannot have any other components. The declared type of component a of R must "match" e1; similarly for b and jj. The result-type is R.

Distinct record types may reuse the same names.

In a record access expression, "R.x", R must have a RECORD type, and x must be a declared component of that type. The resulting type is the declared type of the component x in R's type.

Functions

Groups of function declarations must be processed together, as they are considered to be defined in mutual recursion with each other. For a definition

function f(a:int,b:string):aType = body 

aType must "match" the type of body. If ":aType" is missing, then body must have a VOID type. The formal parameter names (a and b, in this example) must be unique within the parameter list.

In the function call "f(e1, e2, e3)", f must be a declared function for the current scope, and it must be declared to have three parameters; the first must match the type of expression e1, the second must match the type of e2, etc. . The result-type is the declared result-type of the function (which may be VOID)

Turn In:

Please put all files in a folder named "lab6", or something similar. If you can, I'd appreciate paper copies of the work, too.


Acknowledgements

The design of the tigerc.semant.types package is drawn almost enitrely from Andrew Appel's Types module, as given in the first edition of Modern Compiler Implementation in Java. Nearly all of the text in the Rules section above is quoted verbatim from notes written by Professor Steve Vegdahl of the University of Portland, and they are reproduced here with his kind permission.

John H. E. Lasseter