X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=from_list_zippers_to_continuations.mdwn;h=8b1fa68479842295a65ab01e7bd4d62885f93829;hp=07c348635117775683ff1af9461174e351dcf7b4;hb=d0a9dde6d449c9973b29704d7326ef978cba6da6;hpb=b73d55e2b19231870478f491d3f7a051a765c116 diff --git a/from_list_zippers_to_continuations.mdwn b/from_list_zippers_to_continuations.mdwn index 07c34863..8b1fa684 100644 --- a/from_list_zippers_to_continuations.mdwn +++ b/from_list_zippers_to_continuations.mdwn @@ -1,5 +1,5 @@ -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 @@ -26,7 +26,7 @@ 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'): @@ -58,7 +58,7 @@ versus * ~~> ... -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. @@ -70,15 +70,16 @@ This is a task well-suited to using a zipper. We'll define a function `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). +entire list has been unzipped, at which point the zipped half of the +zipper will be 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'] @@ -86,14 +87,15 @@ entire list has been unzipped (and so the zipped half of the zipper is empty). # tz ([], ['a'; 'S'; 'b'; 'S']);; - : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b'] -Note that this implementation enforces the evaluate-leftmost rule. -Task completed. +Note that the direction in which the zipper unzips 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 -lines with left-facing arrows (`<--`) show (recursive) calls to `tz`, +arguments to `tz` each time it is called, including when it is called +recursively within one of the `match` clauses. Note that the +lines with left-facing arrows (`<--`) show (both initial and 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. @@ -101,10 +103,10 @@ simple list. # #trace tz;; t1 is now traced. # tz ([], ['a'; 'b'; 'S'; 'd']);; - tz <-- ([], ['a'; 'b'; 'S'; 'd']) + tz <-- ([], ['a'; 'b'; 'S'; 'd']) (* Initial call *) tz <-- (['a'], ['b'; 'S'; 'd']) (* Pull zipper *) tz <-- (['b'; 'a'], ['S'; 'd']) (* Pull zipper *) - tz <-- (['b'; 'a'; 'b'; 'a'], ['d']) (* Special step *) + tz <-- (['b'; 'a'; 'b'; 'a'], ['d']) (* Special 'S' step *) tz <-- (['d'; 'b'; 'a'; 'b'; 'a'], []) (* Pull zipper *) tz --> ['a'; 'b'; 'a'; 'b'; 'd'] (* Output reversed *) tz --> ['a'; 'b'; 'a'; 'b'; 'd'] @@ -117,7 +119,7 @@ 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, @@ -134,17 +136,17 @@ recipe for constructing the list goes like this: 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 recipe. So in this +(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 and return a processed list. +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: @@ -155,11 +157,11 @@ some small but interesting differences. We've included the orginal | (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)) = + let rec tc (l: char list) (k: (char list) -> (char list)) = match l with - | [] -> List.rev (c []) - | 'S'::zipped -> tc zipped (fun tail -> c (c tail)) - | target::zipped -> tc zipped (fun tail -> target::(c tail));; + | [] -> 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'] @@ -167,40 +169,48 @@ some small but interesting differences. We've included the orginal # 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 +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 `zipper` will +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 -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 +We have not named the functional argument `unzipped`, although that is +what the parallel would suggest. The reason is that `unzipped` (in +`tz`) is a +list, but `k` (in `tc`) is a function. That's the most crucial +difference between the solutions---it's 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`. -In the `tc` version of the task, we simply compose `c` with itself: -`c o c = fun tail -> c (c tail)`. +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 `c` must be at the point in the computation when -`tc` is called with the first argument `"Sd"`. Two choices: is it +continuation function `k` must be at the point in the computation when +`tc` is applied to the 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 +The reason this task was chosen is because the task itself (as opposed +to the functions used to implement the task) 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 +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. +See Ken Shan's paper [Shift to control](http://www.cs.rutgers.edu/~ccshan/recur/recur.pdf), +which inspired some of the discussion in this topic.) +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 @@ -214,7 +224,6 @@ 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. -The following section explores this connection. We'll return to the -list task after talking about generalized quantifiers below. +We'll explore this next.