C311 Spring 1996: Exam 2

Haynes, Hilsdale, and Subramaniam

April 1, 1996

You have the entire class period for this exam. Show your work to receive credit. If you use any procedure that is not standard in Scheme, you must define it (in any blank space that seems large enough).

1. 15 points
   What is the output of the following Scheme expressions?

   (+ 3 4 (call/cc (lambda (k) 
                     (* 80 (k 3))))
          7 5)
   
   Answer: 22
   
   (+ 3 4 (call/cc (lambda (k) 
                     (* 80 (k (k 3)))))
          7 5)
   
   Answer: 22
   
   (+ 3 4 (call/cc (lambda (k) 
                     (+ 6 (call/cc (lambda (j)
                                      (* 80 (j (k 3))))))))
          7 5)
   
   Answer: 22
   

2. 15 points
   Convert the following procedure into continuation-passing style.

   (define Y
     (lambda (m)
       ((lambda (f)
          (f f))
        (lambda (f)
          (m (lambda (x) ((f f) x)))))))
   
   Answer:
   
   (define Y-cps
     (lambda (m k1)
       ((lambda (f k2)
          (f f k2))
        (lambda (f k3)
          (m (lambda (x k4)
   	    (f f (lambda (v)
   		   (v x k4))))
   	 k3))
        k1)))
   

3. 50 points
   The procedure length takes a list ls and returns the length of the list:

   (define length
     (lambda (ls)
       (if (null? ls)
           0
           (add1 (length (cdr ls))))))
   
   (length '(a b c)) ==> 3
   (length '())      ==> 0
   

   • (a) Convert length into continuation-passing style by defining the procedure length-cps which takes a list ls and a continuation k. Redefine the procedure length so that it calls length-cps with a proper initial continuation.
     Answer:

     (define length-cps
       (lambda (ls k)
         (if (null? ls)
             (k 0)
     	(length-cps (cdr ls)
     	  (lambda (tail)
     	    (k (add1 tail)))))))
     
     (define length
       (lambda (ls)
         (length-cps ls (lambda (x) x))))
     

   • (b) Write a representation-independent version of the above program called length-ri, and represent your continuations as records. Redefine length so that it calls length-ri with a proper initial continuation. You may assume "record.ss" has already been loaded.
     Answer

     (define-record init-k ())
     (define-record tail-k (k))
     
     (define length-ri
       (lambda (ls k)
         (if (null? ls)
             (apply-k k 0)
     	(length-ri (cdr ls)
     	  (make-tail-k k)))))
     
     (define apply-k
       (lambda (k v)
         (variant-case k
           [init-k () v]
           [tail-k (k) (apply-k k (add1 v))])))
     
     (define length
       (lambda (ls)
         (length-ri ls (make-init-k))))
     

   • (c) Convert the above program so that it passes its arguments as registers. Call the new program length-reg (which should take zero arguments). Redefine length so that it sets up the registers properly for the call to length-reg, and returns the answer.
     Answer:

     (define-record init-k ())
     (define-record tail-k (k))
     
     (define ls* #f)
     (define k* #f)
     (define v* #f)
     
     ;; ls* k*
     (define length-reg
       (lambda ()
         (if (null? ls*)
     	(begin
     	  (set! v* 0)
     	  (apply-k))
     	(begin
     	  (set! k* (make-tail-k k*))
     	  (set! ls* (cdr ls*))
     	  (length-reg)))))
     
     ;; k* v*
     (define apply-k
       (lambda ()
         (variant-case k*
           [init-k () 'done]
           [tail-k (k)
     	(set! k* k)
     	(set! v* (add1 v*))
     	(apply-k)])))
     
     (define length
       (lambda (ls)
         (set! k* (make-init-k))
         (set! ls* ls)
         (length-reg)
         v*))
     

   • (d) Convert the above program into the stack-form program length-st by placing the control information (i.e., continuations) on a stack. Redefine length so that it sets up the stack and registers properly for the call to length-st and returns the answer. You may assume the existence of some properly defined stack package with top, push! and pop!.
     Answer:

     (define ls* #f)
     (define v* #f)
     
     ;; ls* k*
     (define length-st
       (lambda ()
         (if (null? ls*)
     	(begin
     	  (set! v* 0)
     	  (apply-k))
     	(begin
     	  (push! 'tail-k)
     	  (set! ls* (cdr ls*))
     	  (length-st)))))
     
     ;; k* v*
     (define apply-k
       (lambda ()
         (case (pop!)
           [(init-k) () 'done]
           [(tail-k) 
            (set! v* (add1 v*))
            (apply-k)])))
     
     (define length
       (lambda (ls)
         (push! 'init-k)
         (set! ls* ls)
         (length-st)
         v*))