Homework 29-31

This problem requires Lecture 28 and book section 4.2.

Exercise 4.8, p.142 - (180 minutes)
This problem will be spread over three assignments (HW 29-31). You don't have to submit anything until Homework 31 is due.

Some printed editions of the textbook show an error in the first rule:

    (type-of-expression «e₁» tenv) = t
    ...
    (type-of-expression «e_n» tenv) = t,    n > 0
  ___________________________________________________________
    (type-of-expression «listof (e₁,...,e_n)» tenv) = (listof t)

The red part of the above should not be in the book, so don't get confused by it. Use "list" as the keyword for an expression that makes a list from its arguments, and "listof" as the keyword for type-expressions.

This exercise requires that you complete the following:

• add the SIX new list-handling expressions to the grammar (follow the BNF given in the problem, plus do the car and cdr as described in the last paragraph of the problem in the text)
• add the new type-exp for lists to the grammar (follow the BNF given in the problem)
• add a new type for lists (change the define-datatype for type)
• change expand-type-expression to deal with the new list expression
• change type-to-external-form to return a printable form of the list type
• add new clauses to type-of-expression to handle the new list-handling expressions (follow the semantic rules in the problem)
• add new clauses to eval-expression to implement the new list-handling expressions

You may need to write some helper functions to assist with these.

Note that "null?" is a predicate that returns a boolean, and "emptylist [t]" is a constructor that returns an empty list.

The grammar in the book shows that emptylist requires a type parameter. In addition to answering the questions in the textbook, describe briefly how you might implement type-checking for emptylist without requiring a type parameter in the grammar.

IMPORTANT: To facilitate grading a type crash, we've added a variable arity function to the interpreter called type-crash.  You should call this function when the type error is detected.  The autograder is dependent on this type of crash, and will not award points otherwise.

Example Tests:

(run "list(1,2,3,4)") should return "(1 2 3 4)". This tests the evaluation part of the program.

(type-check "list(1,2,3,4)") should return "(listof int)". This tests the type-checking part of the program.

The type-checking interpreter.

Instructions on submitting homework is here

Last updated at 12:03 pm on Wednesday, November 17, 2004.