Assignment 3: Static Semantics

Due: 10:00 pm, Monday, October 18.

Project 3 is to read chapter five of the text and build a static-semantics checker for Appel's Tiger language.

Your code should perform the static-semantics checks decribed in Chapter 5:

• type-check the program
• check for "break" statements that occur out of scope.

Your semant module should export a function with this signature:

transProg : Absyn.exp -> unit

that checks an AST and outputs error messages if anything is wrong. (Why is our type-checker called transProg rather than something like typeCheck? Because we'll be extending it in project 4 to type-check and translate the AST to our intermediate representation.)

You will find a structure Types defining a datatype to represent Tiger types in $TIGER/chap5/types.sml. If you wish to use the type lattice I sketched out in my types lecture for your compiler, you will have to extend Appel's definition to include a "bottom" type (compatible with everything) for the type of break expressions. This will permit your typechecker to pass expressions such as

if y = 0 then break else x / y
x / (if y = 0 then break else y)
a[break] := x
x := break

This is a permitted extension to the compiler. It's not required, however.

You should submit:

• A semant.sml file containing your code
• Any other source files you wrote to support your checker
• Your sources.cm file
• A text file describing
  • The members of your team
  • Anything you think is of interest about your code.

Words to the wise:

• Appel's advice on pages 121/122 about breaking the work into a part A and a part B is good advice.
• One thing I found confusing when I wrote my checker was the fact that there are two "ty" types:

  Types.ty

  These are semantic values—they represent the various types found in Tiger. This is carefully designed to assist the type-checking process, e.g. handling circularities.

  Absyn.ty

  These are syntactic values—they represent the notation in Tiger for describing types.

  Obviously, we can map any Absyn.ty chunk of Tiger type syntax to a Types.ty value. But don't confuse the two different datatypes. Anytime you must handle a description of a Tiger type, be clear in your mind: are you handling a semantic value or a chunk of syntax?
• This is a significant piece of code. I found it harder than the parser as a straight-up programming effort.
• The single trickiest part of the typechecker is dealing with Tiger's mutually recursive type declarations. You have to rule out loops—that is, this is probably not a useful set of type declarations:

  type a = b
  type b = a
  

  but this is:

  type a = b
  type c = int
  type b = c
  

  I know of at least two good ways to do this, and many more bad ways. Give it some thought.

CS4410