Problem Set 7: Static Types

Due date: 11/1 @ 5:00 pm

This goal of this problem set is to understand what it takes to implement a statically and explicitly typed programming languages.

Use the Pretty Big language and require the EoPL language.

The goal is to design and implement a type system for this programming language:

 Block is: { Declarations* Statement+ }

 Declaration is: (Type Variable = Expression) 

 Type is one of: 
 -- bool 
 -- int 
 -- (Type -> Type)

 Variable is: alphanumeric sequence of characters 

 Expression is one of: 
 -- Variable 
 -- Number 
 -- (Expression + Expression) 
 -- (Expression > Expression) 
 -- (procedure (Parameter*) Block)
 -- (Expression Expression*)

 Parameter is: (Type Variable)

 Statement is one of: 
 -- (Variable = Expression) 
 -- (if Expression Block else Block)
 -- (while Expression Block)
 -- (return Expression)
    Constraint: a return-statement may occur 
    only inside of a procedure body

Problem 1:

Develop type checking rules for this language.

Convince yourself that they are sound.

Add a typed construct with unsound rules and demonstrate why the rules are unsound.

Problem 2:

Design and implement a type checker based on your sound rules from Problem 1.

Problem 3:

Design and implement a static rule checker that determines whether a program satisfies the constraint on return statements.