[SOLVED] EECS 321 Programming Languages: Homework 8

EECS 321 Programming Languages: Homework 8

Install the plai-typed language via DrRackets 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 arent 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.

Dont 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, dont 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 isnt 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
[email protected]