Computer Science 3675
Summer 2002
Programming Assignment 4

Due: Wednesday, July 17, 11:59pm

This exercise has you write a program in Scheme. There is a page

scheme description
that describes Scheme by relating it to Astarte. You can also read the Scheme Report for a more definitive and complete source.

To use Scheme, you will find Dr. Scheme convenient.

  1. Use Dr. Scheme under Unix in room 320. It is called drscheme.

    2. You need to set the language to full scheme, not the stripped down versions that are available. Under the Language menu, select "Choose Language", and change the language to "Full Scheme".

  2. Get Dr. Scheme for yourself. It runs under Windows. You can get it from www.cs.rice.edu/CS/PLT/packages/drscheme.

The Assignment

Write an evaluator for expressions in Scheme. The expressions should allow variables, numbers, and operations plus, minus, times and divide. All of these operations should have exactly two parameters. For example, if your evaluator is passed parameter (plus 3 5), then it should produce answer 8. Evaluating (minus 5 2) yields 3, and evaluating (divide 10 5) yields 2.

Additionally, your evaluator should allow an expression of the form (let (x v) e), which indicates that variable x should be bound to the value of expression v, and that e should be evaluated with that binding. The value of expression (let (x v) e) is the value of e. (If x already has a value, then the new value takes precedence over the old one.)

Note that your version of let is a little different from the let function that is part of Scheme. The Scheme let takes a list of pairs of bindings, where yours takes only one binding pair.

Your evaluator should have two parameters: the expression to evaluate and an environment in which to evaluate it. The environment tells the values of variables. Represent the environment as an association list, which has the form ((x1 v1) (x2 v2) ...), indicating that variable x1 has value v1, variable x2 has value v2, etc. Use standard function assoc to get the value of a variable from the association list. Read about assoc in either of the Scheme documentation pages.

Here are some examples of what your evaluator should produce. In these examples, it is presumed that the first parameter of evaluate is the expression to evaluate, and the second parameter is the environment.

  1. (evaluate '(plus 2 3) ()) = 5 (Notice that the environment is (). There are no variable bindings. Also notice the quote mark on the expression. You need to quote it to prevent the Scheme interpreter from trying to evaluate it.

  2. (evaluate '(plus (times 2 3) (times 4 5)) ()) = 26.

  3. (evaluate 'x '((y 2) (x 5))) = 5. (This evaluates expression x in an environment where y is bound to 2 and x is bound to 5. The answer is 5, the value of x.)

  4. (evaluate '(times x 3) '((x 5) (y 2))) = 15.

  5. (evaluate '(times x 3) '((x 5) (x 2))) = 15.

  6. (evaluate '(let (z 15) (plus z z)) ()) = 30.

  7. (evaluate '(let (r (plus 2 5)) (times r 2)) ()) = 14.

  8. (evaluate '(let (s 5) (let (t (plus s s)) (times s (plus t 3)))) ()) = 65

The last example is easier to read if it is displayed in a better form. It looks like this. 
      (evaluate
         '(let (s 5)                       ; s = 5
               (let (t (plus s s))         ; t = s + s
                    (times s (plus t 3))   ; compute s*(t+3)
               )
          )
          ()                            ; the environment has no bindings yet
      )

Hints

This assignment should be easy to do. The program is quite short.

See the interpreter in the text. You will need to modify it, or a similar version discussed in class. First type in your basic interpreter that just does addition and multiplication. Try it out, and make sure it is working.

Now add subtraction and division. Test.

Now add the environment parameter to evaluate. Also add a symbol as one of the possible forms that an expression can have. You will have a case in the cond that looks something like this. 

        ((symbol? e) (...))
where the missing expression looks up the value of symbol e in the environment. Use standard Scheme function assoc to get the value of e from the environment. Test this new evaluator. See whether it can get the value to which an identifier is bound from the environment.

Now add the let expressions. If the first thing in the expression is the symbol let, and the expression looks like (let (x v) a), then you want to add pair (x v') to the front of the environment, and evaluate a in that new environment. What should v' be? (Hint: It is not just v, since v might be an expression, and x should be bound to a number.) Be sure to use the correct selectors. If e is (let (x v) a), how do you get x, v and a out of e? (x, for example, is the (caadr of e).)

Turning in the assignment

Turn in your assignment using the handin program, as assignment 4.