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>


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.


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.


  • 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]