lists-to-contin tweaks
authorJim Pryor <profjim@jimpryor.net>
Wed, 1 Dec 2010 06:01:41 +0000 (01:01 -0500)
committerJim Pryor <profjim@jimpryor.net>
Wed, 1 Dec 2010 06:01:41 +0000 (01:01 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
from_lists_to_continuations.mdwn

index 7873a2c..1d0ad42 100644 (file)
@@ -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 [])
        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']
        
        - : 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
        - : 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:
 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.
 
 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
 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:
 
 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'`
 
 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.
 
 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
 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
 continuations with embedded prompts.
 
 The reason the task is well-suited to the list zipper is in part