Assignment 6: Continuations and Representation Independence

CPS your interpreter. After CPSing, create two copies of your interpreter, making your continuations representation independent and using procedural representation for one copy, and data structural representation for the other. Here is a copy of the interpreter you are to CPS.

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

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 fact-5 (empty-env))
  120)


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

(test "letcc"
  (value-of letcc-fun (empty-env))
  12)

Submit your representation-independent interpreter, along with all helper functions and test programs. Make sure to submit your helpers for both procedural and data structural representation of continuations. Place all of your code in a file named a6.scm and submit the file to Vincent.