edits

[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 1ef5f9c..8b1fa68 100644 (file)
--- a/from_list_zippers_to_continuations.mdwn
+++ b/from_list_zippers_to_continuations.mdwn
@@ -70,7 +70,8 @@ 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
 `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);;
        
 
        type 'a list_zipper = ('a list) * ('a list);;
        


@@ -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']
 
        # 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
 
 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 (recursively) 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.
 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']);;
        # #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 <-- (['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']
        tz <-- (['d'; 'b'; 'a'; 'b'; 'a'], [])  (* Pull zipper *)
        tz --> ['a'; 'b'; 'a'; 'b'; 'd']        (* Output reversed *)
        tz --> ['a'; 'b'; 'a'; 'b'; 'd']


@@ -170,15 +172,17 @@ some small but interesting differences.  We've included the orginal
 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
 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 `zipped` will
 not be instantiated).
 
 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).
 

-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
+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,
 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,


@@ -191,16 +195,22 @@ you have already constructed the initial list `"abSd"`, what's the desired conti
 
 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
 
 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
+`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.
 `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'`
 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
 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