@@ -186,3 +195,120 @@ Here are some examples of using these different continuation operators. The cont But this evaluates differently. In the `let/cc` example, `k` is bound to the rest of the computation *including its termination*, so after executing `k 1` we never come back and finish with `10 + < >`. A `let/cc`-bound `k` never returns to the context where it was invoked. Whereas the `shift`-bound `k` only includes up to the edge of the `reset` box --- here, the rest of the computation, but *not including* its termination. So after `k 1`, if there is still code inside the body of `shift`, as there is here, we continue executing it. Thus the `shift` code evaluates to `111` not to `101`. Thus code using `let/cc` can't be *straightforwardly* translated into code using `shift`. It can be translated, but the algorithm will be more complex. + + +## Some call/cc (or let/cc) exercises from The Seasoned Schemer ## + +Here are a series of examples from *The Seasoned Schemer*, which we recommended at the start of term. It's not necessary to have the book to follow the exercises, though if you do have it, its walkthroughs will give you useful assistance. + +For reminders about Scheme syntax, see [[here|/exercises/assignment12/#scheme]], and [[here|/rosetta1]] and [[here|/rosetta3]]. Other resources are on our [[Learning Scheme]] page. + +Most of the examples assume the following preface: + + #lang racket + + (define (atom? x) + (and (not (pair? x)) (not (null? x)))) + +Now try to figure out what this function does: + + (define alpha + (lambda (a lst) + (let/cc k ; now what will happen when k is called? + (letrec ([aux (lambda (l) + (cond + [(null? l) '()] + [(eq? (car l) a) (k (aux (cdr l)))] + [else (cons (car l) (aux (cdr l)))]))]) + (aux lst))))) + +Here is [[the answer|cps_hint_1]], but try to figure it out for yourself. + +Next, try to figure out what this function does: + + (define beta + (lambda (lst) + (let/cc k ; now what will happen when k is called? + (letrec ([aux (lambda (l) + (cond + [(null? l) '()] + [(atom? (car l)) (k (car l))] + [else (begin + ; what will the value of the next line be? why is it ignored? + (aux (car l)) + (aux (cdr l)))]))]) + (aux lst))))) + +Here is [[the answer|cps_hint_2]], but try to figure it out for yourself. + +Next, try to figure out what this function does: + + (define gamma + (lambda (a lst) + (letrec ([aux (lambda (l k) + (cond + [(null? l) (k 'notfound)] + [(eq? (car l) a) (cdr l)] + [(atom? (car l)) (cons (car l) (aux (cdr l) k))] + [else + ; what happens when (car l) exists but isn't an atom? + (let ([car2 (let/cc k2 ; now what will happen when k2 is called? + (aux (car l) k2))]) + (cond + ; when will the following condition be met? what happens then? + [(eq? car2 'notfound) (cons (car l) (aux (cdr l) k))] + [else (cons car2 (cdr l))]))]))] + [lst2 (let/cc k1 ; now what will happen when k1 is called? + (aux lst k1))]) + (cond + ; when will the following condition be met? + [(eq? lst2 'notfound) lst] + [else lst2])))) + +Here is [[the answer|cps_hint_3]], but try to figure it out for yourself. + +Here is the hardest example. Try to figure out what this function does: + + (define delta + (letrec ([yield (lambda (x) x)] + [resume (lambda (x) x)] + [walk (lambda (l) + (cond + ; is this the only case where walk returns a non-atom? + [(null? l) '()] + [(atom? (car l)) (begin + (let/cc k2 (begin + (set! resume k2) ; now what will happen when resume is called? + ; when the next line is executed, what will yield be bound to? + (yield (car l)))) + ; when will the next line be executed? + (walk (cdr l)))] + [else (begin + ; what will the value of the next line be? why is it ignored? + (walk (car l)) + (walk (cdr l)))]))] + [next (lambda () ; next is a thunk + (let/cc k3 (begin + (set! yield k3) ; now what will happen when yield is called? + ; when the next line is executed, what will resume be bound to? + (resume 'blah))))] + [check (lambda (prev) + (let ([n (next)]) + (cond + [(eq? n prev) #t] + [(atom? n) (check n)] + ; when will n fail to be an atom? + [else #f])))]) + (lambda (lst) + (let ([fst (let/cc k1 (begin + (set! yield k1) ; now what will happen when yield is called? + (walk lst) + ; when will the next line be executed? + (yield '())))]) + (cond + [(atom? fst) (check fst)] + ; when will fst fail to be an atom? + [else #f]) + )))) + +Here is [[the answer|cps_hint_4]], but again, first try to figure it out for yourself.100 +let/cc k (10 + 1)