Assignment 2: 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 on Canvas, please put all these .scm files into a single folder named a2, and zip that folder into a compressed archive named a2.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 and lists. So, for example, don’t 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. If you want to, you can use the unify function from unify.scm (bit it isn’t necessary).

Part 1: Environments

A environment is a data structure that represents variables and their values. Here is an abstract data type (ADT) that we’ll 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 Scheme’s 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.

Here’s 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. That’s 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 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 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 Go’s 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
         | 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 Scheme’s 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 literal number, then (inc n) simplifies to the value of n + 1
• if n is a literal 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