C311 Spring 1997: Exam 2

Instructors: C. Haynes and G. Gomez-Espinoza

1. 30 points Convert the following procedures to CPS Form. Redefine the original procedures so that the cps'ed version is called with a proper initial continuation.

   a) (define sum
        (lambda (n)
          (if (zero? n)
             0
             (+ (sum (- n 1)) n))))

   Answer:

   (define sum-cps
     (lambda (n k)
       (if (zero? n)
         (k 0)
         (sum-cps (- n 1)
   	(lambda (v) (k (+ v n)))))))
   
   (define sum
     (lambda (n)
       (sum-cps n (lambda (v) v))))

   b) (define depth
        (lambda (alst)
          (if (null? alst)
   	 1
   	 (let ((drest (depth (cdr alst))))
   	   (if (pair? (car alst))
   	     (let ((dfirst (+ (depth (car alst)) 1)))
   	       (if (< dfirst drest) drest dfirst))
   	     drest)))))

   Answer:

   (define depth-cps
     (lambda (alst k)
       (if (null? alst)
         (k 1)
         (depth-cps (cdr alst)
   	(lambda (v)
   	  (let ((drest v))
   	    (if (pair? (car alst))
   	      (depth-cps (car alst)
   		(lambda (v)
   		  (let ((dfirst (+ v 1)))
   		    (if (< dfirst drest) (k drest) (k dfirst)))))
   	      (k drest))))))))
   
   (define depth
     (lambda (alst)
       (depth-cps alst (lambda (x) x))))

   c) (define Y
        (lambda (f)
          ((lambda (x) (f (lambda (y) ((x x) y))))
           (lambda (x) (f (lambda (y) ((x x) y)))))))

   Answer:

   (define Y-cps
     (lambda (f k)
       ((lambda (x k) (f (lambda (y k) (x x (lambda (v) (v y k)))) k))
        (lambda (x k) (f (lambda (y k) (x x (lambda (v) (v y k)))) k))
        k)))
   
   (define Y
     (lambda (f)
       (Y-cps f (lambda (x) x))))

2. 10 points Convert sum-cps from CPS Form to Representation-independent Form, representing continuations as procedures.

   Answer:

   (define sum-cps
     (lambda (n k)
       (if (zero? n)
         (apply-k k 0)
         (sum-cps (- n 1)
   	(make-sum-k n k)))))
   
   (define make-sum-k
     (lambda (n k)
       (lambda (v) (apply-k k (+ v n)))))
   
   (define make-final-k
     (lambda ()
       (lambda (v) v)))
   
   (define apply-k
     (lambda (k v)
       (k v)))
   
   (define sum
     (lambda (n)
       (sum-cps n (make-final-k))))

3. 10 points Convert this procedure to Data-Structure Form, representing continuations as lists.

   Answer:

   (define sum-cps
     (lambda (n k)
       (if (zero? n)
         (apply-k k 0)
         (sum-cps (- n 1)
   	(make-sum-k n k)))))
   
   (define make-sum-k
     (lambda (n k)
       (list 'sum-k n k)))
   
   (define make-final-k
     (lambda ()
       (list 'final-k)))
   
   (define apply-k
     (lambda (k v)
       (record-case k
         (sum-k (n k)
   	(apply-k k (+ v n)))
         (final-k () v))))
   
   (define sum
     (lambda (n)
       (sum-cps n (make-final-k))))

4. 10 points Convert the above program to Imperative Form, using register variables instead of formal parameters. Redefine sum so that it sets up the registers properly for the call to sum-cps/reg.

   Answer:

   (define n-reg 'ignored)
   (define k-reg 'ignored)
   (define v-reg 'ignored)
   
   (define sum-cps/reg
     (lambda ()
       (if (zero? n-reg)
         (begin
   	(set! k-reg k-reg)
   	(set! v-reg 0)
   	(apply-k/reg))
         (begin
   	(set! k-reg (make-sum-k n-reg k-reg))
   	(set! n-reg (- n-reg 1))
   	(sum-cps/reg)))))
   
   (define make-sum-k
     (lambda (n k)
       (list 'sum-k n k)))
   
   (define make-final-k
     (lambda ()
       (list 'final-k)))
   
   (define apply-k/reg
     (lambda ()
       (record-case k-reg
         (sum-k (n k)
   	(set! k-reg k)
   	(set! v-reg (+ v-reg n))
   	(apply-k/reg))
         (final-k () v-reg))))
   
   (define sum
     (lambda (n)
       (set! k-reg (make-final-k))
       (set! n-reg n)
       (sum-cps/reg)))

5. 10 points Convert the above program to Framed-Stack Form (you may assume push!, pop!, and top procedures have been defined).

   Answer:

   (define n-reg 'ignored)
   (define v-reg 'ignored)
   
   (define sum-cps/reg
     (lambda ()
       (if (zero? n-reg)
         (begin
   	(set! v-reg 0)
   	(apply-k/reg))
         (begin
   	(push! (make-sum-frame n-reg))
   	(set! n-reg (- n-reg 1))
   	(sum-cps/reg)))))
   
   (define make-sum-frame
     (lambda (n)
       (list 'sum-frame n)))
   
   (define make-final-frame
     (lambda ()
       (list 'final-frame)))
   
   (define apply-k/reg
     (lambda ()
       (let ([frame (top)])
         (pop!)
         (record-case frame
   	(sum-frame (n)
   	  (set! v-reg (+ v-reg n))
   	  (apply-k/reg))
   	(final-frame () v-reg)))))
   
   (define sum
     (lambda (n)
       (push! (make-final-frame))
       (set! n-reg n)
       (sum-cps/reg)))

6. 10 points What is the value of each of the following Scheme expressions?
   1. (+ 1 (call/cc (lambda (k) (+ 10 (+ 100 1000)))))
      ==> 1111
   2. (+ 1 (call/cc (lambda (k) (+ 10 (+ 100 (k 1000))))))
      ==> 1001
   3. (+ 1 (call/cc (lambda (k) (+ 10 (k (+ 100 1000))))))
      ==> 1101
   4. (+ 1 (call/cc (lambda (k) (+ 10 (call/cc (lambda (k1) (k (k1 100))))))))
      ==> 111
   5. (call/cc (lambda (k) (+ 1 (+ 10 (call/cc (lambda (k1) (+ 100 (k1 (k 1000)))))))))
      ==> 1000