##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 datastructure 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:
+ let foo x =
+ try
+ (if x = 1 then 10
+ else abort 20) + 1
+ end
+ in (foo 2) + 1;;
+
+we can imagine a box:
+
+ let foo x =
+ +---------------------------+
+ | try |
+ | (if x = 1 then 10 |
+ | else abort 20) + 1 |
+ | end |
+ +---------------------------+
+ in (foo 2) + 1;;
+
+and as we're about to enter the box, we want to take a snapshot of the code *outside* the box. If we decide to abort, we'd be aborting to that snapshotted code.
+
+<!--
+# #require "delimcc";;
+# open Delimcc;;
+# let reset body = let p = new_prompt () in push_prompt p (body p);;
+val reset : ('a Delimcc.prompt -> unit -> 'a) -> 'a = <fun>
+# let foo x = reset(fun p () -> (shift p (fun k -> if x = 1 then k 10 else 20)) + 1) in (foo 1) + 100;;
+- : int = 111
+# let foo x = reset(fun p () -> (shift p (fun k -> if x = 1 then k 10 else 20)) + 1) in (foo 2) + 100;;
+- : int = 120
+-->
and the order in which the `'S'`s get evaluated can lead to divergent
behavior.
-For now, we'll agree to always evaluate the leftmost `'S'`.
+For now, we'll agree to always evaluate the leftmost `'S'`, which
+guarantees termination, and a final string without any `'S'` in it.
This is a task well-suited to using a zipper. We'll define a function
-`tz`, which accomplished the task by mapping a char list zipper to a
-char list. We'll call the two parts of the zipper `unzipped` and
-`zipped`; we start with a fully zipped list, and move elements to the
-zipped part by pulling the zipped down until the zipped part is empty.
+`tz` (for task with zippers), which accomplishes the task by mapping a
+char list zipper to a char list. We'll call the two parts of the
+zipper `unzipped` and `zipped`; we start with a fully zipped list, and
+move elements to the zipped part by pulling the zipped down until the
+entire list has been unzipped (and so the zipped half of the zipper is empty).
<pre>
type 'a list_zipper = ('a list) * ('a list);;
Task completed.
One way to see exactly what is going on is to watch the zipper in
-action by tracing the execution of `t1`. By using the `#trace`
+action by tracing the execution of `tz`. By using the `#trace`
directive in the Ocaml interpreter, the system will print out the
-arguments to `t1` each time it is (recurcively) called. Note that the
+arguments to `tz` each time it is (recurcively) called. Note that the
lines with left-facing arrows (`<--`) show (recursive) calls to `tz`,
giving the value of its argument (a zipper), and the lines with
right-facing arrows (`-->`) show the output of each recursive call, a
-list.
+simple list.
<pre>
# #trace tz;;
-----------------------------------------
(3) make a new list whose first element is 'b' and whose tail is the list constructed in step (2)
(4) make a new list whose first element is 'a' and whose tail is the list constructed in step (3)
-<pre>
+</pre>
What is the type of each of these steps? Well, it will be a function
from the result of the previous step (a list) to a new list: it will
function, `tc` (for task with continuations), that will take an input
list (not a zipper!) and a continuation and return a processed list.
The structure and the behavior will follow that of `tz` above, with
-some small but interesting differences:
+some small but interesting differences. We've included the orginal
+`tz` to facilitate detailed comparison:
<pre>
+let rec tz (z:char list_zipper) =
+ match z with (unzipped, []) -> List.rev(unzipped) (* Done! *)
+ | (unzipped, 'S'::zipped) -> tz ((List.append unzipped unzipped), zipped)
+ | (unzipped, target::zipped) -> tz (target::unzipped, zipped);; (* Pull zipper *)
+
let rec tc (l: char list) (c: (char list) -> (char list)) =
match l with [] -> List.rev (c [])
| 'S'::zipped -> tc zipped (fun x -> c (c x))
A good way to test your understanding is to figure out what the
continuation function `c` must be at the point in the computation when
-`tc` is called with
+`tc` is called with the first argument `"Sd"`. Two choices: is it
+`fun x -> a::b::x`, or it is `fun x -> b::a::x`?
+The way to see if you're right is to execute the following
+command and see what happens:
+
+ tc ['S'; 'd'] (fun x -> 'a'::'b'::x);;
There are a number of interesting directions we can go with this task.
The task was chosen because the computation can be viewed as a
simplified picture of a computation using continuations, where `'S'`
plays the role of a control operator with some similarities to what is
-often called `shift`. &sset; &integral; In the analogy, the list
-portrays a string of functional applications, where `[f1; f2; f3; x]`
-represents `f1(f2(f3 x))`. The limitation of the analogy is that it
-is only possible to represent computations in which the applications
-are always right-branching, i.e., the computation `((f1 f2) f3) x`
-cannot be directly represented.
+often called `shift`. In the analogy, the list portrays a string of
+functional applications, where `[f1; f2; f3; x]` represents `f1(f2(f3
+x))`. The limitation of the analogy is that it is only possible to
+represent computations in which the applications are always
+right-branching, i.e., the computation `((f1 f2) f3) x` cannot be
+directly represented.
One possibile development is that we could add a special symbol `'#'`,
and then the task would be to copy from the target `'S'` only back to