Choose ONE of the following options to complete.
Out of the five programs below, you may either:
All definitions must be representation independent with respect to continuations. You must use a data structural representation of continuations.
Submit your registerized and trampolined programs, along with registerized or trampolined test calls to those programs.
(define depth
(lambda (ls k)
(cond
[(null? ls) (k 1)]
[(pair? (car ls))
(depth (car ls)
(lambda (l)
(depth (cdr ls)
(lambda (r)
(let ((l (add1 l)))
(k (if (< l r) r l)))))))]
[else (depth (cdr ls) k)])))
(define ack
(lambda (n m k)
(cond
[(zero? n) (k (add1 m))]
[(zero? m) (ack (sub1 n) 1 k)]
[else (ack n (sub1 m)
(lambda (v)
(ack (sub1 n) v k)))])))
(define fact
(lambda (n k)
((lambda (fact k)
(fact fact n k))
(lambda (fact n k)
(cond
[(zero? n) (k 1)]
[else (fact fact (sub1 n) (lambda (v) (k (* n v))))]))
k)))
(define pascal
(lambda (n k)
(let ((pascal
(lambda (pascal k)
(k (lambda (m a k)
(cond
[(> m n) (k '())]
[else (pascal pascal
(lambda (f)
(let ((a (+ a m)))
(f (add1 m) a
(lambda (w)
(k (cons a w)))))))]))))))
(pascal pascal
(lambda (f)
(f 1 0 k))))))
(define M
(lambda (f k)
(k (lambda (ls k)
(cond
((null? ls) (k '()))
(else (M f
(lambda (p)
(p (cdr ls)
(lambda (d)
(f (car ls)
(lambda (a)
(k (cons a d))))))))))))))
Here is an example of how to call each of these programs:
(depth '(1 (2 (3 (4)))) (empty-k)) => 4
(ack 2 2 (empty-k)) => 7
(fact 5 (empty-k)) => 120
(pascal 10 (empty-k)) => '(1 3 6 10 15 21 28 36 45 55)
(M (lambda (v k)
(k (add1 v)))
(lambda (p)
(p '(1 2 3) (empty-k)))) => '(2 3 4)