Assignment 3: An Expression Evaluator and Simplifier
Your task for this assignment is to implement a Scheme expression evaluator and simplifier. The assignment is divided into parts that ask you to put your code into these files:
- Part 1:
env1.scm
,env2.scm
- Part 2:
myeval.scm
- Part 3:
simplify.scm
When it is time to submit your work, please put all these .scm
files into a single folder named a3
, and zip that folder into a compressed archive named a3.zip
.
Make sure to use exactlythe same function names and arguments (otherwise the marking software may give you 0!).
Please use MIT Scheme, and stick to basic Scheme functions and lists. So, for example, dont uses loops or vectors in your solution. Use high-level functions like map
, filter
, and fold
when it makes your code simpler or easier to understand.
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.
Part 1: Environments
A environment is a data structure that represents variables and their values. Here is an abstract data type (ADT) that well be using for this assignment:
-
(make-empty-env)
Returns a new empty environment.
-
(apply-env env v)
Returns the value of variable
v
in environmentenv
.If
v
is not inenv
, then it calls Schemes standarderror
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 ofv
in it isval
.If
v
already has a value inenv
, then in the newly returned environment this value will be shadowed , i.e. the value ofv
will beval
. 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)1> (apply-env test-env 'b)2> (apply-env test-env 'c)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.
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 expressionenv1;; the environment)-1> (myeval '(2 + (3 * 1));; the expressionenv1;; the environment)5> (myeval '((m * a) - 0.1);; the expressionenv2;; the environment)-4.1> (myeval '(4 * (s * s));; the expressionenv3;; the environment);apply-env: unknown variable s ;; call error if expression can't 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 (using Gos grammar style ) that defines what exactly is, and is not, a valid expression:
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 | numbernumber = a Scheme numbervar= 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 valid expression):
(0 + e)
simplifies toe
(e + 0)
simplifies toe
(0 * e)
simplifies to0
(e * 0)
simplifies to0
(1 * e)
simplifies toe
(e * 1)
simplifies toe
(e / 1)
simplifies toe
(e - 0)
simplifies toe
(e - e)
simplifies to0
(e ** 0)
simplifies to1
(e ** 1)
simplifies toe
(1 ** e)
simplifies to1
- if
n
is a number, then(inc n)
simplifies to the value ofn + 1
- if
n
is a number, then(dec n)
simplifies to the value ofn - 1
You should recursively simplify sub-expressions. Note that there is no environment involved with this function, and so you cannot 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
Reviews
There are no reviews yet.