--- /dev/null
+* [Example of an not-fully-immersive game](http://www.i-mockery.com/minimocks/50arcadecabinets/star-wars-arcade.gif)
+* [A more immersive game](http://upload.wikimedia.org/wikipedia/commons/7/78/AC89-0437-20_a.jpeg)
+
+
+3. `callcc` was originally introduced in Scheme. There it's written `call/cc` and is an abbreviation of `call-with-current-continuation`. Instead of the somewhat bulky form:
+
+ (call/cc (lambda (k) ...))
+
+ I prefer instead to use the lighter, and equivalent, shorthand:
+
+ (let/cc k ...)
+
+
+Callcc/letcc examples
+---------------------
+
+First, here are two examples in Scheme:
+
+ (+ 100 (let/cc k (+ 10 1)))
+ |-----------------|
+
+This binds the continuation `outk` of the underlined expression to `k`, then computes `(+ 10 1)` and delivers that to `outk` in the normal way (not through `k`). No unusual behavior. It evaluates to `111`.
+
+What if we do instead:
+
+ (+ 100 (let/cc k (+ 10 (k 1))))
+ |---------------------|
+
+This time, during the evaluation of `(+ 10 (k 1))`, we supply `1` to `k`. So then the local continuation, which delivers the value up to `(+ 10 [_])` and so on, is discarded. Instead `1` gets supplied to the outer continuation in place when `let/cc` was invoked. That will be `(+ 100 [_])`. When `(+ 100 1)` is evaluated, there's no more of the computation left to evaluate. So the answer here is `101`.
+
+You are not restricted to calling a bound continuation only once, nor are you restricted to calling it only inside of the `call/cc` (or `let/cc`) block. For example, you can do this:
+
+ (let ([p (let/cc k (cons 1 k))])
+ (cons (car p) ((cdr p) (cons 2 (lambda (x) x)))))
+ ; evaluates to '(2 2 . #<procedure>)
+
+What happens here? First, we capture the continuation where `p` is about to be assigned a value. Inside the `let/cc` block, we create a pair consisting of `1` and the captured continuation. This pair is bound to p. We then proceed to extract the components of the pair. The head (`car`) goes into the start of a tuple we're building up. To get the next piece of the tuple, we extract the second component of `p` (this is the bound continuation `k`) and we apply it to a pair consisting of `2` and the identity function. Supplying arguments to `k` takes us back to the point where `p` is about to be assigned a value. The tuple we had formerly been building, starting with `1`, will no longer be accessible because we didn't bring along with us any way to refer to it, and we'll never get back to the context where we supplied an argument to `k`. Now `p` gets assigned not the result of `(let/cc k (cons 1 k))` again, but instead, the new pair that we provided: `'(2 . #<identity procedure>)`. Again we proceed to build up a tuple: we take the first element `2`, then we take the second element (now the identity function), and feed it a pair `'(2 . #<identity procedure>)`, and since it's an argument to the identity procedure that's also the result. So our final result is a nested pair, whose first element is `2` and whose second element is the pair `'(2 . #<identity procedure>)`. Racket displays this nested pair like this:
+
+ '(2 2 . #<procedure>)
+
+
+---
+
+Some callcc/letcc exercises
+---------------------------
+
+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](/assignment8/) and [here](/week1/) and [here](/translating_between_ocaml_scheme_and_haskell). 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](/hints/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](/hints/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](/hints/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](/hints/cps_hint_4), but again, first try to figure it out for yourself.
+
+
+Delimited control operators
+===========================
+
+Here again is the CPS transform for `callcc`:
+
+ [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v)
+
+`callcc` is what's known as an *undelimited control operator*. That is, the continuations `outk` that get bound into our `k`s include all the code from the `call/cc ...` out to *and including* the end of the program. Calling such a continuation will never return any value to the call site.
+
+(See the technique employed in the `delta` example above, with the `(begin (let/cc k2 ...) ...)`, for a work-around. Also. if you've got a copy of *The Seasoned Schemer*, see the comparison of let/cc vs. "collector-using" (that is, partly CPS) functions at pp. 155-164.)
+
+Often times it's more useful to use a different pattern, where we instead capture only the code from the invocation of our control operator out to a certain boundary, not including the end of the program. These are called *delimited control operators*. A variety of these have been formulated. The most well-behaved from where we're coming from is the pair `reset` and `shift`. `reset` sets the boundary, and `shift` binds the continuation from the position where it's invoked out to that boundary.
+
+It works like this:
+
+ (1) outer code
+ ------- reset -------
+ | (2) |
+ | +----shift k ---+ |
+ | | (3) | |
+ | | | |
+ | | | |
+ | +---------------+ |
+ | (4) |
+ +-------------------+
+ (5) more outer code
+
+First, the code in position (1) runs. Ignore position (2) for the moment. When we hit the `shift k`, the continuation between the `shift` and the `reset` will be captured and bound to `k`. Then the code in position (3) will run, with `k` so bound. The code in position (4) will never run, unless it's invoked through `k`. If the code in position (3) just ends with a regular value, and doesn't apply `k`, then the value returned by (3) is passed to (5) and the computation continues.
+
+So it's as though the middle box---the (2) and (4) region---is by default not evaluated. This code is instead bound to `k`, and it's up to other code whether and when to apply `k` to any argument. If `k` is applied to an argument, then what happens? Well it will be as if that were the argument supplied by (3) only now that argument does go to the code (4) syntactically enclosing (3). When (4) is finished, that value also goes to (5) (just as (3)'s value did when it ended with a regular value). `k` can be applied repeatedly, and every time the computation will traverse that same path from (4) into (5).
+
+I set (2) aside a moment ago. The story we just told is a bit too simple because the code in (2) needs to be evaluated because some of it may be relied on in (3).
+
+For instance, in Scheme this:
+
+ (require racket/control)
+
+ (reset
+ (let ([x 1])
+ (+ 10 (shift k x))))
+
+will return 1. The `(let ([x 1]) ...` part is evaluated, but the `(+ 10 ...` part is not.
+
+Notice we had to preface the Scheme code with `(require racket/control)`. You don't have to do anything special to use `call/cc` or `let/cc`; but to use the other control operators we'll discuss you do have to include that preface in Racket.
+
+This pattern should look somewhat familiar. Recall from our discussion of aborts, and repeated at the top of this page:
+
+ let foo x =
+ +---try begin----------------+
+ | (if x = 1 then 10 |
+ | else abort 20 |
+ | ) + 100 |
+ +---end----------------------+
+ in (foo 2) + 1000;;
+
+The box is working like a reset. The `abort` is implemented with a `shift`. Earlier, we refactored our code into a more CPS form:
+
+ let x = 2
+ in let snapshot = fun box ->
+ let foo_result = box
+ in (foo_result) + 1000
+ in let continue_normally = fun from_value ->
+ let value = from_value + 100
+ in snapshot value
+ in
+ if x = 1 then continue_normally 10
+ else snapshot 20;;
+
+`snapshot` here corresponds to the code outside the `reset`. `continue_normally` is the middle block of code, between the `shift` and its surrounding `reset`. This is what gets bound to the `k` in our `shift`. The `if...` statement is inside a `shift`. Notice there that we invoke the bound continuation to "continue normally". We just invoke the outer continuation, saved in `snapshot` when we placed the `reset`, to skip the "continue normally" code and immediately abort to outside the box.
+
+---
+
+Examples of shift/reset/abort
+-----------------------------
+
+Here are some more examples of using delimited control operators. We present each example three ways: first a Scheme formulation; then we compute the same result using CPS and the lambda evaluator; then we do the same using the Continuation monad in OCaml. (We don't demonstrate the use of Oleg's delimcc library.)
+
+
+Example 1:
+
+ ; (+ 1000 (+ 100 (abort 11))) ~~> 11
+
+ app2 (op2 plus) (var thousand)
+ (app2 (op2 plus) (var hundred) (abort (var eleven)))
+
+ # Continuation_monad.(run0(
+ abort 11 >>= fun i ->
+ unit (100+i) >>= fun j ->
+ unit (1000+j)));;
+ - : int = 11
+
+When no `reset` is specified, there's understood to be an implicit one surrounding the entire computation (but unlike in the case of `callcc`, you still can't capture up to *and including* the end of the computation). So it makes no difference if we say instead:
+
+ # Continuation_monad.(run0(
+ reset (
+ abort 11 >>= fun i ->
+ unit (100+i) >>= fun j ->
+ unit (1000+j))));;
+ - : int = 11
+
+
+Example 2:
+
+ ; (+ 1000 (reset (+ 100 (abort 11)))) ~~> 1011
+
+ app2 (op2 plus) (var thousand)
+ (reset (app2 (op2 plus) (var hundred) (abort (var eleven))))
+
+ # Continuation_monad.(run0(
+ reset (
+ abort 11 >>= fun i ->
+ unit (100+i)
+ ) >>= fun j ->
+ unit (1000+j)));;
+ - : int = 1011
+
+Example 3:
+
+ ; (+ 1000 (reset (+ 100 (shift k (+ 10 1))))) ~~> 1011
+
+ app2 (op2 plus) (var thousand)
+ (reset (app2 (op2 plus) (var hundred)
+ (shift (\k. ((op2 plus) (var ten) (var one))))))
+
+ Continuation_monad.(
+ let v = reset (
+ let u = shift (fun k -> unit (10 + 1))
+ in u >>= fun x -> unit (100 + x)
+ ) in let w = v >>= fun x -> unit (1000 + x)
+ in run0 w);;
+ - : int = 1011
+
+Example 4:
+
+ ; (+ 1000 (reset (+ 100 (shift k (k (+ 10 1)))))) ~~> 1111
+
+ app2 (op2 plus) (var thousand)
+ (reset (app2 (op2 plus) (var hundred)
+ (shift (\k. (app (var k) ((op2 plus) (var ten) (var one)))))))
+
+ Continuation_monad.(
+ let v = reset (
+ let u = shift (fun k -> k (10 :: [1]))
+ in u >>= fun x -> unit (100 :: x)
+ ) in let w = v >>= fun x -> unit (1000 :: x)
+ in run0 w);;
+ - : int list = [1000; 100; 10; 1]
+
+To demonstrate the different adding order between Examples 4 and 5, we use `::` in the OCaml version instead of `+`. Here is Example 5:
+
+ ; (+ 1000 (reset (+ 100 (shift k (+ 10 (k 1)))))) ~~> 1111 but added differently
+
+ app2 (op2 plus) (var thousand)
+ (reset (app2 (op2 plus) (var hundred)
+ (shift (\k. ((op2 plus) (var ten) (app (var k) (var one)))))))
+
+ Continuation_monad.(let v = reset (
+ let u = shift (fun k -> k [1] >>= fun x -> unit (10 :: x))
+ in u >>= fun x -> unit (100 :: x)
+ ) in let w = v >>= fun x -> unit (1000 :: x)
+ in run0 w);;
+ - : int list = [1000; 10; 100; 1]
+
+
+Example 6:
+
+ ; (+ 100 ((reset (+ 10 (shift k k))) 1)) ~~> 111
+
+ app2 (op2 plus) (var hundred)
+ (app (reset (app2 (op2 plus) (var ten)
+ (shift (\k. (var k))))) (var one))
+
+ (* not sure if this example can be typed as-is in OCaml... this is the best I an do at the moment... *)
+
+ # type 'x either = Left of (int -> ('x,'x either) Continuation_monad.m) | Right of int;;
+ # Continuation_monad.(let v = reset (
+ shift (fun k -> unit (Left k)) >>= fun i -> unit (Right (10+i))
+ ) in let w = v >>= fun (Left k) ->
+ k 1 >>= fun (Right i) ->
+ unit (100+i)
+ in run0 w);;
+ - : int = 111
+
+<!--
+# type either = Left of (int -> either) | Right of int;;
+# let getleft e = match e with Left lft -> lft | Right _ -> failwith "not a Left";;
+# let getright e = match e with Right rt -> rt | Left _ -> failwith "not a Right";;
+# 100 + getright (let v = reset (fun p () -> Right (10 + shift p (fun k -> Left k))) in getleft v 1);;
+-->
+
+Example 7:
+
+ ; (+ 100 (reset (+ 10 (shift k (k (k 1)))))) ~~> 121
+
+ app2 (op2 plus) (var hundred)
+ (reset (app2 (op2 plus) (var ten)
+ (shift (\k. app (var k) (app (var k) (var one))))))
+
+ Continuation_monad.(let v = reset (
+ let u = shift (fun k -> k 1 >>= fun x -> k x)
+ in u >>= fun x -> unit (10 + x)
+ ) in let w = v >>= fun x -> unit (100 + x)
+ in run0 w)
+ - : int = 121
+
+<!--
+
+ print_endline "=== pa_monad's Continuation Tests ============";;
+
+ (1, 5 = C.(run0 (unit 1 >>= fun x -> unit (x+4))) );;
+ (2, 9 = C.(run0 (reset (unit 5 >>= fun x -> unit (x+4)))) );;
+ (3, 9 = C.(run0 (reset (abort 5 >>= fun y -> unit (y+6)) >>= fun x -> unit (x+4))) );;
+ (4, 9 = C.(run0 (reset (reset (abort 5 >>= fun y -> unit (y+6))) >>= fun x -> unit (x+4))) );;
+ (5, 27 = C.(run0 (
+ let c = reset(abort 5 >>= fun y -> unit (y+6))
+ in reset(c >>= fun v1 -> abort 7 >>= fun v2 -> unit (v2+10) ) >>= fun x -> unit (x+20))) );;
+
+ (7, 117 = C.(run0 (reset (shift (fun sk -> sk 3 >>= sk >>= fun v3 -> unit (v3+100) ) >>= fun v1 -> unit (v1+2)) >>= fun x -> unit (x+10))) );;
+
+ (8, 115 = C.(run0 (reset (shift (fun sk -> sk 3 >>= fun v3 -> unit (v3+100)) >>= fun v1 -> unit (v1+2)) >>= fun x -> unit (x+10))) );;
+
+ (12, ["a"] = C.(run0 (reset (shift (fun f -> f [] >>= fun t -> unit ("a"::t) ) >>= fun xv -> shift (fun _ -> unit xv)))) );;
+
+
+ (0, 15 = C.(run0 (let f k = k 10 >>= fun v-> unit (v+100) in reset (callcc f >>= fun v -> unit (v+5)))) );;
+
+-->
[[!toc]]
+## Coroutines ##
-The technique illustrated here with our fringe enumerators is a powerful and important one. It's an example of what's sometimes called **cooperative threading**. A "thread" is a subprogram that the main computation spawns off. Threads are called "cooperative" when the code of the main computation and the thread fixes when control passes back and forth between them. (When the code doesn't control this---for example, it's determined by the operating system or the hardware in ways that the programmer can't predict---that's called "preemptive threading.") Cooperative threads are also sometimes called *coroutines* or *generators*.
+Recall [[the recent homework assignment|/exercises/assignment12]] where you solved the same-fringe problem with a `make_fringe_enumerator` function, or in the Scheme version using streams instead of zippers, with a `lazy-flatten` function.
+
+The technique illustrated in those solutions is a powerful and important one. It's an example of what's sometimes called **cooperative threading**. A "thread" is a subprogram that the main computation spawns off. Threads are called "cooperative" when the code of the main computation and the thread fixes when control passes back and forth between them. (When the code doesn't control this---for example, it's determined by the operating system or the hardware in ways that the programmer can't predict---that's called "preemptive threading.") Cooperative threads are also sometimes called *coroutines* or *generators*.
With cooperative threads, one typically yields control to the thread, and then back again to the main program, multiple times. Here's the pattern in which that happens in our `same_fringe` function:
<!-- * [[!wikipedia Green_threads]]
* [[!wikipedia Protothreads]] -->
-The way we built cooperative threads here crucially relied on two heavyweight tools. First, it relied on our having a data structure (the tree zipper) capable of being a static snapshot of where we left off in the tree whose fringe we're enumerating. Second, it relied on our using mutable reference cells so that we could update what the current snapshot (that is, tree zipper) was, so that the next invocation of the `next_leaf` function could start up again where the previous invocation left off.
+The way we built cooperative threads using `make_fringe_enumerator` crucially relied on two heavyweight tools. First, it relied on our having a data structure (the tree zipper) capable of being a static snapshot of where we left off in the tree whose fringe we're enumerating. Second, it either required us to manually save and restore the thread's snapshotted state (a tree zipper); or else we had to use a mutable reference cell to save and restore that state for us. Using the saved state, the next invocation of the `next_leaf` function could start up again where the previous invocation left off.
+
+It's possible to build cooperative threads without using those tools, however. Already our [[solution using streams|/exercises/assignment12#streams2]] uses neither zippers nor any mutation. Instead it saves the thread's state in explicitly-created thunks, and resumes the thread by forcing the thunk.
-It's possible to build cooperative threads without using those tools, however. Some languages have a native syntax for them. Here's how we'd write the same-fringe solution above using native coroutines in the language Lua:
+Some languages have a native syntax for coroutines. Here's how we'd write the same-fringe solution above using native coroutines in the language Lua:
> function fringe_enumerator (tree)
if tree.leaf then
To get a better understanding of how that execution pattern works, we'll add yet a second execution pattern to our plate, and then think about what they have in common.
-While writing OCaml code, you've probably come across errors. In fact, you've probably come across errors of two sorts. One sort of error comes about when you've got syntax errors or type errors and the OCaml interpreter isn't even able to understand your code:
+While writing OCaml code, you've probably come across errors. In fact, you've probably come across errors of several sorts. One sort of error comes about when you've got syntax errors and the OCaml interpreter isn't even able to parse your code. A second sort of error is type errors, as in:
# let lst = [1; 2] in
"a" :: lst;;
Error: This expression has type int list
but an expression was expected of type string list
-But you may also have encountered other kinds of error, that arise while your program is running. For example:
+Type errors are also detected and reported before OCaml attempts to execute or evaluate your code. But you may also have encountered a third kind of error, that arises while your program is running. For example:
# 1/0;;
Exception: Division_by_zero.
# List.nth [1;2] 10;;
Exception: Failure "nth".
-These "Exceptions" are **run-time errors**. OCaml will automatically detect some of them, like when you attempt to divide by zero. Other exceptions are *raised* by code. For instance, here is the implementation of `List.nth`:
+These "Exceptions" are **run-time errors**. OCaml will automatically detect some of them, like when you attempt to divide by zero. Other exceptions are *raised* by code. For instance, here is the standard implementation of `List.nth`:
let nth l n =
if n < 0 then invalid_arg "List.nth" else
| a::l -> if n = 0 then a else nth_aux l (n-1)
in nth_aux l n
-Notice the two clauses `invalid_arg "List.nth"` and `failwith "nth"`. These are two helper functions which are shorthand for:
+(The Juli8 version of `List.nth` only differs in sometimes raising a different error.) Notice the two clauses `invalid_arg "List.nth"` and `failwith "nth"`. These are two helper functions which are shorthand for:
raise (Invalid_argument "List.nth");;
raise (Failure "nth");;
raise bad
-the effect is for the program to immediately stop. That's not exactly true. You can also programmatically arrange to *catch* errors, without the program necessarily stopping. In OCaml we do that with a `try ... with PATTERN -> ...` construct, analogous to the `match ... with PATTERN -> ...` construct:
+the effect is for the program to immediately stop. That's not exactly true. You can also programmatically arrange to *catch* errors, without the program necessarily stopping. In OCaml we do that with a `try ... with PATTERN -> ...` construct, analogous to the `match ... with PATTERN -> ...` construct. (In OCaml 4.02 and higher, there is also a more inclusive construct that combines these, `match ... with PATTERN -> ... | exception PATTERN -> ...`.)
# let foo x =
try
*and that exception is never caught*, then the effect is for the program to immediately stop.
-Trivia: what's the type of the `raise (Failure "two")` in:
+**Trivia**: what's the type of the `raise (Failure "two")` in:
if x = 1 then 10
else raise (Failure "two")
(fun x -> raise (Failure "two") : 'a -> 'a)
-Remind you of anything we discussed earlier? /Trivia.
+Remind you of anything we discussed earlier? (At one point earlier in term we were asking whether you could come up with any functions of type `'a -> 'a` other than the identity function.)
+
+**/Trivia.**
Of course, it's possible to handle errors in other ways too. There's no reason why the implementation of `List.nth` *had* to raise an exception. They might instead have returned `Some a` when the list had an nth member `a`, and `None` when it does not. But it's pedagogically useful for us to think about the exception-raising pattern now.
Here we call `foo bar 0`, and `foo` in turn calls `bar 0`, and `bar` raises the exception. Since there's no matching `try ... with ...` block in `bar`, we percolate back up the history of who called that function, and we find a matching `try ... with ...` block in `foo`. This catches the error and so then the `try ... with ...` block in `foo` (the code that called `bar` in the first place) will evaluate to `20`.
-OK, now this exception-handling apparatus does exemplify the second execution pattern we want to focus on. But it may bring it into clearer focus if we simplify the pattern even more. Imagine we could write code like this instead:
+OK, now this exception-handling apparatus does exemplify the second execution pattern we want to focus on. But it may bring it into clearer focus if we **simplify the pattern** even more. Imagine we could write code like this instead:
# let foo x =
try begin
else
return 20 -- abort early
end
- return value + 100 -- in Lua, a function's normal value
- -- must always also be explicitly returned
+ return value + 100 -- in a language like Scheme, you could omit the `return` here
+ -- but in Lua, a function's normal result must always be explicitly `return`ed
end
> return foo(1)
##What do these have in common?##
-In both of these patterns, we need to have some way to take a snapshot of where we are in the evaluation of a complex piece of code, so that we might later resume execution at that point. In the coroutine example, the two threads need to have a snapshot of where they were in the enumeration of their tree's leaves. In the abort example, we need to have a snapshot of where to pick up again if some embedded piece of code aborts. Sometimes we might distill that snapshot into a data structure like a zipper. But we might not always know how to do so; and learning how to think about these snapshots without the help of zippers will help us see patterns and similarities we might otherwise miss.
+In both of these patterns --- coroutines and exceptions/aborts --- we need to have some way to take a snapshot of where we are in the evaluation of a complex piece of code, so that we might later resume execution at that point. In the coroutine example, the two threads need to have a snapshot of where they were in the enumeration of their tree's leaves. In the abort example, we need to have a snapshot of where to pick up again if some embedded piece of code aborts. Sometimes we might distill that snapshot into a data structure like a zipper. But we might not always know how to do so; and learning how to think about these snapshots without the help of zippers will help us see patterns and similarities we might otherwise miss.
A more general way to think about these snapshots is to think of the code we're taking a snapshot of as a *function.* For example, in this code:
and we can think of the code starting with `let foo_result = ...` as a function, with the box being its parameter, like this:
+ let foo_result = < >
+ in foo_result + 100
+
+or, spelling out the gap `< >` as a bound variable:
+
fun box ->
let foo_result = box
in (foo_result) + 1000
The key idea behind working with continuations is that we're *inverting control*. In the fragment above, the code `(if x = 1 then ... else snapshot 20) + 100`---which is written as if it were to supply a value to the outside context that we snapshotted---itself *makes non-trivial use of* that snapshot. So it has to be able to refer to that snapshot; the snapshot has to somehow be available to our inside-the-box code as an *argument* or bound variable. That is: the code that is *written* like it's supplying an argument to the outside context is instead *getting that context as its own argument*. He who is written as value-supplying slave is instead become the outer context's master.
-In fact you've already seen this several times this semester---recall how in our implementation of pairs in the untyped lambda-calculus, the handler who wanted to use the pair's components had *in the first place to be supplied to the pair as an argument*. So the exotica from the end of the seminar was already on the scene in some of our earliest steps. Recall also what we did with v2 and v5 lists. Version 5 lists were the ones that let us abort a fold early:
-go back and re-read the material on "Aborting a Search Through a List" in [[Week4]].
+In fact you've already seen this several times this semester---recall how in our implementation of pairs in the untyped lambda-calculus, the handler who wanted to use the pair's components had *in the first place to be supplied to the pair as an argument*. So the exotica from the end of the seminar was already on the scene in some of our earliest steps. Recall also what we did with our [[abortable list traversals|/topics/week12_abortable_traversals]].
This inversion of control should also remind you of Montague's treatment of determiner phrases in ["The Proper Treatment of Quantification in Ordinary English"](http://www.blackwellpublishing.com/content/BPL_Images/Content_store/Sample_chapter/0631215417%5CPortner.pdf) (PTQ).