(no commit message)

[lambda.git] / from_list_zippers_to_continuations.mdwn

diff --git a/from_list_zippers_to_continuations.mdwn b/from_list_zippers_to_continuations.mdwn
index 8b1fa68..dcd11ce 100644 (file)
--- 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.
 
 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
 
 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.
 
 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)  
 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)
 >      -----------------------------------------  
 >      (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
 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
 
        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).
 
 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
 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
 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)`.
 
 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
 
 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);;
 
 
     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
 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.
 
 
 We'll explore this next.