Due Thursday March 6, 11:59pm.
This assignment consists of converting several procedures (familiar from assignment 1) 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))))))
your answer would be
(define fact-cps
(lambda (n k)
(if (zero? n)
(k 1)
(fact-cps (sub1 n)
(lambda (v)
(k (* n v)))))))
When CPS'ing, memq is not considered a primitive
procedure (it has recursion in it). For problem 3, assume you have
the following definition:
(define memq-cps
(lambda (a ls k)
(cond
[(null? ls) (k #f)]
[(eq? a (car ls)) (k ls)]
[else (memq-cps a (cdr ls) k)])))
To check whether your procedures work correctly, you might want to test them with the initial continuation
(define final-val-k
(lambda (v)
(printf "The answer is ~s~n" v)))
which is somewhat like the continuation used by the grader.
Convert the following procedures to CPS.
1. (define assq
(lambda (a als)
(cond
[(null? als) #f]
[(eq? (caar als) a) (car als)]
[else (assq a (cdr als))])))
2. (define duplicate
(lambda (n a)
(if (zero? n)
'()
(cons a (duplicate (sub1 n) a)))))
3. (define union
(lambda (s0 s1)
(if (null? s0)
s1
(if (memq (car s0) s1)
(union (cdr s0) s1)
(cons (car s0) (union (cdr s0) s1))))))
4. (define snoc
(lambda (ls i)
(if (null? ls)
(list i)
(cons (car ls) (snoc (cdr ls) i)))))
5. (define prefixes
(letrec ([prefix-hlp
(lambda (ls current-prefix answ)
(if (null? ls)
answ
(let ([new-prefix (snoc current-prefix (car ls))])
(prefix-hlp
(cdr ls)
new-prefix
(cons new-prefix answ)))))])
(lambda (ls)
(prefix-hlp ls '() '(())))))
The test cases will be the ones used in assignment 1. In addition, the grader will undefine the original procedures (to make sure you use only the -cps versions).
As before, but refer to "handin 6".