Due Date

May 9, 1996. Please turn in your solution at the beginning of the lecture.


The assignment consists of converting a number of procedures to continuation-passing style (CPS). The continuation argument should be the last argument of the new procedure. For example if you were asked to convert the following procedure into CPS,

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


Convert the following procedures to CPS. (The last four questions are harder than the rest).

  1. (define dupla
      (lambda (a n)
        (if (zero? n)
            (cons a (dupla a (sub1 n))))))

  2. (define listmul
      (lambda (ls)
        (if (null? ls)
            (* (car ls) (listmul (cdr ls))))))

  3. (define treemul
      (lambda (tr)
          [(null? tr) 1]
          [(not (pair? (car tr))) (* (car tr) (treemul (cdr tr)))]
          [else (* (treemul (car tr)) (treemul (cdr tr)))])))

  4. (define union
      (lambda (a b)
          [(null? a) b]
          [(memv (car a) b) (union (cdr a) b)]
          [else (cons (car a) (union (cdr a) b))])))

  5. (define fib
      (lambda (n)
        (if (< n 2)
            (+ (fib (- n 1)) (- n 2)))))

  6. (define snoc
      (lambda (i ls)
        (if (null? ls)
            (list i)
            (cons (car ls) (snoc i (cdr ls))))))

  7. Assume f has been converted to CPS:
    (define map
      (lambda (f ls)
        (if (null? ls)
            (cons (f (car ls)) (map f (cdr ls))))))

  8. Assume pred has been converted to CPS:
    (define filter
      (lambda (pred ls)
          [(null? ls) '()]
          [(pred (car ls)) (filter pred (cdr ls))]
          [else (cons (car ls) (filter pred (cdr ls)))])))

  9. Assume f and g have been converted to CPS. Not only should compose be converted to CPS, but the procedure it returns should also be converted.
    (define compose
      (lambda (f g)
        (lambda (x)
          (f (g x)))))

  10. (define depth
      (lambda (ls)
          [(null? ls) 1]
          [(not (pair? (car ls))) (depth (cdr ls))]
          [else (let ([head (add1 (depth (car ls)))]
                      [tail (depth (cdr ls))])
                  (if (< head tail) tail head))])))


Amr A Sabry
Mon Apr 29 09:54:39 PDT 1996