--- /dev/null
-Refunctionalizing list zippers
-------------------------------
++Refunctionalizing zippers: from lists to continuations
++------------------------------------------------------
+
+ If zippers are continuations reified (defuntionalized), then one route
+ to continuations is to re-functionalize a zipper. Then the
+ concreteness and understandability of the zipper provides a way of
+ understanding an equivalent treatment using continuations.
+
+ Let's work with lists of `char`s for a change. To maximize readability, we'll
+ indulge in an abbreviatory convention that "abSd" abbreviates the
+ list `['a'; 'b'; 'S'; 'd']`.
+
+ We will set out to compute a deceptively simple-seeming **task: given a
+ string, replace each occurrence of 'S' in that string with a copy of
+ the string up to that point.**
+
+ We'll define a function `t` (for "task") that maps strings to their
+ updated version.
+
+ Expected behavior:
+
+ t "abSd" ~~> "ababd"
+
+
+ In linguistic terms, this is a kind of anaphora
+ 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 task can give rise to considerable complexity.
+ Note that it matters which 'S' you target first (the position of the *
+ indicates the targeted 'S'):
+
+ t "aSbS"
+ *
+ ~~> t "aabS"
+ *
+ ~~> "aabaab"
+
+ versus
+
+ t "aSbS"
+ *
+ ~~> t "aSbaSb"
+ *
+ ~~> t "aabaSb"
+ *
+ ~~> "aabaaabab"
+
+ versus
+
+ t "aSbS"
+ *
+ ~~> t "aSbaSb"
+ *
+ ~~> t "aSbaaSbab"
+ *
+ ~~> t "aSbaaaSbaabab"
+ *
+ ~~> ...
+
-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.
+
+ 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` (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 unzipped part by pulling the zipper down until the
+ entire list has been unzipped (and so the zipped half of the zipper is empty).
+
+ 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']
+
+ # tz ([], ['a'; 'S'; 'b'; 'S']);;
+ - : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b']
+
+ Note that this implementation enforces the evaluate-leftmost rule.
+ Task completed.
+
+ 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
+ simple list.
+
+ # #trace tz;;
+ t1 is now traced.
+ # tz ([], ['a'; 'b'; 'S'; 'd']);;
+ tz <-- ([], ['a'; 'b'; 'S'; 'd'])
+ tz <-- (['a'], ['b'; 'S'; 'd']) (* Pull zipper *)
+ tz <-- (['b'; 'a'], ['S'; 'd']) (* Pull zipper *)
+ tz <-- (['b'; 'a'; 'b'; 'a'], ['d']) (* Special step *)
+ tz <-- (['d'; 'b'; 'a'; 'b'; 'a'], []) (* Pull zipper *)
+ tz --> ['a'; 'b'; 'a'; 'b'; 'd'] (* Output reversed *)
+ tz --> ['a'; 'b'; 'a'; 'b'; 'd']
+ tz --> ['a'; 'b'; 'a'; 'b'; 'd']
+ tz --> ['a'; 'b'; 'a'; 'b'; 'd']
+ tz --> ['a'; 'b'; 'a'; 'b'; 'd']
+ - : char list = ['a'; 'b'; 'a'; 'b'; 'd']
+
+ The nice thing about computations involving lists is that it's so easy
+ 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 zipper 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,
+ `make_list 'a' (make_list 'b' (make_list 'S' (make_list 'd' empty)))`). The
+ recipe for constructing the list goes like this:
+
+ > (0) Start with the empty list []
+ > (1) make a new list whose first element is 'd' and whose tail is the list constructed in step (0)
+ > (2) make a new list whose first element is 'S' and whose tail is the list constructed in step (1)
+ > -----------------------------------------
+ > (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)
+
+ 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
+ (or group of steps) a **continuation** of the previous steps. 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
++zipper as a continuation: a function
+ describing how to finish building a list. We'll write a new
+ function, `tc` (for task with continuations), that will take an input
+ list (not a zipper!) and a continuation `k` (it's conventional to use `k` for continuation variables) 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:
+
+ 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) (k: (char list) -> (char list)) =
+ match l with
+ | [] -> List.rev (k [])
+ | 'S'::zipped -> tc zipped (fun tail -> k (k tail))
+ | target::zipped -> tc zipped (fun tail -> target::(k tail));;
+
+ # tc ['a'; 'b'; 'S'; 'd'] (fun tail -> tail);;
+ - : char list = ['a'; 'b'; 'a'; 'b']
+
+ # tc ['a'; 'S'; 'b'; 'S'] (fun tail -> tail);;
+ - : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b']
+
-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
+ four recursive calls to `tc`, and `zipped` will take on the values
+ `"bSd"`, `"Sd"`, `"d"`, and `""` (and, once again, on the final call,
+ the first `match` clause will fire, so the the variable `zipped` will
+ not be instantiated).
+
-I have not called the functional argument `unzipped`, although that is
++We have not called the functional argument `unzipped`, although that is
+ what the parallel would suggest. The reason is that `unzipped` is a
+ list, but `k` is a function. 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 (and
-relatively inefficient) `List.append`.
++together the two instances of `unzipped` with an explicit (and,
++computationally speaking, relatively inefficient) `List.append`.
+ In the `tc` version of the task, we simply compose `k` with itself:
+ `k o k = fun tail -> k (k tail)`.
+
+ A call `tc ['a'; 'b'; 'S'; 'd']` yields a partially-applied function; it still waits for another argument, a continuation of type `char list -> char list`. We have to give it an "initial continuation" to get started. Here we supply *the identity function* as the initial continuation. Why did we choose that? Well, if
+ you have already constructed the initial list `"abSd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"abSd"`? Clearly, the identity function.
+
+ A good way to test your understanding is to figure out what the
+ continuation function `k` must be at the point in the computation when
+ `tc` is called with the first argument `"Sd"`. Two choices: is it
+ `fun tail -> 'a'::'b'::tail`, or it is `fun tail -> 'b'::'a'::tail`? The way to see if
+ you're right is to execute the following command and see what happens:
+
+ tc ['S'; 'd'] (fun tail -> 'a'::'b'::tail);;
+
+ There are a number of interesting directions we can go with this task.
+ 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 continuation operator. (It works like the Scheme operators `shift` or `control`; the differences between them don't manifest themselves in this example.) 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 way to extend this exercise would be to add a special symbol `'#'`,
+ and then the task would be to copy from the target `'S'` only back to
+ the closest `'#'`. This would allow our task to simulate delimited
+ continuations with embedded `prompt`s (also called `reset`s).
+
+ The reason the task is well-suited to the list zipper is in part
+ because the list monad has an intimate connection with continuations.
+ We'll explore this next.
+
+