COSC 152 Programming Languages

Fall 2007

Homework Assignment #9

Type Checking

Due: Friday, Nov 30, 12:00PM CST
Submit: E-mail electronic copy to professor, with a subject header "COSC 152 HW#9".
Work may be completed in pairs. Each team should submit only once. Be certain to put both team member names on work submitted. It would be courteous to carbon-copy your partner when e-mailing the final submission.

The Grammar

For this assignment, extend the grammar from HW #8 with simple type annotations as noted below:

<type>	::=	int
	|	bool
	|	( { <type> }*(*) ) -> <type>

A concrete function type would thus look like "(int) -> int" or "(int * int * int) -> bool".

Concrete types are to be added to the grammar in precisely three productions:

<expr>	::=	( lambda ( {<id> : < type>}* ) <expr> )
	|	( letrec ( { ( <id> : <type> ( lambda ( { <id> : <type> }*(,) ) <expr> ) )}* ) <expr> )
<stmt>	::=	proc <id> ( { <id> : <type> }*(,) ) <stmt>

Parser

Use the SLLGEN parser generator system to specify your lexical and syntax rules, and automatically build your parse function.

You will not be graded on an unparse function, but it is an invaluable debugging tool to have. Also, you will probably want a specific unparse-type function to convert your internal type representations back to concrete syntax.

Interpreter

With only minimal changes to your interpreter (essentially adding the type fields to the cases clauses for the three modified productions, and then ignoring them,) you should be able to run all previous testcases by adding the appropriate type annotations.

Type Checker

Write a type-check function that performs type checking on a parsed program and returns either the result type or a type error if one is found.

Notes:

The new language does not require type annotations for variables declared as part of a var or let block. Your type checker can assign proper types for all of these using simple type inference (no unification required.)

Your internal representation of types must be able to represent and match base types (int,bool,) function types (arrow types,) as well as a void type, the return type of all statements.

Because all statements have a return type of void, your type checker will return void as the result type of all properly formed programs in the full grammar. For development and testing purposes, you may find it helpful to temporarily pare down the grammar to the expression subset to debug at that level.

Emit useful error messages upon encountering a type error. Give at least the offending syntax, the expected type, and the found type.

Here is a good testcase for your type-checker and interpreter. It calculates and prints the greatest common divisor of the two initial variables.