COSC 152 Programming Languages
Fall 2006
Homework Assignment #9
Type Checking
Due: Friday, Nov 17, 2:00PM CST
Submit: E-mail electronic
copy to professor, with a subject header "COSC 152 HW#9".
Work may be completed in groups of up to three students. Each group
should submit only once. Be certain to put all team member names on
work submitted. It would be courteous to carbon-copy your team mates
when e-mailing the final submission.
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> |
For this assignment, you may remove from the list of primitives
all operators dealing with S-Expressions. We will discuss list types
next week.
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.
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.
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.
Back