Assignment 3, CSC430, Spring 2008
1 Guidelines
1.1 Contracts & Test Cases
For this and all remaining assignments, every function you develop must come with the following things:
A commented header line that expresses the result of the function in terms of its inputs, written in English. Be as precise as you can within the space of a line or two.
A commented contract line that gives the types of the inputs and the output. The contract should have the form <in-type> ... -> <out-type>. So, for instance, a numerical square function might have the contract line:
; number -> number
Test cases. A function without test cases is incomplete. Write the test cases first, please.
1.2 Handling errors
Your parser and interpreter must detect errors and explicitly signal them by calling (error ...). We will consider an error raised internally by Scheme to be a bug in your code.
For example, Scheme signals a "divide by zero" error if you attempt to evaluate (/ 1 0). Since we use Scheme’s division function to implement division in CFWAE, you may be tempted to leave it to Scheme to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Scheme’s division procedure.
Note that you may assume that your contracts are respected. That is, if your interp function’s contract indicates that it expects a CFWAE, you do not need to worry about miscreants that call it with a number or a string or another surprising value.
1.3 Language Level & File Format
For this assignment, you must develop your solutions using the Programming Languages: Application and Interpretation: Restricted PLAI Scheme language level. Your test cases must use the (test ...) or (test/exn ...) form.
Your solution should take the form of a single file. Solve each problem separately, ands make sure that each solution appears in a separate part of the file, with comments separating each problem’s solution.
Hand in your solution using the handin server. For help with the handin server, please see the course web page.
2 Extended Interpreter
Write a parser and interpreter for the CFWAE language we’ve discussed in class, extended with the language features described below. Your interpreter should have eager application semantics and use deferred substitution. Call the new language CFWAE (conditionals, functions, with, and arithmetic expressions).
The function parse must consumes an expression in the language’s concrete syntax and return the abstract syntax representation of that expression. The function parse must accept only expressions in the grammar of the language.
In addition to parse, you must implement the function interp, which consumes an abstract syntax expression (as returned by the parse function) and returns a CFWAE-value. Please include a contract for every function that you write and include test cases that amply exercise all of the code you’ve written.
3 Features to Implement
3.1 Booleans
Your language should now include the boolean values, true and false, and the boolean operators, and, or, and not.
From the parser’s standpoint, these names should all be treated as keywords. That is, the parser will recognize true, false, explicitly, and they will not be recognized as variable names.
From the interpreter’s standpoint, type errors are now possible! You must detect and signal these errors in the interpreter. In particular, the possible type errors are
applying a numeric operator to a boolean, and
applying a boolean operator to a number.
I recommend that you add booleans to your language and test this extension thoroughly before moving on.
3.2 Conditionals
Next, we want a conditional. We’ll use if, using the syntax described by the EBNF below. Note that ifexp has three branches:
a test expression that must evaluate to a boolean,
a then expression that is evaluated if the test expression evaluates to true, and
an else expression that is evaluated if the test expression evaluates to false.
Evaluation should signal an error for non-boolean test values.
In order to make the conditional useful, you must also add a binary equality operator for numbers, =. It should return true exactly when its two arguments are equal.
I recommend that you add if to your language and test this extension thoroughly before moving on.
3.3 Multi-argument fun
Extend the fun language feature described in lecture so that functions can accept a list of zero or more arguments instead of just one. All arguments to the function must evaluate with the same deferred substitutions. An example of a multi-argument fun:
{{fun {x y} {* x y}} 2 3}
This evaluates to 6.
As you did for multi-armed with, you must ensure that the arguments to a function have distinct names.
3.4 Syntax of CFWAE
The syntax of the CFWAE language with these additional features can be captured with the following EBNF:
CFWAE |
| = |
| num |
|
| | |
| true |
|
| | |
| false |
|
| | |
| {+ CFWAE CFWAE} |
|
| | |
| {- CFWAE CFWAE} |
|
| | |
| {* CFWAE CFWAE} |
|
| | |
| {/ CFWAE CFWAE} |
|
| | |
| {and CFWAE CFWAE} |
|
| | |
| {or CFWAE CFWAE} |
|
| | |
| {not CFWAE} |
|
| | |
| {= CFWAE CFWAE} |
|
| | |
| id |
|
| | |
| {if CFWAE CFWAE CFWAE} |
|
| | |
| {with {{id CFWAE}*} CFWAE} |
|
| | |
| {fun {id *} CFWAE} |
|
| | |
| {CFWAE CFWAE *} |
... where an id is not true, false, +, -, *, /, and, or, not, =, with, if or fun.
If a fun or a with expression has duplicate identifiers, we consider it a syntax error. Therefore, such errors must be detected in parse. For example, parsing the following expressions must signal errors:
{with {{x 10} {x 20}} 50} |
|
{fun {x x} 10} |
subsection{Syntax of CFWAE}
The syntax of the CFWAE language with these additional features can be captured with the following EBNF:
CFWAE |
| = |
| num |
|
| | |
| true |
|
| | |
| false |
|
| | |
| {+ CFWAE CFWAE} |
|
| | |
| {- CFWAE CFWAE} |
|
| | |
| {* CFWAE CFWAE} |
|
| | |
| {/ CFWAE CFWAE} |
|
| | |
| {and CFWAE CFWAE} |
|
| | |
| {or CFWAE CFWAE} |
|
| | |
| {not CFWAE} |
|
| | |
| {= CFWAE CFWAE} |
|
| | |
| id |
|
| | |
| {if CFWAE CFWAE CFWAE} |
|
| | |
| {with {{id CFWAE}*} CFWAE} |
|
| | |
| {fun {id *} CFWAE} |
|
| | |
| {CFWAE CFWAE *} |
... where an id is not true, false, +, -, *, /, and, or, not, =, with, if or fun.
If a fun or a with expression has duplicate identifiers, we consider it a syntax error. Therefore, such errors must be detected in parse. For example, parsing the following expressions must signal errors:
{with {{x 10} {x 20}} 50} |
|
{fun {x x} 10} |
4 Support Code
Your code must adhere to the following template, without any changes:
; represents a binding in a with expression |
(define-type Binding |
[binding (name symbol?) (named-expr CFWAE?)]) |
|
; represents an expression |
(define-type CFWAE |
[num (n number?)] |
[bool (b boolean?)] |
[binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)] |
[with (lob (listof Binding?)) (body CFWAE?)] |
[id (name symbol?)] |
[ifexp (tst CFWAE?) (then CFWAE?) (els CFWAE?)] |
[fun (params (listof symbol?)) (body CFWAE?)] |
[app (f CFWAE?) (args (listof CFWAE?))]) |
|
; represents an environment during evaluation |
(define-type Env |
[mtEnv] |
[anEnv (name symbol?) (value CFWAE-Value?) (env Env?)]) |
|
; represents a possible result of evaluation |
(define-type CFWAE-Value |
[numV (n number?)] |
[boolV (b boolean?)] |
[closureV (params (listof symbol?)) |
(body CFWAE?) |
(env Env?)]) |
|
; parse : expression -> CFWAE |
; This procedure parses an expression into a CFWAE |
(define (parse sexp) |
...) |
|
; interp : CFWAE -> CFWAE-Value |
; This procedure interprets the given CFWAE and produces a result |
; in the form of a CFWAE-Value (either a boolV, a closureV or a numV) |
(define (interp expr) |
...) |
5 Acknowledgments
Thanks to Shriram Krishnamurthi and Greg Cooper for these assignments.