2.8 Extended Interpreter
You must complete this assignment by yourself.
You must submit this in an archive named "xinterp.zip".
2.8.1 FWAE
Write a parser and interpreter for the FWAE language from class.
2.8.2 CFWAE
You must submit this in a file named "xinterp.ss".
Extend FWAE 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).
2.8.2.1 Syntax
The syntax of the CFWAE language with these additional features can be captured with the following grammar:
| CFWAE | = | number | ||
| | | (+ CFWAE CFWAE) | |||
| | | (- CFWAE CFWAE) | |||
| | | (* CFWAE CFWAE) | |||
| | | (/ CFWAE CFWAE) | |||
| | | id | |||
| | | (if0 CFWAE CFWAE CFWAE) | |||
| | | (with ([id CFWAE] ...) CFWAE) | |||
| | | (fun (id ...) CFWAE) | |||
| | | (CFWAE ...) |
where number is a Scheme number and id is not '+, '-, '*, '/, 'with, 'if0, or 'fun.
| (with ([x 10] [x 20]) 50) |
| (fun (x x) 10) |
2.8.2.2 Template
Your code must adhere to the following template, without any changes:
| (define-type Binding |
| [binding (name symbol?) (named-expr CFWAE?)]) |
| (define-type CFWAE |
| [num (n number?)] |
| [binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)] |
| [with (lob (listof Binding?)) (body CFWAE?)] |
| [id (name symbol?)] |
| [if0 (c CFWAE?) (t CFWAE?) (e CFWAE?)] |
| [fun (args (listof symbol?)) (body CFWAE?)] |
| [app (f CFWAE?) (args (listof CFWAE?))]) |
| (define-type Env |
| [mtEnv] |
| [anEnv (name symbol?) (value CFWAE-Value?) (env Env?)]) |
| (define-type CFWAE-Value |
| [numV (n number?)] |
| [closureV (params (listof symbol?)) |
| (body CFWAE?) |
| (env Env?)]) |
| ; parse : expression -> CFWAE |
| ; This procedure parses an expression into a CFWAE |
| (define (parse sexp) |
| ....) |
| ; interp : CFWAE Env -> CFWAE-Value |
| ; This procedure interprets the given CFWAE in the environment |
| ; and produces a result in the form of a CFWAE-Value |
| (define (interp expr env) |
| ....) |
2.8.2.3 Conditionals
The semantics of (if0 test then else) is: if the test evalutes to zero, then the entire expression evalutes to the result of then, otherwise, it evalautes to else. Evaluation should signal an error for non-numeric test values.
You will find the Scheme function zero? useful in interp.
2.8.2.4 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.
You will want to write a function called extend-Env that extends an environment (via anEnv) many times for each binding it is given.
2.8.2.5 Tests
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.
If you are not sure if an error raised by your program constitutes a bug, search the Help Desk for test/exn. test/exn tests for errors, but only succeeds on errors that you explicitly signal.
You should have parse tests for all allowable syntactic forms: including syntax that results in errors when run. You should also include parse tests that find all erroneous forms of syntax.
You should have interp tests that demonstrate you recreate the behavior of substitution from Rudimentary Interpreter, in addition to new tests to demonstrate correct (and erroneous) usage of if0, function definition, and function application.
2.8.3 CFWAE (Lazy)
You must submit this in a file named "xinterp-lazy.ss".
Copy your CFWAE interpreter into a file named "xinterp-lazy.ss" and modify it so that it has lazy application semantics. (We strongly recommend that you not attempt this part of the assignment until you’ve gotten the first interpreter done, thoroughly tested, and debugged!)
2.8.3.1 Template
Your code must adhere to the following template, without any changes:
| (define-type Binding |
| [binding (name symbol?) (named-expr CFWAE?)]) |
| (define-type CFWAE |
| [num (n number?)] |
| [binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)] |
| [with (lob (listof Binding?)) (body CFWAE?)] |
| [id (name symbol?)] |
| [if0 (c CFWAE?) (t CFWAE?) (e CFWAE?)] |
| [fun (args (listof symbol?)) (body CFWAE?)] |
| [app (f CFWAE?) (args (listof CFWAE?))]) |
| (define-type Env |
| [mtEnv] |
| [anEnv (name symbol?) (value CFWAE-Value?) (env Env?)]) |
| (define-type CFWAE-Value |
| [numV (n number?)] |
| [closureV (params (listof symbol?)) |
| (body CFWAE?) |
| (env Env?)] |
| [exprV (expr CFWAE?) (env Env?)]) |
| ; parse : expression -> CFWAE |
| ; This procedure parses an expression into a CFWAE |
| (define (parse sexp) |
| ....) |
| ; interp : CFWAE Env -> CFWAE-Value |
| ; This procedure interprets the given CFWAE in the environment |
| ; and produces a result in the form of a CFWAE-Value |
| (define (interp expr env) |
| ....) |
2.8.3.2 Tests
You should be able to run all the tests from "xinterp.ss". It is considered a “special” test case to show that your code is lazy. There are two good ways to do this. You will get points for both.