From: Jim Pryor Date: Wed, 1 Dec 2010 06:01:41 +0000 (-0500) Subject: lists-to-contin tweaks X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=abe3498df36846ee2b95a33bc63f9bbe4b69d9b3;hp=ae36642e2abca2e552e48cfaca3265de603c35bb lists-to-contin tweaks Signed-off-by: Jim Pryor --- diff --git a/from_lists_to_continuations.mdwn b/from_lists_to_continuations.mdwn index 7873a2cd..1d0ad42b 100644 --- a/from_lists_to_continuations.mdwn +++ b/from_lists_to_continuations.mdwn @@ -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