Work is to be completed in teams of two. 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
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).
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.
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:
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.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. 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))