Submit: Turn in two Scheme source files called hw8.scm and hw8-test.scm using the turnin command on morbius.mscsnet.mu.edu or one of the other Systems Lab machines.

Work is to be completed in teams of two. Be certain to include both teammates names in the file. You may submit multiple times, but only the last turnin will be kept. The automatic submission system will not accept work after the deadline. (If both partners are submitting work to TA-Bot -- which isn't a bad idea to get twice as much automated testing done during the week -- please be sure that one partner overwrites with a blank submission, or at least that the versions are identical. If the TA has to grade two separate versions of the project from a team, she is authorized to enter the lower of the two grades into the gradebook for that team!)

Include a comment block at the very top of each file that contains the following:

  ; COSC 3410 - Project [#]
  ; Explain briefly the functionality of the program.
  ; @authors [your names]
  ; Instructor [your instructor]
  ; TA-BOT:MAILTO [your email addresses]


Your source file should be in the EoPL dialect ("#lang eopl" at top of file) supported by DrRacket, and should not make use of non-standard features like comment boxes that produce an XML file rather than a flat text .scm file.

At the bottom of your hw8.scm, please include the line:

(provide scan&parse run typecheck)

Your hw8-test.scm file should be a SchemeUnit testsuite, as shown in class. You are only expected to have testcases for typecheck for this assisgnment.

The Grammar

Extend your grammar from the previous assignment to include simple type annotations as noted below:

<type-exp>	::=	int
		int-type-exp ()
	|	bool
		bool-type-exp ()
	|	( { <type-exp> }*(*) -> <type-exp> )
		proc-type-exp (arg-types result-type)
	|	listof <type-exp>
		list-type-exp (element-type)

A concrete function type would thus look like "(int -> int)" or "(int * int * int -> bool)".

Because type-checking of S-expression operators is more complex than the other primitives, it is necessary to pull the S-expression operators out of the default environment, and to put them back into the grammar. Restore productions to the grammar for the primitives cons, car, cdr, list, null?, and emptylist.

Concrete types are to be added to the grammar in precisely three productions:

<expr>	::=	( lambda ( {<identifier> : < type-exp>}* ) <expression> )
		proc-exp (vars types body)
	|	( letrec ( { ( <type-exp> < identifier> ( lambda ( { <identifier > : <type-exp>}* ) <expression> )) }* ) <expression> )
		letrec-exp (p-result-types p-names b-varss b-vars-types p-bodies letrec-body)
	|	emptylist <type>
		emptylist-exp (element-type)

This language is a close relative to the CHECKED language of EoPL Chapter 7, extensions from exercises 7.5 (multi-args), 7.6 (assignment), and 7.9 (listof types).

Interpreter

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 typecheck function that performs type checking on programs and returns either the result type or a type error if one is found.

typecheck : String → Type
Usage: (typecheck "pgm") = t, the resulting type of the program "pgm" or a type error if one is found.

Examples:
> (typecheck "print 5")
int
> (typecheck "if #t then print 5 else print 6")
void
> (typecheck "print (emptylist bool)")
(listof bool)
> (typecheck "print (list (lambda (x:int) (add x 1)) (lambda (y:int) (add y 2)) (lambda (z:int) (add z 3)))"
(listof (int -> int))
> (typecheck "print (letrec ((int fib (lambda (x:int) (if (lesser x 2) x (add (fib (sub x 1)) (fib (sub x 2))))))) (fib 1))"
int


Notes:

• The new language does not require type annotations for variables declared as part of a var or letblock. 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,) list types, and a voidtype, the return type of all statements.
  • For ease of testing, let us assume that the print statement does not return void type, but instead returns the type of the expression to be printed. Your test cases, therefore should concentrate on calling type-of on parsed programs consisting of a print statement.
  • 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 emptylist will now require a type as a parameter.
  • Because all statements (except print) have a return type of void, your type checker will return void as the result type of all other properly formed statements in the full grammar.
  • 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:
    print (letrec ((int gcd (lambda (a:int b:int) (if (equal a b) a (if (greater a b) (gcd (sub a b) b) (gcd a (sub b a))))))) (gcd 1755 364))