Assignment 7: Continuation Representation Independence, Trampolining, and Registerization

Part I:

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 a7.scm and submit the file to Vincent.

Part II:

Choose ONE of the following options to complete.

Out of the five programs below, you may either:

Trampoline two programs and registerize the remaining three, or
Trampoline three programs and registerize the remaining two.

All definitions must be representation independent with respect to continuations. You must use a data structural representation of continuations.

Submit your registerized and trampolined programs along with their test suites (from the last assignment).


(define depth
  (lambda (ls k)
    (cond
      [(null? ls) (k 1)]
      [(pair? (car ls))
       (depth (car ls)
         (lambda (l)
	   (depth (cdr ls)
	     (lambda (r)
	       (let ((l (add1 l)))
	         (k (if (< l r) r l)))))))]
      [else (depth (cdr ls) k)])))

(define ack
  (lambda (n m k)
    (cond
      [(zero? n) (k (add1 m))]
      [(zero? m) (ack (sub1 n) 1 k)]
      [else (ack n (sub1 m)
              (lambda (v)
	        (ack (sub1 n) v k)))])))

(define fact
  (lambda (n k)
    ((lambda (fact k)
       (fact fact n k))
     (lambda (fact n k)
       (cond
         [(zero? n) (k 1)]
         [else (fact fact (sub1 n) (lambda (v) (k (* n v))))]))
     k)))

(define pascal
  (lambda (n k)
    (let ((pascal
           (lambda (pascal k)
             (k (lambda (m a k)
                  (cond
                    [(> m n) (k '())]
                    [else (pascal pascal
		            (lambda (f)
			      (let ((a (+ a m)))
			        (f (add1 m) a
				  (lambda (w)
                                    (k (cons a w)))))))]))))))
      (pascal pascal
        (lambda (f)
	  (f 1 0 k))))))

		
(define M
  (lambda (f k)
    (k (lambda (ls k)
         (cond
           ((null? ls) (k '()))
           (else (M f
                   (lambda (p)
                     (p (cdr ls)
                       (lambda (d)
                         (f (car ls)
                           (lambda (a)
                             (k (cons a d))))))))))))))

Here is an example of how to call each of these programs:

(depth '(1 (2 (3 (4)))) (empty-k)) => 4
(ack 2 2 (empty-k)) => 7
(fact 5 (empty-k)) => 120
(pascal 10 (empty-k)) => '(1 3 6 10 15 21 28 36 45 55)
(M (lambda (v k)
     (k (add1 v)))
  (lambda (p)
    (p '(1 2 3) (empty-k)))) => '(2 3 4)