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