author Jim Pryor Wed, 1 Dec 2010 06:01:41 +0000 (01:01 -0500) committer Jim Pryor Wed, 1 Dec 2010 06:01:41 +0000 (01:01 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>

@@ -158,13 +158,13 @@ some small but interesting differences.  We've included the orginal
let rec tc (l: char list) (c: (char list) -> (char list)) =
match l with
| [] -> List.rev (c [])
-           | 'S'::zipped -> tc zipped (fun x -> c (c x))
-           | target::zipped -> tc zipped (fun x -> target::(c x));;
+           | 'S'::zipped -> tc zipped (fun tail -> c (c tail))
+           | target::zipped -> tc zipped (fun tail -> target::(c tail));;

-       # tc ['a'; 'b'; 'S'; 'd'] (fun x -> x);;
+       # tc ['a'; 'b'; 'S'; 'd'] (fun tail -> tail);;
- : char list = ['a'; 'b'; 'a'; 'b']

-       # tc ['a'; 'S'; 'b'; 'S'] (fun x -> x);;
+       # 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
@@ -184,7 +184,7 @@ 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 x -> c (c x)`.
+`c o c = fun tail -> c (c 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.
@@ -192,25 +192,24 @@ 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 `c` must be at the point in the computation when
`tc` is called with the first argument `"Sd"`.  Two choices: is it
-`fun x -> a::b::x`, or it is `fun x -> b::a::x`?  The way to see if
+`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 x -> 'a'::'b'::x);;
+    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
simplified picture of a computation using continuations, where `'S'`
-plays the role of a control operator with some similarities to what is
-often called `shift`.  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.) 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
always right-branching, i.e., the computation `((f1 f2) f3) x` cannot
be directly represented.

-One possibile development is that we could add a special symbol `'#'`,
+One way to extend this exercise would be to add a special symbol `'#'`,
and then the task would be to copy from the target `'S'` only back to
-the closest `'#'`.  This would allow the task to simulate delimited
+the closest `'#'`.  This would allow our task to simulate delimited
continuations with embedded prompts.

The reason the task is well-suited to the list zipper is in part