3.8 Extended Interpreter
You must complete this assignment by yourself.
You must submit this in an archive named "xinterp.zip". This archive must contain a folder named "xinterp". This folder must contain all the files specified below. You must attach "xinterp.zip" to an email whose subject is "BYU - Fall 2010 - CS 330 - xinterp" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 9/30. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.
You must complete this assignment using a specific language. Choose Determine language from source in the DrRacket menu, then writeas the first line of your program, overwritting the default #lang at the top of the file.
3.8.1 FWAE
Write a parser and interpreter for the FWAE language from class.
3.8.2 CFWAE
You must submit this in a file named "xinterp.rkt".
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).
3.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 CFWAE ...) |
where number is a Racket number and id is not '+, '-, '*, '/, 'with, 'if0, or 'fun.
| CFWAE | = | number | ||
| | | (list '+ CFWAE CFWAE) | |||
| | | (list '- CFWAE CFWAE) | |||
| | | (list '* CFWAE CFWAE) | |||
| | | (list '/ CFWAE CFWAE) | |||
| | | id | |||
| | | (list 'if0 CFWAE CFWAE CFWAE) | |||
| | | (list 'with (list (list id CFWAE) ...) CFWAE) | |||
| | | (list 'fun (list id ...) CFWAE) | |||
| | | (list CWFAE CWFAE ...) |
| (with ([x 10] [x 20]) 50) |
| (fun (x x) 10) |
3.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) |
| ....) |
3.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 Racket function zero? useful in interp.
3.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.
3.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 Racket to be a bug in your code.
For example, Racket signals a “divide by zero” error if you attempt to evaluate (/ 1 0). Since we use Racket’s division function to implement division in CFWAE, you may be tempted to leave it to Racket to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Racket’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.
3.8.3 CFWAE (Lazy) [Extra Credit]
You must submit this in a file named "xinterp-lazy.rkt".
Copy your CFWAE interpreter into a file named "xinterp-lazy.rkt" 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!)
3.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) |
| ....) |
3.8.3.2 Tests
You should be able to run all the tests from "xinterp.rkt". 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.