Complete this assignment with the same team you worked with for Continuations (Written). You and your partner must each understand the answers to all the problems, so don't just split up the work.
Type Checker
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>} | {/ <expr> <expr>} | {zero? <expr>} | {bif <expr> <expr> <expr>} | <id> | {with {<id> : <type> <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>)where an
<id>
is not true, false, :, +, -, *, /, zero?,
bif, with, fun, nempty, ncons, nempty?, nfirst,
or nrest
.
In the surface syntax for types, base types are represented by
symbols, and the arrow type by a Racket 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:
-
zero?
consumes a number, and returnstrue
if it is0
,false
otherwise -
the test expression of
bif
("boolean if") must evaluate totrue
orfalse
-
ncons
consumes a number and a numeric list, and produces a numeric list
Design and Implement the Type Checker
You must write your type checker in #lang plai
.
Use this template to get started
started. The template defines the abstract syntax of the language (using define-type
). Do not modify these definitions.
Define the function
parse
, which consumes the concrete representation of a program, and returns its abstract syntax tree. To be precise,parse :: S-exp -> Expr
You may assume that the s-expressions provided to parse conform to the grammar and do not have free identifiers.Write down type judgments for the five numeric list constructs:
nempty
,ncons
,nempty?
,nfirst
, andnrest
. Turn in your work as a PDF (preferable) or text file (less preferable) with your code.-
Implement the function
type-of
, which consumes the abstract representation of a program (i.e. the result ofparse
) 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. To be precise,type-of :: Expr -> Type
However, if the program does have a type error,type-of
invokeserror
with an appropriate error message. For example:(type-of (parse '{+ 1 2}))
should produce(t-num)
, while:(type-of (parse '{3 4}))
should callerror
with some string, e.g. "Number is not a function".
Racket's (match ...)
Syntax
One last reminder about
Racket's
(match ...)
syntax. Use it! Love it! As always, it is
not required (but at this point highly encouraged for your own sanity).
Handin
Turn in two files:
typecheck.rkt
, your program.judgments.(pdf|txt|jpg)
, your type judgments.