The next issue is whether the continuations are _delimited_ or not. In [[our discussion of aborts|week13_coroutines_exceptions_and_aborts#index3h2]], we had a box, and what `abort` did was skip the rest of the code inside the box and resume execution at the outside border of the box. This is the pattern of a **delimited continuation**, with the box being the delimiter. There are a bunch of different operators that have been proposed for dealing with delimited continuations. Many of them are interdefinable (though the interdefinitions are sometimes complex). We won't be trying to survey them all. The ones we'll suggest as a paradigm are the pair of `reset` and `shift`. The first of these marks where the box goes, and the second has two roles: (i) it marks where you should start skipping (if you're going to "skip the rest of the code inside the box"), and (ii) it specifies a variable `k` that we bind to the continuation representing that skipped code. Thus we have:
- initial outside code
- +---reset--------------------+
- | initial inside code |
- | shift k ( ... ) |
- | remaining inside code |
- +----------------------------+
- remaining outside code
+<pre>
+initial outside code
++---reset--------------------+
+| initial inside code |
+| shift k. ( ... ) |
+| <i>remaining inside code</i> |
++----------------------------+
+<i>remaining outside code</i>
+</pre>
-Really in the implementation of this there are _two_ continuations or snapshots being tracked. There's the potentially skipped code, represented by `remaining inside code` above; and there's also the continuation/snapshot that we resume with if we do skip that code, represented by `remaining outside code`. But only the first of these gets bound to a variable, `k` in the above diagram. What happens in this diagram is that `initial outside code` runs, then `initial inside code` runs, then `remaining inside code` is distilled into a function and bound to the variable `k`, then we run the `( ... )` code with `k` so bound. If that `( ... )` code invokes `k` by applying it to an argument, then `remaining inside code` is run as though the supplied argument were what the `shift k ( ... )` bit evaluated to. If the `( ... )` code doesn't invoke `k`, but just ends with a normal result like `10`, then the `remaining inside code` is skipped and we resume execution with the outside, implicitly snapshotted code `remaining outside code`.
+Really in the implementation of this there are _two_ continuations or snapshots being tracked. There's the potentially skipped code, represented by `remaining inside code` above; and there's also the continuation/snapshot that we resume with if we do skip that code, represented by `remaining outside code`. But only the first of these gets bound to a variable, `k` in the above diagram. What happens in this diagram is that `initial outside code` runs, then `initial inside code` runs, then `remaining inside code` is distilled into a function and bound to the variable `k`, then we run the `( ... )` code with `k` so bound. If that `( ... )` code invokes `k` by applying it to an argument, then `remaining inside code` is run as though the supplied argument were what the `shift k. ( ... )` bit evaluated to. If the `( ... )` code doesn't invoke `k`, but just ends with a normal result like `10`, then the `remaining inside code` is skipped and we resume execution with the outside, implicitly snapshotted code `remaining outside code`.
-You may encounter references to `prompt` and `control`. These are variants of `reset` and `shift` that differ in only subtle ways. As we said, there are lots of variants of these that we're not going to try to survey.
+You may encounter references to `prompt` and `control`. These are variants of `reset` and `shift` that differ in only subtle ways. As we said, there are [lots of variants of these](http://docs.racket-lang.org/reference/cont.html?q=abort#%28mod-path._racket%2Fcontrol%29) that we're not going to try to survey.
We talked before about `abort`. This can be expressed in terms of `reset` and `shift`. At the end of our discussion of abort, we said that this diagram:
100)))])
(+ (foo 2) 1000))
-That shows you how `abort` can be expressed in terms of `shift`. Rewriting the Scheme code into a more OCaml-ish syntax, it might look something like this:
+That shows you how `abort` can be expressed in terms of `shift`. (Notice that with `abort`, there's a special keyword used in the aborting branch but no keyword in the "continue normally" branch; but with `shift` it's the converse.) Rewriting the Scheme code into a more OCaml-ish syntax, it might look something like this:
let foo x = reset (shift k -> if x = 1 then k 10 else 20) + 100) in
foo 2 + 1000
# let shift fun_k = match !reset_label with
| None -> failwith "shift must be inside reset"
| Some p -> Delimcc.shift p fun_k;;
+ # let abort x = match !reset_label with
+ | None -> failwith "abort must be inside reset"
+ | Some p -> Delimcc.abort p x;;
-Also, the previous code has to be massaged a bit to have the right syntax. What you really need to write is:
+(I've added that to my `~/.ocamlinit` file so that it runs every time I start OCaml up. But note that the above code only works when the result types of your `reset` blocks are always the same throughout your whole OCaml session. For the toy examples we're working with, these result types are always `int`, so it's OK. But for more varied usage scenarios, you'd have to do something syntactically more complex.)
+
+Additionally, the previous code has to be massaged a bit to have the right syntax. What you really need to write is:
let foo x = reset (fun () -> shift (fun k -> if x = 1 then k 10 else 20) + 100) in
foo 2 + 1000
(call/cc (lambda (k) ...))
-`(let/cc k ...)` is a lot like `(shift k ...)` (or in the OCaml version, `shift (fun k -> ...)`), except that it doesn't need a surrounding `reset ( ... )` (in OCaml, `reset (fun () -> ...)`). For the undelimited continuation operator, the box is understood to be *the whole rest of the top-level computation*. If you're running a file, that's all the rest of the file that would have been executed after the syntactic hole filled by `(let/cc k ...)`. With `(shift k ...)`, the code that gets bound to `k` doesn't get executed unless you specifically invoke `k`; but `let/cc` works differently in this respect. Thus:
+`(let/cc k ...)` is a lot like `(shift k ...)` (or in the OCaml version, `shift (fun k -> ...)`), except that it doesn't need a surrounding `(reset ... )` (in OCaml, `reset (fun () -> ...)`). For the undelimited continuation operator, the box is understood to be *the whole rest of the top-level computation*. If you're running a file, that's all the rest of the file that would have been executed after the syntactic hole filled by `(let/cc k ...)`. With `(shift k ...)`, the code that gets bound to `k` doesn't get executed unless you specifically invoke `k`; but `let/cc` works differently in this respect. Thus:
(+ 100 (let/cc k 1))
returns `101`, whereas:
- (reset (+ 10 (shift k 1)))
+ (reset (+ 100 (shift k 1)))
+
+only returns `1`. It is possible to duplicate the behavior of `let/cc` using `reset`/`shift`, but you have to structure your code in certain ways to do it.
-only returns `1`. It is possible to duplicate the behavior of `let/cc` using `reset`/`shift`, but you have to structure your code in certain ways to do it. In order to duplicate the behavior of `reset`/`shift` using `let/cc`, you need to also make use of a mutable reference cell. So in that sense delimited continuations are more powerful and undelimited continuations are sort-of a special case.
+You can't duplicate the behavior of `reset`/`shift` using *only* `let/cc`, but you can do it if you *also* make use of a mutable reference cell. So in a way delimited continuations are more powerful, and undelimited continuations are sort-of a special case. (In the OCaml code above for using delimited continuations, there is a mutable reference cell `reset_label`, but this is just for convenience. Oleg's library is designed for use with _multiple_ reset blocks having different labels, and when you invoke `shift` you have to specify which labeled reset block you want to potentially skip the rest of. We haven't introduced that complexity into our discussion, so for convenience we worked around it in showing you how to use `reset` and `shift` in OCaml. And the mutable reference cell was only playing the role of enabling us to work around the need to explicitly specify the `reset` block's label.)
-(In the OCaml code above for using delimited continuations, there is a mutable reference cell `reset_label`, but this is just for convenience. Oleg's library is designed for use with _multiple_ reset blocks having different labels, then when you invoke `shift` you have to specify which labeled reset block you want to potentially skip the rest of. We haven't introduced that complexity into our discussion, so for convenience we worked around it in showing you how to use `reset` and `shift` in OCaml. And the mutable reference cell was only playing the role of enabling us to work around the need to explicitly specify the `reset` block's label.)
+You may have noticed in some of our Scheme code we had the preface `(require racket/control)`. You don't need to do anything special (in Racket) to use `call/cc` or `let/cc`, but you do need that preface to be able to use `reset` and `shift` and `abort`.
## Examples of using these continuation operators ##
Here are some examples of using these different continuation operators. The continuation that gets bound to `k` will be in bold. I'll use an OCaml-ish syntax because that's easiest to read, but these examples don't work as-is in OCaml. The `reset`/`shift` examples need to be massaged into the form displayed above for OCaml; and the `let/cc` examples don't work in OCaml because that's not provided. Alternatively, you could massage all of these into Scheme syntax. You shouldn't find that hard.
-1. <pre><b>100 + </b>let/cc k (10 + 1)</pre>
- This evaluates to `111`. Nothing exotic happens here.
+1. <pre><b>100 + </b>let/cc k. (10 + 1)</pre>
+ This evaluates to `111`. Nothing exotic happens here. As mentioned above, `let/cc` automatically feeds any normal result from its body to its surrounding continuation. You'd get the same result if you invoked the continuation explicitly, as in:
+ <pre><b>100 + </b>let/cc k. (k (10 + 1))</pre>
-2. <pre><b>100 + </b>let/cc k (10 + k 1)</pre>
- This evaluates to `101`. See also example 11, below.
+2. <pre><b>100 + </b>let/cc k. (10 + k 1)</pre>
+ `k` is again bound to `100 + < >`. Note that after invoking `k 1`, the rest of the body of `let/cc k. ( ... )` is discarded, so the result is simply `101`. See example 11, below, for contrast with `shift k. ( ... )`.
-3. <pre><b>let p = </b>let/cc k (1,k) <b>in
+3. You aren't restricted to calling a full-strength continuation function only once; nor are you restricted to calling it only inside the `let/cc` block. For example:
+ <pre><b>let p = </b>let/cc k. (1,k) <b>in
let y = snd p (2, ident) in
(fst p, y)</b></pre>
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:
+ In the second line, we extract the continuation function from the pair `p` and apply it to the argument `(2, ident)`. That results in us discarding the rest of *that* computation and instead executing the following:
<pre><b>let p = </b>(2, ident) <b>in
let y = snd p (2, ident) in
(fst p, y)</b></pre>
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. <pre><b>1000 + (100 + </b>abort 11<b>)</b></pre>
- 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.
+ 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. (This will work in Scheme but not in OCaml.)
5. <pre>1000 + reset <b>(100 + </b>abort 11<b>)</b></pre>
Here 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. <pre>1000 + reset <b>(100 + </b>shift k (10 + 1)<b>)</b></pre>
- Equivalent 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`.
+6. <pre>1000 + reset <b>(100 + </b>shift k. (10 + 1)<b>)</b></pre>
+ Equivalent 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`. (Contrast example 1.)
-7. <pre>1000 + reset <b>(100 + </b>shift k (k (10 + 1))<b>)</b></pre>
+7. <pre>1000 + reset <b>(100 + </b>shift k. (k (10 + 1))<b>)</b></pre>
Here 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.
+ 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. <pre>1000 + reset <b>(100 + </b>shift k (10 + k 1)<b>)</b></pre>
- This 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.)
+8. <pre>1000 + reset <b>(100 + </b>shift k. (10 + k 1)<b>)</b></pre>
+ This 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 `1` is added to `10` and `100` is different. If we used a non-commutative operation instead of `+`, the results of these two examples would be different from each other.)
-9. <pre>1000 + reset <b>(100 + </b>shift k (k)<b>)</b> 1</pre>
- Here `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`.
+9. <pre>1000 + reset <b>(100 + </b>shift k. (k)<b>)</b> 1</pre>
+ Here `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. <pre>1000 + reset <b>(100 + </b>shift k (k (k 1))<b>)</b></pre>
+10. <pre>1000 + reset <b>(100 + </b>shift k. (k (k 1))<b>)</b></pre>
Here `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:
- <pre><b>100 + </b>let/cc k (10 + k 1)</pre>
- which evaluated to `101`. The parallel code where we instead capture the continuation using `shift k ( ... )` would look like this:
- <pre>reset <b>(100 + </b>shift k (10 + k 1)<b>)</b></pre>
- 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`.
+11. Here's another comparison of `let/cc` to `shift`. Recall example 2 above was:
+ <pre><b>100 + </b>let/cc k. (10 + k 1)</pre>
+ which evaluated to `101`. The parallel code where we instead capture the continuation using `shift k. ( ... )` would look like this:
+ <pre>reset <b>(100 + </b>shift k. (10 + k 1)<b>)</b></pre>
+ But this evaluates differently, as we saw in example 8. 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.