Interpreter Project
Part 2: Evaluation and Environment Modification: quote, define, set!

Each step of the interpreter assumes that you have successfully completed the previous step. By writing comprehensive tests (in i-tests.ss), you can be sure that the code you have written so far works properly. Although I will usually provide a few sample tests, the responsibility for extensively testing each section is yours. Demonstrate to me that your Part 1 code passes all of your tests before moving on to Part 2.

To get the starting-point code and sample tests for Part 2, you will first need to run the update37 command which will create the directory cs37/homework/i-2 and copy the files interpreter-p2.ss and i-tests-p2.ss. Next, join your old code and tests (from cs37/homework/i-1) with the new code and tests. To do so, simply follow these steps. (Note: These steps assume that your interpreter stored in a file called "interpreter.ss", that your tests are stored in a file called "i-tests.ss", and that both files are located in your homework/i-1 directory.

1. Change to the homework/i-2 directory: cd ~/cs37/homework/i-2
2. Run the merge script to join your old files and the new files together: ./merge
   • Assuming you successfully merged your old and new files together, the above script will erase the now-unnecessary interpreter-p2.ss and i-tests-p2.ss, leaving you with a new interpreter.ss and i-tests.ss file.
   • In addition, this script added the line (require (lib "pretty.ss")) to the top of your interpreter.ss file to allow us to use the Scheme function pretty-print. The function pretty-print is a nicer version of display which performs word wrapping and automatically inserts newlines.
   • Though it is not added automatically, you may want to include the "trace.ss" library if you'd like to trace functions you are writing.

In order to continue with our interpreter, we need to be able to complete two pieces of the environment abstraction which we omitted in Part 1: the function setup-env and the variable global-env which stores the variables in the global environment.

Scheme predefines many bindings in its global environment: null, null?, car, cdr, list, and cons to name just a few. At this point, we will start with a very small global environment with just a single binding: the symbol null will be bound to the empty list ().

This is a temporary solution. In part 3, we will greatly expand our global environment. For now, we will use the following as our definition for setup-env:

(define setup-env
  (lambda ()
    (extend-env '(null) '(()) empty-env)))

(define global-env (setup-env))

The central component of our interpreter is the evaluator. This is the component that takes a Scheme expression and an environment and evaluates the expression in the context of that particular environment. We will do this evaluation by first determining what type of expression we are given, and then dealing with each type on a case-by-case basis.

The most basic types of expressions are the self-evaluating expressions. Self-evaluating expressions are expression that evaluate to be themselves regardless of the environment. In our language, this will be the booleans < #t and #f >, numbers < 5, -56, 3.1415 > and strings < "hello", "this is a string" >.

We will deal with other types of expressions, such as the special forms define and set! later in Part 2. We will postpone implementing the remaining special forms (if, begin, cond, lambda, let, etc.) until Parts 4 and 5. Our interpreter will begin to be able to evaluate procedure applications in Part 3, and we will complete the evaluation of procedure applications in Part 5.

Since the name eval has already been taken by the real Scheme interpreter, we will call our evaluator i-eval (short for interpreter-evaluator).

We will start with self-evaluating expressions. Scheme has primitive functions that can test whether or not an expression is self-evaluating: boolean?, number?, and string?. Since these are the only types of self-evaluating expressions in our language, we can write an evaluator to handle these fairly easily.

Read through the implementation I give below (which should now be in your interpreter.ss file) and test it out on a few simple expressions to make sure you understand how it works.

(define i-eval
  (lambda (exp env)
    (cond
     ((boolean? exp) exp)
     ((number? exp) exp)
     ((string? exp) exp)
     (else (error "i-eval::unknown expression type" exp)))))

Now, we can create the (read-eval-print-loop) which will read input from the user, evaluate the input in the global-env, print the result, then loop. For example:

> (read-eval-print-loop)
INTERPRETER> 5
5
INTERPRETER> -3.14
-3.14
INTERPRETER> #f
#f
INTERPRETER> "a short string"
"a short string"
INTERPRETER> exit
INTERPRETER done.

Complete the function read-eval-print-loop to support this. An initial version, shown below, is included in your interpreter.ss file. You need to add the ability to allow the user to exit the interpreter by typing the command exit.

(define read-eval-print-loop
  (lambda ()
    (display "INTERPRETER> ")
    (let ((user-input (read)))
      (pretty-print (i-eval user-input global-env))
      (read-eval-print-loop))))

Your interpreter should now handle the self-evaluating boolean, number and string expressions. Now you will extend the range of expressions your interpreter can handle by allowing for quoted expressions. Recall that in Scheme, you can create a quoted expression either by using the quote function, or by using it's short-hand notation, the single quote:

> (quote this-is-quoted)
this-is-quoted
> 'this-is-also-quoted
this-is-also-quoted
> (quote (4 5 6))
(4 5 6)
> '(3.14 #t "hello")
(3.14 #t "hello")

Remember that a single-quote placed immediately before an expression is equivalent to using the full quote notation. The read function automatically expands an apostrophe to the quote notation, so our interpreter doesn't need to worry about expressions that start with single-quotes: handling expressions which use the full quote notation is sufficient.

You should write the procedure quoted? to test to see if an expression is quoted. Notice from the examples above that when a user enters a quoted expression, they are simply entering a list whose first element is the symbol quote. To test out your function, try the following line, which will read one line from you and then return whether or not the line you entered was a quoted expression.

(quoted? (read))   ;See important note below

(Note: You can not simply say (quoted? 'x). In evaluating the expression (quoted? 'x), Scheme evaluates 'x to be the symbol x and so the procedure quoted? is called with the symbol x -- which is no longer quoted; therefore, (quoted? 'x) ; ==> #f. To get the desired effect, you'd have to put your test case in a second quote: (quoted? ''x). When evaluating (quoted? ''x), Scheme evaluates ''x, or (quote (quote x)), to be the list (quote x), which will return #t when passed to quoted?.

You should also write the procedure text-of-quotation which returns the text of a quoted expression. For example, the text of the quotation (quote x) is x. You can test this as follows:

(text-of-quotation (read)) ; try typing (quote x) or '(1 2 3) at the read prompt

Extend i-eval to evaluate quoted expressions. You should use the functions quoted? and text-of-quotation which you just wrote.

(See the summary page for more details.)

Your interpreter can now evaluate self-evaluating expressions as well as quoted expressions. You will now add the ability to define (and, in the next section, mutate) the environment by extending your interpreter to handle variable definitions. Notice that your interpreter's define special form returns the name of the variable you are defining:

> (read-eval-print-loop)
INTERPRETER> (define pi 3.1415)
pi
INTERPRETER> pi
3.1415
INTERPRETER> (define a (quote apple))
a
INTERPRETER> a
apple
INTERPRETER> (define a (quote jacks))
a
INTERPRETER> a
jacks

Fortunately, your work in Part 1 has already laid the necessary groundwork for implementing define. To begin the implementation, we will need to add a case to our cond statement in i-eval to identify the expression type. You will write the tester function definition? for identifying define expressions.

The definition? tester function should end up looking a lot like the quoted? tester you just wrote. In fact, you will need to write many more tester functions which will have the same format. So, we will add a helper function, (tagged-list? exp tag), to capture this abstraction. The tagged-list? function will return #t whenever:

1. exp is a list, and
2. the first element of exp is tag.

(tagged-list? '(define x 8) 'define) ;=> #t
(tagged-list? "some string" 'define) ;=> #f  (not a list)
(tagged-list? '(set! x 6) 'define)   ;=> #f  
(tagged-list? '(define x) 'define)   ;=> #t  ; See note below

Using tagged-list?, write definition? (and go back and rewrite quoted?) in terms of tagged-list?.

(definition? '(define y 3)) ;=> #t
(definition? 5)             ;=> #f

> (definition-variable '(define x 6))
x
> (definition-value '(define x 6))
6

After recognizing that an expression is a definition, we need to evaluate the expression, and update the environment to reflect the new definition. The special form define can be used to either create a new binding or to update an existing binding. Note that define only affects the most recently added frame of an environment.

However, before you place a binding for a variable into the environment, you will need to evaluate the third element of the define expression. For example, in Scheme, when you say (define a (quote (1 2 3))), a is not bound to (quote (1 2 3)); rather, (quote (1 2 3)) is first evaluated, and its result, (1 2 3), is stored as the binding for a.

Write the function (eval-definition exp env) which extracts the definition-value of the define statement from exp and evaluates it using your evaluator, i-eval, and then calls define-variable! with the definition-variable, the result of evaluating the definition-value, and the environment, env.

You will also need to write the above-mentioned function (define-variable! var val env) which checks to see if a binding already exists for var in the first frame of env. If so, we mutate the binding to be val. If no binding exists for var in the first frame, we mutate the frame to include the new binding.

To complete the implementation for define, you will need to make two changes to i-eval. First, i-eval must recognize and properly handle define expressions (by adding a case to your cond statement). Second, i-eval must recognize and deal with variables (also by adding a case to your cond statement). Below is the tester variable? needed to recognize variables.

(define variable?
   (lambda (exp)
     (symbol? exp)))

When you evaluate (using i-eval) an expression that is a variable, it should evaluate as its value in the environment. In Part 1 you wrote a procedure that finds the value of a variable in an environment, so you should use that to extend i-eval so that it properly evaluates variables.

Be sure to thoroughly test your code. Below are some tests you can use, but you should also add your own to your i-tests.ss file:

>  (read-eval-print-loop)
INTERPRETER> (define x 6)
x
INTERPRETER> x
6
INTERPRETER> (define x 23)
23
INTERPRETER> x
x
INTERPRETER> (define q x)
23
INTERPRETER> q
q
INTERPRETER> (define m 'q)
m
INTERPRETER> m
q

Notice that in the expression (define q x), if you hadn't called i-eval on the value component of the define, q would have been bound to the symbol x rather than the value 23.

Congratulations! You have now completed implementing define. You should find that implementing set! is relatively straightforward now. In Scheme, set! can only be used on a variable that has a previous binding in the environment. We search the environment (starting with the most recently added frame) until we find such a binding. Once we find a previous binding, we mutate it to reflect the new value. If we do not find any binding, we return an error.

You will need to implement each of these functions (and update i-eval appropriately) to handle set!. You will find most of these to be very similar to the ones that you previously wrote for define:

assignment?
eval-assignment
assignment-variable
assignment-value
set-variable-value!

Here are some simple tests which behave exactly as they do in Scheme with one exception: our versions of define and set! display the name of the variable that was defined/mutated.

> (read-eval-print-loop)
INTERPRETER> (define x 5)
x
INTERPRETER> (define y x)
y
INTERPRETER> (set! y 10)
y
INTERPRETER> y
10
INTERPRETER> x
5
INTERPRETER> (set! z 5)
ERROR set! cannot set undefined identifier:  z
> (read-eval-print-loop)   ; See next section for explanation
INTERPRETER> x
5

Note that for each new feature we incorporate into our interpreter, we will go through the same steps: creating testers, selectors, controllers, and sometimes helpers, and then updating i-eval.

As you can see from the final two lines of the example interactions listed above, when we exit the read-eval-print-loop, either by explicity typing exit or causing a crash, the global environment still contains all of the bindings we created. This means that we can just run read-eval-print-loop again, and all of our bindings will be in place. This is a nice feature for testing, because if read-eval-print-loop crashes, you can resume with the same environment in place. However, it may also confuse you if this is not what you are expecting after cleanly exiting the read-eval-print-loop.

Modify read-eval-print-loop so that it allows users the option of resetting the global environment back to its initial state. If the user types exit, stop the read-eval-print-loop as you are currently doing -- without resetting the global-env. However, if the user types exit! (that's exit with an exclamation point), stop the read-eval-print-loop and also set! the global-env back to the environment returned by setup-env.