[SOLVED] schemeCMPT 383 Assignment 3: An Expression Evaluator and Simplifier

$25

File Name: schemeCMPT_383_Assignment_3:_An_Expression_Evaluator_and_Simplifier.zip
File Size: 631.14 KB

5/5 - (1 vote)

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 environment env .

    If v is not in env , then it calls 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)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 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 / 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 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.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart
[SOLVED] schemeCMPT 383 Assignment 3: An Expression Evaluator and Simplifier
$25