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

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

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

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.

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 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

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)

INTERPRETER> (if (cons 1 2) 'true 'false)
true
INTERPRETER> (if 'not-false #t #f)
#t
INTERPRETER> (if (< 5 4) 'less 'not-less)
not-less

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

INTERPRETER> (define x 5)
x
INTERPRETER> (if (= x 6)
               (+ x 1))  ;this returns void
#<void>
INTERPRETER> (if (= x 5)
               (+ x 1))
6

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

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))

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>