CS 7400 Machine Problem 6: Extending a Type Inferencer

Out: October 29, 2009

Due: November 5, 2009

FAQs for this assignment are collected here. You should check this archive before asking a question. These refer to a previous version of this problem set, but should still be applicable to you.

For this problem, you will modify the interpreter and type inferencer, interps/inferred.

1. (15 points) Do exercise 7.25 in EOPL3 (Add lists to INFERRED.) Note that this problem refers to exercise 7.9. For this you will add to the grammar of INFERRED the productions

   Type ::= listof Type
   Expression ::= list ( Expression* )
   Expression ::= cons ( Expression, Expression)
   Expression ::= null? (Expression)
   Expression ::= car (Expression)
   Expression ::= cdr (Expression)
   Expression ::= emptylist
   

   The rules for list, cons, and null? are given in the book on page 247. The rule for emptylist should be:

   (type-of emptylist tenv) = listof t
   

   (not what's in the book, which is for CHECKED). For this problem you must
   1. Write out rules like those on page 247 for the remaining constructs (null?, car, and cdr).
   2. Write equations like those on pp 249-250 for each of the 6 new kinds of expressions. You should check these with Aaron before getting too far into your implementation.
   3. Then add the new types and the new equations to the implementation of INFERRED.
2. (5 points) Do exercise 7.28 in EOPL3 (polymorphic let via substitutition). Note that this is a different algorithm than the one discussed in class.
3. (10 points) Finish the implementation of the algorithm for polymorphic let discussed in class.

As usual, you should turn in 3 sets of modules, in directories named mp6-1, mp6-2, and mp6-3.

Observe that the tests in interps/inferred/tests.scm are not very good. You should add additional tests to better exercise the inferencer, and to demonstrate the extensions you write for this problem. Your tests must include both programs that pass your type checker and those that fail, to show that it rejects all the programs it should. Your tests should include running the programs, not just typechecking them.