Interpreter Project
Part 4: Special Forms: begin, if, cond

Part 4 should be completed before class on Tuesday, April 25
Final project due Monday, May 8 at noon


Wrapping up Part 3

If you are still working on Part 3, please let me know if you need help. It is important that you don't fall behind.

To get the code for Part 4 and some wrap-up tests from Part 3, you will first need to run the command update37. Once you have done so, you will have created a new directory (cs37/homework/i-4) which has the new i-tests and interpreter pieces.

To join your old code and tests (from cs37/homework/i-3) with the new code and tests in cs37/homework/i-4, follow these steps:

  1. Change to the i-4 directory: cd ~/cs37/homework/i-4
  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, you should have a a new interpreter.ss and i-tests.ss file in your cs37/homework/i-4 directory.

The wrap-up tests for Part 3 that are provided for you simulate the following interaction with the interpreter. Your interpreter should successfully run the tests in i-tests.ss, but it is strongly recommended that you type some or all of the code in by hand to verify that the interactions are working properly. In particular, i-tests.ss can not test exit and exit! properly, so you must do this by hand.

> (read-eval-print-loop)
INTERPRETER> (define x (cons 1 (cons 2 null)))
x
INTERPRETER> x
(1 2)
INTERPRETER> (null? x)
#f
INTERPRETER> (null? (cdr (cdr x)))
#t
INTERPRETER> (= (car x) (- (car (cdr x)) 1))
#t
INTERPRETER> (define y (cons (car x) x))
y
INTERPRETER> y
(1 1 2)
INTERPRETER> (set! x 5)
x
INTERPRETER> (set! y (+ x 5))
y
INTERPRETER> y
10
INTERPRETER> (* x y)
50
INTERPRETER> exit
INTERPRETER done.
> (read-eval-print-loop)
INTERPRETER> (set! x 10)
x
INTERPRETER> x
10
INTERPRETER> exit!
INTERPRETER done.
> (read-eval-print-loop)
INTERPRETER> (set! x 10)
ERROR: set! cannot set undefined identifier:  x


Introduction to Part 4: Special Forms

Recall that Scheme's rule of evaluation states that all the arguments of a procedure must be evaluated before procedure application. We have seen in class that this rule cannot work for a set of "special forms" that includes define and set!, which you have already implemented in your interpreter.

Special forms are "special" because your interpreter must handle each of these forms differently. For example, in a define expression, such as (define x 5), the first argument, x, is never evaluated. An if expression, such as (if (< x y) x y), always evaluates its first argument, but will only evaluate one of its remaining two. Furthermore, since define, if, cond, etc. are not primitives, they have no binding in the environment. Therefore, with special forms, the operator is never evaluated.

On the other hand, all the primitive procedure applications (and, as we will see in Part 5, also the non-primitive procedure applications) are handled the same way by the your interpreter: The operator and all of the operands are evaluated, then the evaluated operator is applied to the evaluated operands. For example, in the expression (= x y), the operator =, and the operands x and y are all evaluated.


Special Form: begin

Extend your interpreter so that it can handle the special form begin. Recall that the syntax of a begin expression is as follows:

(begin exp1 exp2 ... expn)

The begin expression evaluates each of the expressions (exp1 through expn) in order and returns the value of the last expression. (See the Help Desk for more information on begin if you do not recall how it works.) If there are no expressions except the keyword begin, you should return void. (For now, your interpreter will print out "#<void>"; later, you will modify your interpreter so that it prints out nothing if the result is void.) For example:

INTERPRETER> (begin (define x 5) (+ x 3))
8
INTERPRETER> (begin (display "x + 3 = ") 
                    (display (+ x 3))
                    (newline)
                    'done) 
x + 3 = 8
done
INTERPRETER> (begin) ;this returns void
#<void>
INTERPRETER> (begin (set! x (* x 2)) x)
10
INTERPRETER> x
10
To get the interpreter to return void, use the Scheme primitive function void which you call by simply writing (void). You may also wish to add void to the list of primitive functions your interpreter supports.

To implement begin in your interpreter, you should continue using the same style of abstraction we have been using. Please reference the summary sheet so that the functions you write have the same names as those described.

  1. define a tester procedure, in this case, begin?,
  2. write any necessary selectors, in this case, begin-expressions
  3. and write a controller, in this case, eval-begin


Special Form: if

Next, we will allow our interpreter to handle the special form if. The syntax of an if expression is:

(if test-expression then-expression else-expression)
To evaluate an if expression, first the test-expression is evaluated. If the result is true, the then-expression is evaluated and returned as the result of the if expression. Otherwise, the else-expression is evaluated and returned. Important note: In Scheme, anything other than #f is considered true. For example:

INTERPRETER> (if (cons 1 2) 'true 'false)
true
INTERPRETER> (if 'not-false #t #f)
#t
INTERPRETER> (if (< 5 4) 'less 'not-less)
not-less
Implement all of the necessary procedures to handle if in your interpreter.

Your interpreter should now pass the following tests:

INTERPRETER> (define lst (cons 1 (cons 2 null)))
lst
INTERPRETER> (if (< (car lst) (car (cdr lst))) (car lst) (car (cdr lst)))
1
INTERPRETER> (* 5 (if (= (+ 3 3) (- 8 2)) 10 20))
50
In Scheme, it is possible to write an if expression that has a then-expression but has no else-expression. Modify your implementation so that it can handle if expressions of this form. You should return void if the test-expression evaluates as #f and there is no else-expression. For example:
INTERPRETER> (define x 5)
x
INTERPRETER> (if (= x 6)
               (+ x 1))  ;this returns void
#<void>
INTERPRETER> (if (= x 5)
               (+ x 1))
6
Important note: You are allowed to use Scheme's if to help define if in your interpreter. (The same is true for cond below.)

Reference the summary sheet for the names of the functions you should implement.


Special Form: cond

For the last portion of Part 4, we will add cond to our interpreter. Recall that the syntax of a cond is:

(cond 
   (test1 exp1 exp2 ... expn) 
   (test2 exp1 exp2 ... expn) 
   ...
   (testn exp1 exp2 ... expn))
Each subpiece of the cond expression is known as a clause. To evaluate a cond expression, your interpreter should consider each clause in order, as described below:
  1. Evaluate the expression test1.
  2. If test1 evaluates to be true (or anything that is not #f), then any remaining expressions exp1 .. expn are evaluated from left to right, and the value of the last expression is returned as the result of the entire cond.
    1. Notice that cond is a lot like begin. In fact, you may want to reuse your eval-begin procedure to help you when writing your solution to eval-cond.
    2. Also, note that if a test condition evaluates to be true but there are no other expressions following the test expression, the return value is the evaluated test expression.
  3. If test1 evaluates to be false, then the remaining test expressions are evaluated in order until one is found to be true, or there are no more test expressions.
  4. If no true expression is found, then the result is void.
  5. The symbol else appearing in place of a test expression should be considered to true.

Here are some examples:

INTERPRETER> (cond 
              ((= 3 5) "this is false" "so we skip this one")
              ((= 3 3) "this is true" "so we return this message")
              ((= 5 5) "this is also true" 
                       "but since an earlier test was true" 
                       "this never gets returned"))
"so we return this message"
INTERPRETER> (cond 
              (1  "since 1 is not #f, this evaluates to be true")
              (else "and once again, we never get here"))
"since 1 is not #f, this evaluates to be true"
INTERPRETER> (cond
              ((< (+ 1 1) 0) 'nope)
              ((< 1 0) 'still-no)
              ((= 4 5) 'no-matches))  ;this returns void
#<void>
INTERPRETER> (cond 
              ((< (+ 1 1) 0) 'nope)
              ((< 1 0) 'still-no)
              (else 'matched-else))
matched-else
INTERPRETER> (define x 5)
x
INTERPRETER> (cond
              ((set! x (+ x 1)) x)
              (else "Note: be sure x is 6, not 7"))
6
INTERPRETER> x
6
INTERPRETER> (cond
              ((+ 1 1)))
2
INTERPRETER> (cond)  ; returns void
#<void>
Implement all of the procedures necessary to handle cond in your interpreter. (See the summary sheet.)