Computer Science 3675
Summer 2000
Programming Assignment 4

Due: June 1.

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 if you want a more definitive source. To use Scheme, you have three options (plus others if you explore).

  1. Use the basic MIT Scheme. It is installed only on the Sparc computers in room 320, as /export/stu/3675/bin/scheme. This version is available from MIT swiss-ftp.ai.mit.edu, in the /pub directory.

    The Scheme interpreter is called scheme. So type scheme to start the Scheme interpreter. The way to use it is to write your program using a text editor, and to load your program into the interpreter. If you modify your program, then reload it. To load file "eval.scm", you write 

           (load "eval.scm")
    (The value of this expression is the name of the last function defined in that file, and the interpreter will report that value.)

    To exit Scheme, type a control-D.

  2. Use Dr. Scheme on the Dell computers running Solaris. Currently, only the text-based implementation is available. It is /export/other/x86/bin/scheme. It works similarly to MIT Scheme. See the previous note.

  3. Get Dr. Scheme for yourself. It runs under most common operating systems. You can get it from www.cs.rice.edu/CS/PLT/packages/drscheme. When you run it, be sure to use the Mr. Ed package. You need to have full Scheme, not one of the stripped down versions that is provided.

The Assignment

Write an evaluator for expressions in Scheme. The expressions should allow variables, numbers, and operations +, -, * and /. All of these operations should have exactly two parameters. 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.)

Your evaluator should have two parameters: the expression to evaluate and an environment in which to evaluate it. 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.

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

  1. (eval '(+ 2 3) ()) = 5

  2. (eval '(+ (* 2 3) (* 4 5)) ()) = 26.

  3. (eval 'x '((y 2) (x 5))) = 5.

  4. (eval '(* x 3) '((x 5) (y 2))) = 15.

  5. (eval '(* x 3) '((x 5) (x 2))) = 15.

  6. (eval '(let (z 15) (+ z z)) ()) = 30.

  7. (eval '(let (r (+ 2 5)) (* r 2)) ()) = 14.

  8. (eval '(let (s 5) (let (t (+ s s)) (* s (+ t 3)))) ()) = 65
The last example is easier to read if it is displayed in a better form. It looks like this. 
      (eval
         '(let (s 5)                   ; s = 5
               (let (t (+ s s))        ; t = s + s
                      (* s (+ 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 notes, page 112. 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 eval. 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 of an identifier 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 value.) 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

Email your solution, as an attachment, to karl@cs.ecu.edu, with subject
3675 assn4 your name
Just send the function, not the test cases. That does not mean that you do not need to test it, though! Thorough testing is recommended.