Assignment 8: Registerizing and Trampolining the Interpreter

Consider this direct-style interpreter, which is representation-independent with respect to both procedures and environments.

(define value-of
  (lambda (expr env)
    (pmatch expr
      (,n (guard (or (number? n) (boolean? n))) n)
      (,x (guard (symbol? x)) (apply-env env x))
      ((* ,x1 ,x2)
       (* (value-of x1 env)
          (value-of x2 env)))
      ((sub1 ,x) (sub1 (value-of x env)))
      ((zero? ,x) (zero? (value-of x env)))
      ((if ,test ,conseq ,alt)
       (if (value-of test env)
           (value-of conseq env)
           (value-of alt env)))
      ((letcc ,k-id ,body)
       (call/cc (lambda (k)
                  (value-of body (extend-env k-id k env)))))
      ((throw ,v-exp ,k-exp)
       ((value-of k-exp env) (value-of v-exp env)))
      ((lambda (,id) ,body) (closure id body env))
      ((,rator ,rand) (apply-proc (value-of rator env) (value-of rand env))))))

(define value-of-driver
  (lambda (expr)
    (value-of expr (empty-env))))

Your task is to perform a sequence of correctness preserving transformations on this interpreter:

Step 1: CPS the interpreter (along with any serious helper functions). Your helper functions must use a data-structural representation of environments and closures.
Step 2: Make the CPS'd interpreter representation-independent with respect to continuations. Use a data-structural representation of continuations.
Step 3: Registerize the representation-independent, CPS'd interpreter.
Step 4: Trampoline the registerized, representation-independent, CPS'd interpreter.

You will end up writing four different interpreters, one for each step. Remember that you needn't registerize a helper function if you can prove that it terminates for all possible inputs.

Here are two test programs that work with every version of the interpreter. Remember to test your interpreter after each step in the transformation!

(define-syntax test
  (syntax-rules ()
    ((_ title tested-expression expected-result)
     (let* ((expected expected-result)
            (produced tested-expression))
       (if (equal? expected produced)
           (printf "~s works!\n" title)
           (error
            'test
            "Failed ~s: ~a\nExpected: ~a\nComputed: ~a"
            title 'tested-expression expected produced))))))

(define fact-5
  '((lambda (f)
      ((f f) 5))
    (lambda (f)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((f f) (sub1 n))))))))

(test "fact-5"
  (value-of-driver fact-5)
  120)

(define letcc-fun
  '(* 3 (letcc q (* 2 (throw 4 q)))))

(test "letcc"
  (value-of-driver letcc-fun)
  12)

Submit all four versions of your interpreter, along with all helper functions and test programs. Place all of your code in a file named a8.scm and submit the file to Vincent.

You will not receive full credit on this assignment if you do not submit all four interpreters, and the helper functions required to make all four interpreters pass the test programs.

For this assignment you must use data-structural representations of environments, closures, and continuations.

Start early!

Brainteaser*:

CPS and trampoline the interpreter. Then registerize the trampolined interpreter. Remember to try your test programs!

*Not required. Extra credit will not be given unless all normal homework problem definitions show substantial effort.