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) 1 (* 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).
(define dupla (lambda (a n) (if (zero? n) '() (cons a (dupla a (sub1 n))))))
(define listmul (lambda (ls) (if (null? ls) 1 (* (car ls) (listmul (cdr ls))))))
(define treemul (lambda (tr) (cond [(null? tr) 1] [(not (pair? (car tr))) (* (car tr) (treemul (cdr tr)))] [else (* (treemul (car tr)) (treemul (cdr tr)))])))
(define union (lambda (a b) (cond [(null? a) b] [(memv (car a) b) (union (cdr a) b)] [else (cons (car a) (union (cdr a) b))])))
(define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (- n 2)))))
(define snoc (lambda (i ls) (if (null? ls) (list i) (cons (car ls) (snoc i (cdr ls))))))
f
has been converted to CPS:
(define map (lambda (f ls) (if (null? ls) '() (cons (f (car ls)) (map f (cdr ls))))))
pred
has been converted to CPS:
(define filter (lambda (pred ls) (cond [(null? ls) '()] [(pred (car ls)) (filter pred (cdr ls))] [else (cons (car ls) (filter pred (cdr ls)))])))
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)))))
(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))])))
(define listmul (lambda (l) (cond [(null? l) 1] [(zero? (car l)) (error 0)] [else (* (car l) (listmul (cdr l)))]))) (define listmul (lambda (l) (call/cc (lambda (exit) (letrec ([loop (lambda (l) (cond [(null? l) 1] [(zero? (car l)) (exit 0)] [else (* (car l) (loop (cdr l)))]))]) (loop l))))))
make-coroutine
below such that the
pseudo-code for battleship works.
(define player-1-code (let ([Board (make-board)]) (lambda (resume other-player-first-shot) (letrec ([loop (lambda (other-player-shot) (if (other-player-shot-is-fatal?) (I-lost-the-game) (let ([his-next-shot (resume player-2 (compute-my-shot))]) (loop his-next-shot))))]) (loop other-player-first-shot))))) (define player-2-code ...) (define player-1 (make-coroutine player-1-code)) (define player-2 (make-coroutine player-2-code))
samefringe
problem on page 315 of the book
and understand the coroutine solution. Write a solution in your
favorite programming language. The only constraint is that you don't
needlessly traverse the entire trees.