CSE 130, Summer Session I, 2008

Programming Languages: Principles and Paradigms

Programming Assignment 5

The purpose of this assignment is to get hands-on experience with basic type checking. It is to be completed individually according to the course collaboration policy.

You can work on this assignment using DrScheme or MzScheme on ACS machines or on your own machine. Wherever you work, you first have to install the PLAI language. Once installed, it will work in both DrScheme and MzScheme, and you will find documentation for the PLAI language by selecting "Help Desk" from the Help menu in DrScheme, and then following the link labeled Programming Languages: Application and Interpretation under the heading "Languages".

Tasks

You will write a type checker for the language in PLAI called TFWAE, for "typed functions, with, and arithmetic expressions." Type checking depends on parsing, but not evaluation; this assignment does not involve an interpreter.

Here is a BNF grammar:

<TFWAE> ::= <num>
          | {+ <TFWAE> <TFWAE>}
          | {with {<id> <TFWAE>} <TFWAE>}
          | <id>
          | {fun {<id> : <type>} : <type> <TFWAE>}
          | {<TFWAE> <TFWAE>}

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

Note TFWAE does not permit multiple bindings in with expressions, nor multiple parameters in fun expressions; you must comply with these two simplifications (compared to earlier assignments). TFWAE also does not contain the if0 construct or the generalized binary operators, but you may permit these if you like.

Type Equivalence

You are provided a Type datatype corresponding to the simple type expressions defined (recursively) in the grammar. Your first task is to define a Scheme function type=? that takes two Types and gives #t if they are equivalent, or #f otherwise.

Without a facility for user-defined types, there is no distinction between structural equivalence and name equivalence; the only name for a type in TFWAE is a type expression.

Parsing Type Expressions

Define a Scheme function parse-type that takes an s-expression and gives a corresponding Type if its actual parameter is a valid type expression, or otherwise signals an error with an appropriate message.

Parsing TFWAE Expressions

Define a Scheme function parse that takes an s-expression and gives a corresponding TFWAE or signals an error with an appropriate message. This parser should call parse-type where type expressions are expected.

Type Judgments

Define a Scheme function type-of that takes a TFWAE and gives its Type or signals a type error.

To simplify type-of, define another function that takes a TFWAE and a type environment (whose representation you define) and attempts to determine the TFWAE's Type under that environment. This function will call itself recursively, adding to the type environment for sub-expressions where appropriate. Then type-of can simply call this function, supplying an empty type environment.

Bonus Points

You may earn bonus points by correctly supporting the if0 construct and generalized binary operators, and demonstrating this with tests you supply.

Testing

As with previous assignments, you will need to think carefully about where your code might fail and add your own test cases to the test file. Your submission will be tested against a more comprehensive suite of tests than we gave you and we may also assess the quality of your tests.

Submitting Your Work

• Copy your files to an ACS GNU/Linux machine (if they're not already there).
• Before submitting your work, it's a good idea to make sure it runs in MzScheme on an ACS GNU/Linux machine and passes all the tests we've given you.
• In the directory where your files are, run bundle-pa5 and follow the directions. (If you haven't run prep cs130u yet, you'll have to do that first.)
• You can overwrite earlier submissions until the deadline, so submit early and often!
• After the deadline the bundle script will no longer work. Late submissions will be accepted only by arrangement with the instructor.