Read EOPL Chapter 8 for background.
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,
your answer would be(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))
Convert the following procedures to continuation-passing style.
(define dupla (lambda (a ls) (if (null? ls) '() (cons a (dupla a (cdr ls)))))) (dupla 'x '(a b c))
(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)))
(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))
(define snoc (lambda (x ls) (if (null? ls) (cons x '()) (cons (car ls) (snoc x (cdr ls)))))) (snoc 'z '(x y))
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))
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))
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)
(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))))
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))