Version 2, 2002-11-09 01:30
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
-
the test expression of bif ("boolean if") must
evaluate to true or false
-
ncons consumes a number and a numeric list, and produces a
numeric list
You have three tasks:
-
Define the function parse, which consumes the concrete
representation of a program, and returns its abstract syntax tree.
Next, implement interp, which consumes the abstract
representation of a program, and produces its value as:
- a Scheme number,
- a Scheme boolean,
- a Scheme list, or
- the symbol '<procedure>
-
Write down type judgments for the five numeric list constructs:
nempty, ncons, nempty?, nfirst,
and nrest. You
should turn in hard copy to the cs173 handin bin.
-
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 external representation
of types given above. If the program does have a type error,
type-of invokes the continuation with a string containing
an error message. For example:
(let/cc esc (type-of (parse '{+ 1 2}) esc))
should produce number, while:
(let/cc esc (type-of (parse '{3 4}) esc))
might produce "cannot apply a number".
(This use of continuations is a primitive form of exceptions.)
FAQ
- What changed between versions 1 and 2?
Both type-of and interp should consume the abstract
representation of a program produced by the parse function.
Added braces to the concrete syntax of with.
|