X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=from_list_zippers_to_continuations.mdwn;fp=from_list_zippers_to_continuations.mdwn;h=1ef5f9c065fc670a15e571c3b36eb2ba15092d77;hp=3890f909d801bc2eacf88d23202938cbc716b29f;hb=0feebbaaa58403d836d7ea6166cf709dd3faf1a8;hpb=787a842deca12cc0a1d2bc14006f000a5eb4c07d diff --git a/from_list_zippers_to_continuations.mdwn b/from_list_zippers_to_continuations.mdwn index 3890f909..1ef5f9c0 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. @@ -75,10 +75,10 @@ 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'] @@ -92,7 +92,7 @@ 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 @@ -117,7 +117,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, @@ -141,7 +141,7 @@ 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. @@ -167,7 +167,7 @@ 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 @@ -176,13 +176,13 @@ four recursive calls to `tc`, and `zipped` will take on the values 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)`.