## CS 441 Assignment 4: Continuation-passing Style

This assignment is due Thursday March 7 at 6:00pm (since I gave it out a bit late), by electronic submission.

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
(tail (depth (cdr ls))))
tail

(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))
```