Interpreter Project
Part 3: Primitive Procedures: car, cdr, cons, +, -, *, <, >, =, et cetera

Remember, 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. The responsibility for testing each section is yours.

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

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

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

1. Change to the i-3 directory: cd ~/cs37/homework/i-3
2. Run the merge script to join your old files and the new files together ./merge

The wrap-up tests for Part 2 simulate the interactions with the interpreter which are shown below. 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:

> (read-eval-print-loop)   ; or, more simply, (repl)
INTERPRETER> (set! x 5)
ERROR: set! cannot set undefined identifier:  x
> (read-eval-print-loop)
INTERPRETER> (define x 5)
x
INTERPRETER> x
5
INTERPRETER> (set! x 8)
x
INTERPRETER> x
8
INTERPRETER> (define x 'hello)
x
INTERPRETER> x
hello
INTERPRETER> (define y x)
y
INTERPRETER> (set! x "testing...1...2...3...")
x
INTERPRETER> y
hello
INTERPRETER> x
"testing...1...2...3..."
INTERPRETER> exit
INTERPRETER done.

In today's portion, you will add the ability to evaluate expressions that use Scheme's primitive procedures. We will not write our own implementations of these primitive procedures; rather, when a user of our interpreter asks to evaluate an expression with a primitive procedure, we will call the Scheme primitive. This will save us from having to write our own versions of procedures like +, <, and cons.

In order to properly handle expressions that involve calls to primitive procedures, it is important to recall the rule of evaluation for Scheme procedure applications. Assume that x has been defined as 8 and y has been defined as 9. When Scheme encounters an expression such as (= x y), Scheme first determines the type of the expression to be a procedure application. Scheme knows the expression is a procedure application because:

1. the expression is a list, and
2. the first element of the list is not a special-form, such as quote, define, or set! (which we implemented in Part 2) or begin or if (which we will implement in Part 4).

To evaluate (= x y), Scheme first evaluates = to get the primitive implementation for numerical equality tests. (To see that Scheme really does this, type = on a line by itself in Scheme and you will see that it evaluates to #<primitive:=>.) Next, Scheme evaluates the variable x to get 8 and it evaluates the variable y to get 9. (You handled evaluation of variables in Part 2.) Now that all of the elements of the list (= x y) have been evaluated as (#<primitive:=> 8 9) , we apply the procedure to the arguments (and get #f). Since the name apply has already been taken by the real Scheme interpreter, we will call our apply function i-apply (short for interpreter-apply).

In order to implement primitive functions, we will begin by working on the implementation necessary for handling procedure applications. (See the summary page for details.) We will start by writing the definitions of the tester and selector functions for applications:

(application? exp)    
(operator exp)
(operands exp)

(application? '(cons 1 y)) ; => #t
(application? '(newline))  ; => #t
(application? 'cons)       ; => #f
(operator '(cons 1 y))     ; => cons
(operands '(cons 1 y))     ; => (1 y)
(operands '(newline))      ; => ()

Note that you probably want (application? '()) to return #f.

Once we know that an expression is a procedure application, we have to evaluate each of the procedure arguments. To do this, we will write a helper function called eval-operands that evaluates each element in the list of the operands, and returns a new list containing the evaluated operands. (This list of evaluated operands will become the args parameter to the function i-apply.)

eval-operands should perform as follows:

(define env1 (extend-env '(a b c) '(1 0 8) empty-env))
(eval-operands '(a 9 b c a) env1) ; => (1 9 0 8 1)

Now that we can evaluate the operands in a procedure application, we need to determine the appropriate procedure to apply by evaluating the procedure (as stated in the introduction). For primitive functions, this means that we will need to have each of the primitive procedure names bound to their implementations in the global environment.

We could bind the symbol car directly to the procedure which implements it, and we could bind the symbol cons directly to the procedure that implements it, and so forth. But, we would like a way of determining whether the symbol is bound to a primitive procedure or a user-defined procedure (created with lambda which we will implement in Part 5). To do this, we will "tag" each primitive procedure with the symbol primitive followed by the procedure's name and its implementation. We will do this using the procedure make-primitive:

(define make-primitive
  (lambda (name proc)
    (list 'primitive name proc)))

;; for example
(make-primitive 'car car) ; => (primitive car #<primitive:car>)

(define addition
  (lambda (x y)
     (cond ((< x 0) (addition (add1 x) (sub1 y))) 
           ((= x 0) y)
           ((= y 0) x)
           (else (addition (sub1 x) (add1 y))))))

(make-primitive '+ addition)

Since we will just use Scheme's implementation for each of the primitives that we would like in our interpreter, we could simply say:

(make-primitive '= =) ; => (primitive = #<primitive:=>)
(make-primitive 'cons cons) ; => (primitive cons #<primitive:cons>)

See the code included in this part's interpreter.ss file to see how this is actually done.

Write the tester and selector functions for primitives (see the summary page for details):

primitive-procedure?       ;is the procedure the result of calling make-primitive?
primitive-name             ;returns the name of the primitive
primitive-implementation   ;returns the implementation of the primitive

This new version of setup-env will add the definitions of many primitives to the global environment. In addition, the list primitive-procedures provides an easy way for you to add other primitive functions in the future, should you wish to do so. (You will likely need to do this in Part 6 to create your meta-circular interpreter). Be sure you understand how primitives work in our interpreter.

To complete the implementation for primitive procedure application, you will need the definitions for i-apply and apply-primitive-procedure, which I have provided below:

(define i-apply
   (lambda (proc vals)   ;; note: these "vals" have already been evaluated
     (cond
      ((primitive-procedure? proc) (apply-primitive-procedure proc vals))
      (else (error "unknown procedure type" proc)))))

(define apply-primitive-procedure
   (lambda (proc vals)
     (apply (primitive-implementation proc) vals)))

((application? exp) (eval-application exp env))

Since the application? test is a very general test -- it matches both procedure applications and special forms -- be sure you place the test after you have exhausted all of the tests for special forms.

Your interpreter should now handle the following tests. You must write your own tests that follow the format provided in the i-tests.ss file.

INTERPRETER> (define x 8)
x
INTERPRETER> (define y (+ x 1))
y
INTERPRETER> (define lst (cons x (cons '(x y z) (cons y null))))
lst
INTERPRETER> lst
(8 (x y z) 9)
INTERPRETER> (define z (+ (car lst) (car (cdr (cdr lst)))))
z
INTERPRETER> z
17
INTERPRETER> (= (+ x y) z)
#t
INTERPRETER> (define w *)
w
INTERPRETER> (w x y)
72