X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=from_list_zippers_to_continuations.mdwn;h=dcd11cec2181b4b98f37477e0fbd693ba889a7fa;hp=8b1fa68479842295a65ab01e7bd4d62885f93829;hb=9fe62083953213cce34fc4458e36666902c5ee4b;hpb=67cfadf1ab1d26bfa2e40ba5a675fbcdd7ea5e01 diff --git a/from_list_zippers_to_continuations.mdwn b/from_list_zippers_to_continuations.mdwn index 8b1fa684..dcd11cec 100644 --- a/from_list_zippers_to_continuations.mdwn +++ b/from_list_zippers_to_continuations.mdwn @@ -6,9 +6,9 @@ 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']`. +Let's work with lists of `char`s for a change. We'll sometimes write +"abSd" as an abbreviation for +`['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 @@ -121,14 +121,14 @@ 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 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 +Think of a list as a procedural recipe: `['a'; 'b'; 'c'; 'd']` is the result of +the computation `'a'::('b'::('c'::('d'::[])))` (or, in our old style, +`make_list 'a' (make_list 'b' (make_list 'c' (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) +> (2) make a new list whose first element is 'c' 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) @@ -140,16 +140,11 @@ be a function of type `char list -> char list`. We'll call each step 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)`. +list) -> 'a'::('b'::tail)`. What is the continuation of the 4th step? That is, after we've built up `'a'::('b'::('c'::('d'::[])))`, what more has to happen to that for it to become the list `['a'; 'b'; 'c'; 'd']`? Nothing! Its continuation is the function that does nothing: `fun tail -> tail`. -This means that we can now represent the unzipped part of our -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: +In what follows, we'll be thinking about the result list that we're building up in this procedural way. We'll treat our input list just as a plain old static list data structure, that we recurse through in the normal way we're accustomed to. We won't need a zipper data structure, because the continuation-based representation of our result list will take over the same role. + +So our new function `tc` (for task with continuations) takes an input list (not a zipper) and a also takes a continuation `k` (it's conventional to use `k` for continuation variables). `k` is a function that represents how the result list is going to continue being built up after this invocation of `tc` delivers up a value. When we invoke `tc` for the first time, we expect it to deliver as a value the very de-S'd list we're seeking, so the way for the list to continue being built up is for nothing to happen to it. That is, our initial invocation of `tc` will supply `fun tail -> tail` as the value for `k`. Here is the whole `tc` function. Its structure and behavior follows `tz` from above, which we've repeated here to facilitate detailed comparison: let rec tz (z : char list_zipper) = match z with @@ -178,10 +173,9 @@ 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). -We have not named the functional argument `unzipped`, although that is +We have not named the continuation 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 +`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 @@ -190,14 +184,13 @@ 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 call `tc ['a'; 'b'; 'S'; 'd']` would yield a partially-applied function; it would still wait for another argument, a continuation of type `char list -> char list`. So we have to give it an "initial continuation" to get started. As mentioned above, we supply *the identity function* as the initial continuation. Why did we choose that? Again, if +you have already constructed the result list `"ababd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"ababd"`? 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 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: +`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);; @@ -223,7 +216,7 @@ 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. +because the List monad has an intimate connection with continuations. We'll explore this next.