CS 4536 Homework 6: Type Checking

Due: Thursday, October 15, 5pm via turnin (assignment name hwk6), with one part due on paper as described below
Collaboration Policy: Pairs Permitted

Warning: Doing this assignment instead of type inference will cap your course grade at B.

The Assignment: Write a Type Checker

In this assignment, you will work with a typed language that includes numbers, booleans, conditionals, functions, and numeric lists. The concrete syntax for the language is given by the following BNF grammars:

   <expr> ::= <num>
            | true
            | false
            | {+ <expr> <expr>}
            | {- <expr> <expr>}
            | {* <expr> <expr>}
            | {iszero <expr>}
            | {bif <expr> <expr> <expr>}

            | <id>

            | {with {<id> <expr>} <expr>}
            | {fun {<id> : <type>} : <type> <expr>}
            | {<expr> <expr>}

            | nempty
            | {ncons <expr> <expr>}
            | {nempty? <expr>}
            | {nfirst <expr>}
            | {nrest <expr>}

   <type> ::= number
            | boolean
            | nlist
            | (<type> -> <type>)
  

You have not implemented some of these constructs yet, but they should be familiar:

• iszero consumes a number, and returns true if it is 0, false otherwise
• the test expression of bif ("boolean if") must evaluate to true or false
• ncons consumes a number and a numeric list, and produces a numeric list

1. Define the function parse, which consumes the concrete representation of a program in the grammar given above and returns its abstract syntax tree.

2. Write down type judgments for the five numeric list constructs: nempty, ncons, nempty?, nfirst, and nrest. Turn in hard copy for this part to Prof Fisler.

3. Implement the function type-of, which consumes the abstract representation of a program (i.e. the result of parse). If the program has no type errors, type-of returns the type of the program using the datatype in the starter file. For example,

   (type-of (parse '{+ 3 4}))

   should return (num-t). If the program does have a type error, raise an error message that contains the substring "expected". For example "type error: expected a number".

You do NOT need to implement an interpreter for this assignment.

What to Turn In

Submit two Scheme files: one called checker.ss containing your parse and type-of code and one called tests.ss containing your test cases. Submit the type judgments on paper to Prof Fisler, either in class or in the box on the wall outside her office door (submit these early if you are leaving campus before the deadline).

FAQ

Nothing yet ...