-
Refunctionalizing zippers: from lists to continuations
------------------------------------------------------
resolution, where `'S'` is functioning like an anaphoric element, and
the preceding string portion is the antecedent.
-This deceptively simple task gives rise to some mind-bending complexity.
+This simple task gives rise to considerable complexity.
Note that it matters which 'S' you target first (the position of the *
indicates the targeted 'S'):
~~> ...
</pre>
-Aparently, this task, as simple as it is, is a form of computation,
+Apparently, this task, as simple as it is, is a form of computation,
and the order in which the `'S'`s get evaluated can lead to divergent
behavior.
`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).
+move elements from the zipped part to the unzipped part by pulling the
+zipper down until the entire list has been unzipped (at which point
+the zipped half of the zipper will be empty).
<pre>
type 'a list_zipper = ('a list) * ('a list);;
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 *)
+ 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 *)
# tz ([], ['a'; 'b'; 'S'; 'd']);;
- : char list = ['a'; 'b'; 'a'; 'b'; 'd']
One way to see exactly what is going on is to watch the zipper in
action by tracing the execution of `tz`. By using the `#trace`
directive in the Ocaml interpreter, the system will print out the
-arguments to `tz` each time it is (recurcively) called. Note that the
+arguments to `tz` each time it is (recursively) 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
to visualize them as a data structure. Eventually, we want to get to
a place where we can talk about more abstract computations. In order
to get there, we'll first do the exact same thing we just did with
-concrete zipper using procedures.
+concrete zippers using procedures instead.
Think of a list as a procedural recipe: `['a'; 'b'; 'S'; 'd']`
is the result of the computation `a::(b::(S::(d::[])))` (or, in our old
-style, `makelist a (makelist b (makelist S (makelist c empty)))`).
+style, `makelist 'a' (makelist 'b' (makelist 'S' (makelist 'c' empty)))`).
The recipe for constructing the list goes like this:
<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
be a function of type `char list -> char list`. We'll call each step
-a **continuation** of the recipe. So in this context, a continuation
-is a function of type `char list -> char list`. For instance, the
-continuation corresponding to the portion of the recipe below the
-horizontal line is the function `fun (tail:char list) -> a::(b::tail)`.
-
-This means that we can now represent the unzipped part of our
-zipper--the part we've already unzipped--as a continuation: a function
-describing how to finish building the list. We'll write a new
-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. We've included the orginal
-`tz` to facilitate detailed comparison:
+(or group of steps) a **continuation** of the recipe. So in this
+context, a continuation is a function of type `char list -> char
+list`. For instance, the continuation corresponding to the portion of
+the recipe below the horizontal line is the function `fun (tail:char
+list) -> a::(b::tail)`.
+
+This means that we can now represent the unzipped part of our zipper
+as a continuation: a function describing how to finish building the
+list. We'll write a new 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.
+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 *)
+ 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 [])
| target::zipped -> tc zipped (fun x -> target::(c x));;
# tc ['a'; 'b'; 'S'; 'd'] (fun x -> x);;
-- : char list = ['a'; 'b'; 'a'; 'b']
+- : char list = ['a'; 'b'; 'a'; 'b'; 'd']
# tc ['a'; 'S'; 'b'; 'S'] (fun x -> x);;
- : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b']
</pre>
-To emphasize the parallel, I've re-used the names `zipped` and
+To emphasize the parallel, we've re-used the names `zipped` and
`target`. The trace of the procedure will show that these variables
take on the same values in the same series of steps as they did during
the execution of `tz` above. There will once again be one initial and
not be instantiated).
I have not called the functional argument `unzipped`, although that is
-what the parallel would suggest. The reason is that `unzipped` is a
-list, but `c` is a function. That's the most crucial difference, the
+what the parallel would suggest. The reason is that `unzipped` (in
+`tz`) is a list, but `c` (in `tc`) is a function. ('c' stands for
+'continuation', of course.) That's the most crucial difference, the
point of the excercise, and it should be emphasized. For instance,
you can see this difference in the fact that in `tz`, we have to glue
-together the two instances of `unzipped` with an explicit `List.append`.
-In the `tc` version of the task, we simply compose `c` with itself:
-`c o c = fun x -> c (c x)`.
+together the two instances of `unzipped` with an explicit (and
+relatively computationally inefficient) `List.append`. In the `tc`
+version of the task, we simply compose `c` with itself: `c o c = fun x
+-> c (c x)`.
Why use the identity function as the initial continuation? Well, if
-you have already constructed the list "abSd", what's the next step in
-the recipe to produce the desired result (which is the same list,
-"abSd")? Clearly, the identity continuation.
+you have already constructed the initial list `"abSd"`, what's the next
+step in the recipe to produce the desired result, i.e, the very same
+list, `"abSd"`? Clearly, the identity continuation.
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 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:
+`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
+The reason this task was chosen is because it 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`. 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 input list portrays a
+sequence 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
the closest `'#'`. This would allow the task to simulate delimited
-continuations (for right-branching computations).
+continuations with embedded prompts.
+
+The reason the task is well-suited to the list zipper is in part
+because the list monad has an intimate connection with continuations.
+The following section explores this connection. We'll return to the
+list task after talking about generalized quantifiers below.
+
-The task is well-suited to the list zipper because the list monad has
-an intimate connection with continuations. The following section
-makes this connection. We'll return to the list task after talking
-about generalized quantifiers below.