3.5 Extended Interpreter

You must complete this assignment using a specific language. Choose Determine language from source in the DrRacket menu, then write

#lang plai

as the first line of your program, overwritting the default #lang at the top of the file.

3.5.1 CFWAE

Implement the language 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.5.1.1 Syntax

The syntax of the CFWAE language with these additional features can be captured with the following grammar:

where number is a Racket number and id is not '+, '-, '*, '/, 'with, 'if0, 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)

3.5.1.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.5.1.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.5.1.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.5.1.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.