Due: Thursday, March 2, 5pm via turnin (assignment
name hwk5), with one part due on paper as described below
Collaboration Policy:
Pairs Permitted
Warning: Doing this assignment instead of type inference will cap your course grade at B.
In this assignment, you will work with a typed language that includes numbers, booleans, conditionals, functions, and numeric lists. The concrete syntax for the language is given by the following BNF grammars:
<expr> ::= <num>
| true
| false
| {+ <expr> <expr>}
| {- <expr> <expr>}
| {* <expr> <expr>}
| {iszero <expr>}
| {bif <expr> <expr> <expr>}
| <id>
| {with {<id> <expr>} <expr>}
| {fun {<id> : <type>} : <type> <expr>}
| {<expr> <expr>}
| nempty
| {ncons <expr> <expr>}
| {nempty? <expr>}
| {nfirst <expr>}
| {nrest <expr>}
<type> ::= number
| boolean
| nlist
| (<type> -> <type>)
In the surface syntax for types, base types are represented by
symbols, and the arrow type by a Scheme list of three elements: the
type of the argument, the symbol ->, and the type
of the
result.
You have not implemented some of these constructs yet, but they should be familiar:
iszero consumes a number, and returns
true if
it is 0, false otherwise
bif ("boolean if") must
evaluate to true or false
ncons consumes a number and a numeric list, and
produces a
numeric list
Define the function parse, which consumes the
concrete representation of a program in the grammar given above
and returns its abstract syntax tree.
Write down type judgments for the five numeric list constructs:
nempty, ncons, nempty?,
nfirst, and nrest. Turn in hard copy
for this part to Prof Fisler.
Implement the function type-of, which consumes the
abstract representation of a program (i.e. the result of
parse) and an escape continuation that
accepts a string. If the program has no type errors,
type-of
returns the type of the program, using the names of the types
given in the grammar above. If the program does have a type
error,
type-of invokes the continuation with some string as
an argument. For example:
(let/cc esc (type-of (parse '{+ 1 2}) esc))
should produce number, while:
(let/cc esc (type-of (parse '{3 4}) esc))
would invoke esc with some string, (e.g. "Number is
not a function").
Submit a single Scheme file called checkers.ss containing your code and test cases for the parser and type checker. Submit the type judgments on paper to Prof Fisler, either in class or in the box on the wall outside her office door.
Nothing yet ...