| Code: | pa6.ss |
| Tests: | pa6-tests.ss |
The purpose of this assignment is to deepen your experience with more elaborate type checking. It is to be completed individually according to the course collaboration policy.
You can work on this assignment using DrScheme or MzScheme on ACS machines or on your own machine. Wherever you work, you first have to install the PLAI language. Once installed, it will work in both DrScheme and MzScheme, and you will find documentation for the PLAI language by selecting "Help Desk" from the Help menu in DrScheme, and then following the link labeled Programming Languages: Application and Interpretation under the heading "Languages".
Beginning with your type checker for the TFWAE language, you will extend it with the features described below. The resulting language will be called TRCFWAE, for "typed recursion, conditionals, functions, with, and arithmetic expressions."
Extend your parser and type checker to handle
the boolean type (in type expressions) and
the boolean-typed literals true and false.
Hint: Instead of handling the literals as special keywords, treat them as ordinary identifiers, but include type bindings for them in an initial type environment you use (instead of an empty environment) to check top-level expressions.
Add a predicate (that is, a boolean-valued function) is-zero
whose type is (number -> boolean).
Hint: Again, rather than modifying your parser,
just add a binding to the initial type environment.
Extend your type checker to handle if expressions.
Your parser should permit any 3 valid TRCFWAE expressions in an if,
but your type checker must
require the test expression to have type boolean,
and it must derive the type of the entire if expression
from the then and else expressions,
which are required to have the same type.
If either requirement is violated, the type checker must signal an error.
Note that although the concrete syntax uses if,
the TRCFWAE type variant is called if-true
because if would collide with a name in the PLAI language.
Add support for the typed rec construct
as introduced in the TRCFAE language in PLAI,
and correct type judgments on this construct as discussed in the text.
Per the discussion of rec in the chapter about recursion,
additionally require the cyclic binding to have a function type.
Note this is part of the contract
in the rec type variant of TRCFWAE,
but you'll need to signal an error with a more appropriate message.
Here is a BNF grammar for the TRCFWAE language:
<TRCFWAE> ::= <num>
| {+ <TRCFWAE> <TRCFWAE>}
| {with {<id> <TRCFWAE>} <TRCFWAE>}
| <id>
| {fun {<id> : <type>} : <type> <TRCFWAE>}
| {<TRCFWAE> <TRCFWAE>}
| <bool>
| {is-zero <TRCFWAE>}
| {if <TRCFWAE> <TRCFWAE> <TRCFWAE>}
| {rec {<id> : (<type> -> <type>) <TRCFWAE>} <TRCFWAE>}
<type> ::= number
| boolean
| (<type> -> <type>)
<bool> ::= true | false
You may earn bonus points by adding a guarded construct
with the following syntax where
the ellipsis (...) means
the previous item is present zero or more times:
{guarded {<TRCFWAE> <TRCFWAE>} ...
{otherwise <TRCFWAE>}}
Note exactly one otherwise clause is required at the end.
The parser should accept any valid TRCFWAE wherever that non-terminal appears,
but your type checker must require each test expression
(the first of a pair of TRCFWAEs in a clause) to have type boolean.
It must also require every then expression
(following a test expression or the otherwise keyword)
in the same guarded expression
to have the same type.
If either requirement is violated, the type checker must signal an error.
To earn the points you'll need to include a good set of tests demonstrating this construct is parsed and type-checked correctly.
As with previous assignments, you will need to think carefully about where your code might fail and add your own test cases to the test file. Your submission will be tested against a more comprehensive suite of tests than we gave you and we may also assess the quality of your tests.