[SOLVED] Scheme: Assignment 4: A Scheme Expression Evaluator

Assignment 4: A Scheme Expression Evaluator
For this assignment, you are asked to write various Scheme .scm files. When it is time to submit your work, please put all these .scm files into a single folder named a4, and zip it into a compressed archive named a4.zip.

Make sure to use exactly the same function names and arguments (otherwise the marking software may give you 0!).

Please use MIT Scheme, and stick to basic Scheme functions, special forms, and lists. So, for example, dont uses loops or vectors in your solution.

All the code you write should be written by you do not use any code from any other sources. Cite any and all help you got for this assignment in the source code of the relevant file.

You can (and probably should!) create helper functions for some of the questions.

You dont need to do much error checking: you can assume that valid data is passed to the functions you write.

Part 1: Environments
A environment is an abstract data type (ADT) defined by the following three functions:

(make-empty-env)

Returns a new empty environment.

(apply-env env v)

Returns the value of variable v in environment env.

If v is not in env, then use Schemes standard error function to raise a helpful error message.

(extend-env v val env)

Returns a new environment that is the same as env except that the value of v in it is val.

If v already has a value in env, then in the newly returned environment this value will be shadowed, i.e. the value of v will be val. See the example below.

You can assume v is a symbol.

Heres an example of how these functions can be used. First, we create an environment call test-env that is built up from multiple applications of extend-env to (make-empty-env):

(define test-env
(extend-env a 1
(extend-env b 2
(extend-env c 3
(extend-env b 4
(make-empty-env)))))
)
Here are some calls to apply-env:

=> (apply-env test-env a)
;Value: 1

=> (apply-env test-env b)
;Value: 2

=> (apply-env test-env c)
;Value: 3

=> (apply-env test-env d)
;apply-env: empty environment
Notice that the returned value for b is 2. Thats because the b with value 2 was the most recent b added to the environment, and so it shadows the other b.

Implement this environment ADT in two significantly different ways. Put one implementation in a file called env1.scm, and the other in env2.scm. In the comments at the top of each file include a brief description of how the environments are implemented. Be sure to test each implementation (you should be able to use the same testing code for each). The testing should not depend upon the details of the implementation.

Part 2: An Expression Evaluator
In a file named myeval.scm, implement a function called (myeval expr env) that evaluates the infix expression expr in the environment env. expr can contain variables from the environment.

Here are some examples:

(define env1
(extend-env x -1
(extend-env y 4
(extend-env x 1
(make-empty-env))))
)

(define env2
(extend-env m -1
(extend-env a 4
(make-empty-env)))
)

(define env3
(extend-env q -1
(extend-env r 4
(make-empty-env)))
)

=> (myeval (2 + (3 * x));; the expression
env1;; the environment
)
-1

=> (myeval (2 + (3 * 1));; the expression
env1;; the environment
)
5

=> (myeval ((m * a) 0.1);; the expression
env2;; the environment
)
-4.1

=> (myeval (4 * (s * s));; the expression
env3;; the environment
)
;apply-env: unknown variable s ;; call error if expression cant be evaluated
Your evaluator must be called exactly like this:

(myeval expr env)
expr is an arithmetic expression (as defined below), and env is an environment (using your favourite implementation from part 1) of the variables and their values that can appear in expr. Your implementation of myeval must not depend upon the particular implementation details of the environment.

Here is an EBNF grammar for the expressions that myeval can evaluate:

expr = ( expr + expr )
| ( expr – expr )
| ( expr * expr )
| ( expr / expr )
| ( expr ** expr );; e.g. (2 ** 3) is 8, (3 ** 3) is 27
| ( inc expr );; adds 1 to expr
| ( dec expr );; subtracts 1 from expr
| var
| number
number = a Scheme number
var= a Scheme symbol
If you call myeval on an expression not generated by this grammar, or if the expression contains a variable not in the environment, then use Schemes standard error function to return a helpful error. Also, call error whenever division by 0 occurs.

Part 3: An Expression Simplifier
In a file named simplify.scm, create a function called (simplify expr) that returns, if possible, a simplified version of expr. To simplify an expression, repeatedly apply the following rules to expr wherever possible (e is any expression):

(0 + e) simplifies to e
(e + 0) simplifies to e
(0 * e) simplifies to 0
(e * 0) simplifies to 0
(1 * e) simplifies to e
(e * 1) simplifies to e
(e 0) simplifies to e
(e e) simplifies to 0
(e ** 0) simplifies to 1
(e ** 1) simplifies to e
(1 ** e) simplifies to 1
if n is a number, then (inc n) simplifies to the value of n + 1
if n is a number, then (dec n) simplifies to the value of n 1
You should recursively simplify sub-expressions. Note that there is no environment involved with this function, and so you cannot (and should not!) use myeval in simplify.

Here are a few example simplifications:

> (simplify ((1 * (a + 0)) + 0))
;Value: a

> (simplify (((a + b) (a + b)) * (1 * (1 + 0))))
;Value: 0

> (simplify ((1 * a) + (b * 1)))
;Value: (a + b)

> (simplify ((1 * a) + (b * 0)))
;Value: a

> (simplify (z ** (b * (dec 1))))
;Value: 1