COSC 3410 Programming Languages
Fall 2011
Homework Assignment #10
Type Checking
Due: Wednesday, Nov 30, 11:00am CST
Submit: Turn in
Scheme source files called "hw10.scm" (your interpreter) and "hw10-test.scm"
(a SchemeUnit testsuite for your type-checker)
using the
turnin command on
the
Systems Lab
machines. Include the names of all authors at the top of the files
in a comment block.
Work may be completed in pairs. Each team should have only one member turnin.
The Grammar
For this assignment, extend the grammar from
HW #9
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 scan&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.
- Type checking lists will require representing list types and factoring
the list operations out of the default environment and back into
the grammar. Note that empty-list will now require a type as
a parameter.
- 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
[Revised 2011 Nov 30 11:35 DWB]