EECS 321 Programming Languages: Homework 8
Install the plai-typed language via DrRacket’s File | Install Package … menu item. Type plai-typed into the “Package Source” box and click “OK”.
You can find documentation for PLAI typed by going to the main documentation page for your installation (type f1 in DrRacket and then click the “Up” links until there aren’t any more) and following the “PLAI Typed Language” link you find there.
Start your program with #lang plai-typed.
Part 1 – True, False, equals, and if
Add support for true, false, {= … …}, and {if … … …} expressions, where = accepts only numbers (and produces a boolean), and if requires a boolean expression for the test and that the “then” and the “else” branches have the same type.
Don’t write a parser; just test directly on abstract syntax.
Part 2 – Typed Lists
Add support for lists to the language by extending it with the following expressions:
<TFAE> = …
| {cons <TFAE> <TFAE>}
| {first <TFAE>}
| {rest <TFAE>}
| {nil <type>}
| {empty? <TFAE>}
<type> = number
| bool
| {<type> -> <type>}
| {listof <type>}
All of which work as they do in Racket, with the exception of nil, which is just the empty list, but must be annotated with a type. For example, the type of {nil num} is {listof num}.
Require that all elements of a list have the same type, which you can ensure when type-checking cons.
It might seem unusual that nil must come with a type. Since the empty list can have many types, the programmer has to explicitly pick the one that agrees with the rest of the list.
Again, don’t bother with a parser and just use the abstract syntax directly.
Part 3 – Typing Rules
Here are the precise typing rules for the new constructs
Part N – Handin instructions
You must use the following definitions of types and expressions (you are free to make other types that you use internally).
(define-type TFAE
[num (n : number)]
[bool (b : boolean)]
[add (l : TFAE) (r : TFAE)]
[sub (l : TFAE) (r : TFAE)]
[eql (l : TFAE) (r : TFAE)]
[id (name : symbol)]
[ifthenelse (tst : TFAE) (thn : TFAE) (els : TFAE)]
[fun (arg : symbol) (typ : Type) (body : TFAE)]
[app (rator : TFAE) (rand : TFAE)]
[consl (fst : TFAE) (rst : TFAE)]
[firstl (lst : TFAE)]
[restl (lst : TFAE)]
[nil (typ : Type)]
[mtl? (lst : TFAE)])
(define-type Type
[numT]
[boolT]
[arrowT (dom : Type) (codom : Type)]
[listT (typ : Type)])
Your program must define this function:
type-check-expr : TFAE -> Type
If type-check-expr is passed an expression that isn’t well-typed, then it should fail with an exception containing the string: type-error. Note that free variables count as type errors, so must also raise errors with the string type-error.
Last update: Tuesday, February 28th, 2017
stamourv@eecs.northwestern.edu