| Assigned: | Monday, September 21 |
| Due: | Wednesday, September 30, 11:59pm |
This exercise has you write a program in Scheme. You can read in the book about Scheme, or see the Scheme Report for a more definitive and complete source.
To use Scheme, you will find Racket convenient. You can get it from racket-lang.org. When you run it, set the language to R5RS Scheme (under legacy languages).
A Scheme comment is begins with a semicolon and ends at the end of the line.
Write an evaluator for expressions in Scheme. Use the evaluator in the book on page 151 as a starting point. It is recommended that you use that form, with helper function eval-params.
Your evaluator should allow more than the one in the book.
The expressions should allow numbers and operations plus, minus, times and divide. All of those operations should take any positive number of parameters. For example, if your evaluator is passed parameter (plus 3 5 4), then it should produce answer 12. Subtractions and divisions are done from left to right. Evaluating (minus 5 2 1) yields 2, and evaluating (divide 10 5) yields 2.
Make this change to the evaluator and test it.
Your expression evaluator should handle an expression of the form (if A B C). It starts by evaluating A. If A's value is 0 or 0.0, then it yields the value of C. Otherwise, it yields the value of B. For example, evaluation of expression (if (plus 1 2) (minus 3 5) (plus 5 6)) yields −2. Evaluating (if A B C) must only evaluate one of expressions B and C, not both.
Add this to your expression evaluator. Test it.
Your expression evaluator will allow variables. Add a second parameter to it, which is an environment telling the values of variables. An environment is a list of the form ((x1 v1) (x2 v2) ...), indicating that variable x1 has value v1, x2 has value v2, etc. A list of that form is called an association list. For example, association list ((rabbit 4) (mouse 30)) indicates that variable rabbit has value 4 and variable mouse has value 30. There is a useful Scheme function called assoc for looking up values in association lists. Scheme expression (assoc x L) searches association list L for the first occurrence of a list whose car is x, and it returns the first pair that it finds. For example, evaluating (assoc 'mouse '((rabbit 4) (mouse 30) (hamster 25))) yields list (mouse 30). If it cannot find a suitable pair, assoc yields #f.
Add the second parameter and add a test for a variable. Assume that a variable is a symbol, and use function symbol? to test whether a value is a symbol. Be sure to add a second parameter to each recursive call to eval-expr. Note that eval-params will also need another parameter, since it also needs to know the environment. Test this. For example, (eval-expr 'y '((y 20))) should yield 20. It says to produce the value of variable y, assuming that y is 20.
Your expression evaluator should allow variable values to be promises, which are expressions that have not yet been computed. The value of a variable in an environment is either a number (not a promise) or is a pair (E env) where E is an expression and env is an environment. When a variable is looked up, if its value is a pair (a promise), the promise should be evaluated. Be sure to compute it in the stored environment. For example, association list ((mouse ((plus x y) ((x 10) (y 20))))) says that the value of mouse can be found by computing (plus x y) in environment ((x 10) (y 20)). When (and if) the evaluation is done, mouse will have value 30.
When you perform an evaluation, replace the value of the variable by the computed value. That is, memoize the result. You can do that by using an imperative feature of Scheme. Evaluating (set-car! L v) changes the car of L to v in-place, by modifying the linked list. Evaluating (set-cdr! L v) changes the cdr of L to v in-place. Note that set-car! and set-cdr! are nonfunctional aspects of Scheme, and must be used with care.
Modify your evaluator to handle environments where variable values can be pairs. Test it. When a variable value is fetched, it should be evaluated and memoized.
(Note. A truly lazy system would not perform an evaluation of a promise until it is actually used in an operation, such as plus. For this simple evaluator we will assume that any value that is being fetched will be used.)
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. That is easy to handle by just adding it to the beginning of the association list. Remember that assoc finds the first suitable pair in the list.)
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 binding pairs, where yours takes only one binding pair.
When evaluating (let (x v) e), your evaluator should not immediately evaluate v. Instead, it should bind x to a promise (v env) where env is the current environment. Then it should evaluate e in that new environment.
Here are some examples of what your evaluator should do. In these examples, it is presumed that the first parameter of evaluate is the expression to evaluate, and the second parameter is the environment.
(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.)
(evaluate '(plus (times 2 3) (minus 4 2)) '( )) = 8.
(evaluate '(if (times 2 4) (plus 1 8) (divide 5 0)) '( )) = 9.
(evaluate '(if (minus 5 5) (divide 1 0) (plus 1 8)) '( )) = 9.
(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.)
(evaluate '(times x 3) '((x 5) (y 2))) = 15.
(evaluate '(times x 3) '((x 5) (x 2))) = 15.
(evaluate '(times x x) '((x ((plus y x) ((x 2)(y 3)))))) = 25
(evaluate '(let (z 15) (plus z z)) '( )) = 30.
(evaluate '(let (r (plus 2 5)) (times r 2)) '( )) = 14.
(evaluate '(let (s 5) (let (t (plus s s)) (times s (plus t 3)))) '( )) = 65
(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
)
This assignment should be easy to do. The program is quite short. Just pay careful attention to what you are writing, and try it on simple examples by hand. Rember that evaluating (cdr '(1 2)) yields list (2), not number 2.
Type in the interpreter from the book, and try it to ensure that it is working.
Now add subtraction and division. Test. Then add if expressions. Test that.
Now add the environment parameter. 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. Initially assume that the variable
value must be a number. Test this new evaluator.
Then improve it so that the value of a variable can be a promise. A promise needs to contain an expression and an environment in which it should be evaluated. That is, a promise is a closure. Test it again.
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 env)) to the front of the current environment env. Notice that, if E = (let (x v) a) then x is (caadr E). What are the other parts?
Add a tester to your program that runs enough test cases to show that the evaluator appears to be working. Put it in a function called test. Running (test) should run the tests and show the results.
Submit this assignment as assignment 3, using submit as in previous assignments. For example, use command
~abrahamsonk/3675/bin/submit 3 eval.scmYou can check what you have submitted using
~abrahamsonk/3675/bin/submit 3