C311 Fall 1996 -- Programming Languages

Assignment 6: CPS Transformation

Due Friday, October 25, 5:00P

This assignment consists of converting several procedures (familiar from assignment 1) to continuation-passing style. The continuation argument should be the last argument of the new procedure. The name of the procedure you convert should be the name of the original procedure plus the suffix ``-cps''. So, for example, if you were asked to convert the following procedure into continuation-passing style,

(define fact
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (sub1 n))))))

(define fact-cps
  (lambda (n k)
    (if (zero? n)
        (k 1)
        (fact-cps (sub1 n)
          (lambda (v)
            (k (* n v)))))))

To check whether your procedures work correctly, you might want to test them with the initial continuation

(define init-k
  (lambda (v)
    (printf "The answer is ~s~n" v)
    (reset)))

Assignment

Convert the following procedures to CPS.

1. (define list-index
     (lambda (a ls)
       (cond
	 [(null? ls) -1]
	 [(eq? (car ls) a) 0]
	 [else
	   (let ([answ (list-index a (cdr ls))])
	     (if (= answ -1)
	       -1
	       (add1 answ)))])))

2. (define intersection
     (lambda (s0 s1)
       (cond
	 [(null? s0) '()]
	 [(memq (car s0) s1)  (cons (car s0)
				(intersection (cdr s0) s1))]
	 [else (intersection (cdr s0) s1)])))

3. (define count-parens
     (lambda (ls)
       (cond
	 [(null? ls) 2]
	 [(list? (car ls)) (+ (count-parens (car ls)) (count-parens (cdr ls)))]
	 [else (count-parens (cdr ls))])))

4. (define depth
     (lambda (ls)
       (cond
	 [(null? ls) 1]
	 [(pair? ls) (max (add1 (depth (car ls)))
		       (depth (cdr ls)))]
	 [else 0])))

5. (define vector-index
     (lambda (a v)
       (let ([vlen (vector-length v)])
	 (letrec ([vindex-hlp
		    (lambda (n)
		      (cond
			[(= vlen n)	-1]
			[(eq? (vector-ref v n) a)	n]
			[else (vindex-hlp (add1 n))]))])
	   (vindex-hlp 0)))))

Submission