CS 441 Assignment 4: Continuation-passing Style

Read EOPL Chapter 8 for background.

Format

The language for this homework assignment is Scheme (not Micro Scheme).

This assignment consists of converting a number of procedures 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))))))

(fact 5)

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

(fact-cps 5 (lambda (x) x))

Assignment

Convert the following procedures to continuation-passing style.

1. (define dupla
     (lambda (a ls)
       (if (null? ls)
           '()
   	(cons a (dupla a (cdr ls))))))
   
   (dupla 'x '(a b c))
   

2. (define tree-mult
     (lambda (ls)
       (cond
         ((null? ls) 1)
         ((not (pair? (car ls)))
          (* (car ls) (tree-mult (cdr ls))))
         (else
   	(* (tree-mult (car ls)) (tree-mult (cdr ls)))))))
   
   (tree-mult '((1 2) (3 4)))
   

3. (define double*
     (lambda (a ls)
       (cond
         ((null? ls) '())
         ((not (pair? (car ls)))
          (if (eq? (car ls) a)
              (cons a (cons a (double* a (cdr ls))))
   	   (cons (car ls) (double* a (cdr ls)))))
         (else
   	(cons (double* a (car ls)) (double* a (cdr ls)))))))
   
   (double* 'a '(a b (c a) d))
   

4. (define snoc
     (lambda (x ls)
       (if (null? ls)
           (cons x '())
   	(cons (car ls) (snoc x (cdr ls))))))
   
   (snoc 'z '(x y))
   

5. Convert both map and dbl in:

   (define map
     (lambda (f ls)
       (cond
         ((null? ls) '())
         (else (cons (f (car ls)) (map f (cdr ls)))))))
   
   (define dbl (lambda (a) (list a a)))
   
   (map dbl '(a b c))
   

6. Convert both filter and its functional argument in: Assume pred has been converted to continuation-passing style.

   (define filter
     (lambda (pred ls)
       (cond
         ((null? ls) '())
         ((not (pred (car ls))) (filter pred (cdr ls)))
         (else
   	(cons (car ls) (filter pred (cdr ls)))))))
   
   (filter (lambda (x) (not (zero? x))) '(1 2 0 3))
   

7. Convert compose, its functional arguments, and the procedure that compose returns in:

   (define compose
     (lambda (f g)
       (lambda (x)
         (f (g x)))))
   
   ((compose (lambda (x) (add1 x)) (lambda (y) (sub1 y))) 0)
   

8. (define depth
     (lambda (ls)
       (cond
         ((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))))))
   
   (depth '(a b (c (d))))
   

9. Do not convert parse or environments, but do convert eval and any other procedures you have to in:

   (define eval
     (lambda (e env)
       (variant-case e
         (Const (value)
           value)
         (Var (name)
           (lookup env name))
         (Lam (formals body) 
           (lambda (arg) (eval body (extend env (car formals) arg))))
         (Ap (fun args)
           (let ((vfun (eval fun env))
                 (varg (eval (car args) env)))
             (vfun varg))))))
   
   (eval (parse '((lambda (x) x) 1)) (make-empty))