This evaluates to `111`. Nothing exotic happens here. 2.100 +let/cc k (10 + 1)

This evaluates to `101`. See also example 11, below. 3.100 +let/cc k (10 + k 1)

In the first line, we bind the continuation function (the bold code) to `k` and then bind the variable `p` to the pair of `1` and that function. In the second line, we extract the continuation function from the pair `p` and apply it to the argument `(2, ident)`. That results in the following code being run:let p =let/cc k (1,k)in let y = snd p (2, ident) in (fst p, y)

which in turn results in the nested pair `(2, (2, ident))`. Notice how the first time through, when `p`'s second element is a continuation, applying it to an argument is a bit like time-travel? The metaphysically impossible kind of time-travel, where you can change what happened. The second time through, `p` gets bound to a different pair, whose second element is the ordinary `ident` function. 4.let p =(2, ident)in let y = snd p (2, ident) in (fst p, y)

Here the box is implicit, understood to be the rest of the code. The result is just the abort value `11`, because the bold code is skipped. 5.1000 + (100 +abort 11)

1000 + resetHere the box or delimiter is explicitly specified. The bold code is skipped, but the outside code `1000 + < >` is still executed, so we get `1011`. 6.(100 +abort 11)

1000 + resetEquivalent to preceding. We bind the bold code to `k` but then never apply `k`, so the value `10 + 1` is supplied directly to the outside code `1000 + < >`, resulting in `1011`. 7.(100 +shift k (10 + 1))

1000 + resetHere we do invoke the captured continuation, so what gets passed to the outside code `1000 + < >` is `k (10 + 1)`, that is, `(100 + (10 + 1))`. Result is `1111`. In general, if the last thing that happens inside a `shift k ( ... )` body is that `k` is applied to an argument, then we do continue running the bold code between `shift k ( ... )` and the edge of the `reset` box. 8.(100 +shift k (k (10 + 1)))

1000 + resetThis also results in `1111`, but via a different path than the preceding. First, note that `k` is bound to `100 + < >`. So `k 1` is `101`. Then `10 + k 1` is `10 + 101`. Then we exit the body of `shift k ( ... )`, without invoking `k` again, so we don't add `100` any more times. Thus we pass `10 + 101` to the outside code `1000 + < >`. So the result is `1000 + (10 + 101)` or `1111`. (Whereas in the preceding example, the result was `1000 + (100 + 11)`. The order in which the operations are performed is different. If we used a non-commutative operation instead of `+`, the results of these two examples would be different from each other.) 9.(100 +shift k (10 + k 1))

1000 + resetHere `k` is bound to `100 + < >`. That function `k` is what's returned by the `shift k ( ... )` block, and since `k` isn't invoked (applied) when doing so, the rest of the bold `reset` block is skipped (for now). So we resume the outside code `1000 + < > 1`, with what fills the gap `< >` being the function that was bound to `k`. Thus this is equivalent to `1000 + (fun x -> 100 + x) 1` or `1000 + 101` or `1101`. 10.(100 +shift k (k))1

1000 + resetHere `k` is bound to `100 + < >`. Thus `k 1` is `101`. Now there are two ways to think about what happens next. (Both are valid.) One way to think is that since the `shift` block ends with an additional outermost application of `k`, then as described in example 7 above, we continue through the bold code with the value `k 1` or `101`. Thus we get `100 + 101`, and then we continue with the outermost code `1000 + < >`, getting `1000 + (100 + 101)`, or `1201`. The other way to think is that since `k` is `100 + < >`, and `k 1` is `101`, then `k (k 1)` is `201`. Now we leave the `shift` block *without* executing the bold code a third time (we've already taken account of the two applications of `k`), resuming with the outside code `1000 + < >`, thereby getting `1000 + 201` as before. 11. Here's a comparison of `let/cc` to `shift`. Recall example 2 above was:(100 +shift k (k (k 1)))

which evaluated to `101`. The parallel code where we instead capture the continuation using `shift k ( ... )` would look like this:100 +let/cc k (10 + k 1)

resetBut 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 +shift k (10 + k 1))