C311 Fall 1996: Exam 2

Instructors: C. Haynes and G. Gomez-Espinoza

Write your answers on the blank paper provided, with your name on each page. There are 80 points total. You have the entire class period for this exam. Show your work to receive partial credit. Check your work carefully!

  1. 30 points Convert the following procedures to CPS form: 
    1. (define mult
     (lambda (ls)
       (cond
	 [(null? ls) 1]
	 [(zero? (car ls)) 0]
	 [else (* (car ls) (mult (cdr ls)))])))
    
    (define mult
      (lambda (ls)
	(mult-cps ls (make-final-k))))

    (define mult-cps
      (lambda (ls k)
        (cond
          [(null? ls) (k 1)]
          [(zero? (car ls)) (k 0)]
          [else (mult-cps (cdr ls)
	          (lambda (v)
		    (k (* (car ls) v))))])))
    
2. (define another-mult
     (letrec ([mult-it
		(lambda (ls n)
		  (cond
		    [(null? ls) n]
		    [(zero? (car ls)) 0]
		    [else (mult-it (cdr ls) (* (car ls) n))]))])
       (lambda (ls)
	 (mult-it ls 1))))
     
    (define another-mult
      (lambda (ls)
        (another-mult-cps ls (make-final-k))))

    (define another-mult-cps
      (letrec ([mult-it
		 (lambda (ls n k)
	           (cond
		     [(null? ls) (k n)]
		     [(zero? (car ls)) (k 0)]
		     [else (mult-it (cdr ls) (* (car ls) n) k)]))])
        (lambda (ls k)
          (mult-it ls 1 k))))
    
3. (define test
     (lambda ()
       (let ([three (+ 3 (mult '(0 1 2 3 4 5 6 7 8)))]
	     [four  (mult '(1 1 1 2 1 1 1 2))]
	     [two^5 (mult '(2 2 2 2 2))])
	 (let ([x (mult (list three four two^5))])
	   (if (= x 384)
	     'everything-ok
	     'something-wrong)))))
    
    (define test
      (lambda ()
        (test-cps (make-final-k))))

    (define test-cps
      (lambda (k)
        (mult-cps '(0 1 2 3 4 5 6 7 8)
          (lambda (v)
	    (let ([three (+ 3 v)])
	      (mult-cps '(1 1 1 2 1 1 1 2)
	        (lambda (v)
	          (let ([four v])
		    (mult-cps '(2 2 2 2 2)
		      (lambda (v)
		        (let ([two^5 v])
		          (mult-cps (list three four two^5)
			    (lambda (v)
			      (let ([x v])
			        (if (= x 384)
				    (k 'everything-ok)
				    (k 'something-wrong))))))))))))))))
    (define make-final-k
      (lambda ()
        (lambda (v)
          (printf "The answer is ~s~n" v))))

  2. 20 points Convert mult from CPS form to
    1. Representation-independent form, representing continuations as procedures, 
      (define mult
  (lambda (ls)
    (mult-cps ls (make-final-k))))

(define mult-cps
  (lambda (ls k)
    (cond
      [(null? ls) (apply-k k 1)]
      [(zero? (car ls)) (apply-k k 0)]
      [else (mult-cps (cdr ls)
	      (make-mult-k ls k))])))

(define make-mult-k
  (lambda (ls k)
    (lambda (v)
      (apply-k k (* (car ls) v)))))

(define make-final-k
  (lambda ()
    (lambda (v)
      (printf "The answer is ~s~n" v))))

(define apply-k
  (lambda (k v)
    (k v)))
    2. Data-structure form, representing continuations as lists, 
      (define mult
  (lambda (ls)
    (mult-cps ls (make-final-k))))

(define mult-cps
  (lambda (ls k)
    (cond
      [(null? ls) (apply-k k 1)]
      [(zero? (car ls)) (apply-k k 0)]
      [else (mult-cps (cdr ls)
	      (make-mult-k ls k))])))

(define make-mult-k
  (lambda (ls k)
    (list 'mult-k ls k)))

(define make-final-k
  (lambda ()
    (list 'final-k)))

(define apply-k
  (lambda (k v)
    (record-case k
      (mult-k (ls k)
	(apply-k k (* (car ls) v)))
      (final-k ()
	v))))
    3. Imperative form, using register variables instead of formal parameters, and 
      (define reg-ls 'ignored)
(define reg-v  'ignored)
(define reg-k  'ignored)

(define mult
  (lambda (ls)
    (set! k-reg (make-final-k))
    (set! ls-reg ls)
    (mult-cps/reg)))

(define mult-cps/reg
  (lambda ()
    (cond
      [(null? ls-reg)
       (set! v-reg 1)
       (apply-k/reg)]
      [(zero? (car ls-reg))
       (set! v-reg 0)
       (apply-k/reg)]
      [else
	(set! k-reg (make-mult-k ls-reg k-reg))
	(set! ls-reg (cdr ls-reg))
	(mult-cps/reg)])))

(define make-mult-k
  (lambda (ls k)
    (list 'mult-k ls k)))

(define make-final-k
  (lambda ()
    (list 'final-k)))

(define apply-k/reg
  (lambda ()
    (record-case k-reg
      (mult-k (ls k)
	(set! k-reg k)
	(set! v-reg (* (car ls) v-reg))
	(apply-k/reg))
      (final-k ()
	v-reg))))
    4. Framed-stack form (you may assume push!, pop!, and top procedures have been defined). 
      (define reg-ls 'ignored)
(define reg-v  'ignored)

(define mult
  (lambda (ls)
    (push! (make-final-frame))
    (set! ls-reg ls)
    (mult-cps/reg)))

(define mult-cps/reg
  (lambda ()
    (cond
      [(null? ls-reg)
       (set! v-reg 1)
       (apply-k/reg)]
      [(zero? (car ls-reg))
       (set! v-reg 0)
       (apply-k/reg)]
      [else
	(push! (make-mult-frame ls-reg))
	(set! ls-reg (cdr ls-reg))
	(mult-cps/reg)])))

(define make-mult-frame
  (lambda (ls)
    (list 'mult-frame ls)))

(define make-final-frame
  (lambda ()
    (list 'final-frame)))

(define apply-k/reg
  (lambda ()
    (let ([frame (top)])
      (pop!)
      (record-case frame
	(mult-frame (ls)
	  (set! v-reg (* (car ls) v-reg))
	  (apply-k/reg))
	(final-frame ()
	  v-reg)))))

  3. 6 points The original mult is a function that takes a list and multiplies all the elements in the list. While doing this work it checks if there is a zero in the list, and if there is one, ignores the rest of the list (but still does all the previous pending multiplications). Modify mult so that if it finds a zero, it returns zero immediately, without doing the pending multiplications. (Hint: use call/cc).

    (define mult
  (lambda (ls)
    (call/cc
      (lambda (return)
	(letrec ([mult-hlp
		   (lambda (ls)
		     (cond
		       [(null? ls) 1]
		       [(zero? (car ls)) (return 0)]
		       [else (* (car ls) (mult-hlp (cdr ls)))]))])
	    (mult-hlp ls))))))
  4. 6 points Is it possible to define this new version of mult with Java-style try/catch (2nd-class continuations)? If so, how (don't worry about details of Java syntax)? If not, why not?

    (define mult
  (lambda (ls)
    (try
      (lambda ()
	(letrec ([mult-hlp
		   (lambda (ls)
		     (cond
		       [(null? ls) 1]
		       [(zero? (car ls)) (throw 'mult-excp)]
		       [else (* (car ls) (mult-hlp (cdr ls)))]))])
	  (mult-hlp ls)))
      (lambda (e) (eq? e 'mult-excp))
      (lambda (e) 0))))
  5. 8 points What is the value of each of the following Scheme expressions?
    1. (* 2 (call/cc (lambda (k) (* 7 (* 3 5))))) ==> 210
    2. (* 2 (call/cc (lambda (k) (* 7 (* 3 (k 5)))))) ==> 10
    3. (* 2 (call/cc (lambda (k) (* 7 (k (* 3 5)))))) ==> 30
    4. (* 2 (call/cc (lambda (k) (* 7 (call/cc (lambda (k1) (k (k1 5)))))))) ==> 70

  6. 10 points The following Scheme code models some of the characteristics of Java-style exception handling, but it does not implement the "dynamic wall". That is, handler-proc is run with the same raise procedure that caused it to be invoked. Why may this be bad? Indicate a modification to try that fixes this problem. 
    (define try
  (lambda (body-thunk guard-proc handler-proc)
    (call/cc
      (lambda (k)
	(fluid-let ((raise (let ((outer-raise raise))
			     (lambda (v)
			       (if (guard-proc v)
				 (fluid-let ((raise outer-raise))
				   (k (handler-proc v)))
				 (outer-raise v))))))
	  (body-thunk))))))