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 ofextend-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 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 insimplify.

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