Signed-off-by: Jim Pryor <profjim@jimpryor.net>
to get there, we'll first do the exact same thing we just did with
concrete zipper using procedures instead.
to get there, we'll first do the exact same thing we just did with
concrete zipper using procedures instead.
-Think of a list as a procedural recipe: `['a'; 'b'; 'S'; 'd']` is the result of
-the computation `'a'::('b'::('S'::('d'::[])))` (or, in our old style,
-`make_list 'a' (make_list 'b' (make_list 'S' (make_list 'd' empty)))`). The
+Think of a list as a procedural recipe: `['a'; 'b'; 'c'; 'd']` is the result of
+the computation `'a'::('b'::('c'::('d'::[])))` (or, in our old style,
+`make_list 'a' (make_list 'b' (make_list 'c' (make_list 'd' empty)))`). The
recipe for constructing the list goes like this:
> (0) Start with the empty list []
> (1) make a new list whose first element is 'd' and whose tail is the list constructed in step (0)
recipe for constructing the list goes like this:
> (0) Start with the empty list []
> (1) make a new list whose first element is 'd' and whose tail is the list constructed in step (0)
-> (2) make a new list whose first element is 'S' and whose tail is the list constructed in step (1)
+> (2) make a new list whose first element is 'c' and whose tail is the list constructed in step (1)
> -----------------------------------------
> (3) make a new list whose first element is 'b' and whose tail is the list constructed in step (2)
> (4) make a new list whose first element is 'a' and whose tail is the list constructed in step (3)
> -----------------------------------------
> (3) make a new list whose first element is 'b' and whose tail is the list constructed in step (2)
> (4) make a new list whose first element is 'a' and whose tail is the list constructed in step (3)
context, a continuation is a function of type `char list -> char
list`. For instance, the continuation corresponding to the portion of
the recipe below the horizontal line is the function `fun (tail : char
context, a continuation is a function of type `char list -> char
list`. For instance, the continuation corresponding to the portion of
the recipe below the horizontal line is the function `fun (tail : char
-list) -> 'a'::('b'::tail)`.
+list) -> 'a'::('b'::tail)`. What is the continuation of the 4th step? That is, after we've built up `'a'::('b'::('c'::('d'::[])))`, what more has to happen to that for it to become the list `['a'; 'b'; 'c'; 'd']`? Nothing! Its continuation is the function that does nothing: `fun tail -> tail`.
-This means that we can now represent the unzipped part of our
-zipper as a continuation: a function
-describing how to finish building a list. We'll write a new
-function, `tc` (for task with continuations), that will take an input
-list (not a zipper!) and a continuation `k` (it's conventional to use `k` for continuation variables) and return a processed list.
-The structure and the behavior will follow that of `tz` above, with
-some small but interesting differences. We've included the orginal
-`tz` to facilitate detailed comparison:
+In what follows, we'll be thinking about the result list that we're building up in this procedural way. We'll treat our input list just as a plain old static list data structure, that we recurse through in the normal way we're accustomed to. We won't need a zipper data structure, because the continuation-based representation of our result list will take over the same role.
+
+So our new function `tc` (for task with continuations) takes an input list (not a zipper) and a also takes a continuation `k` (it's conventional to use `k` for continuation variables). `k` is a function that represents how the result list is going to continue being built up after this invocation of `tc` delivers up a value. When we invoke `tc` for the first time, we expect it to deliver as a value the very de-S'd list we're seeking, so the way for the list to continue being built up is for nothing to happen to it. That is, our initial invocation of `tc` will supply `fun tail -> tail` as the value for `k`. Here is the whole `tc` function. Its structure and behavior follows `tz` from above, which we've repeated here to facilitate detailed comparison:
let rec tz (z : char list_zipper) =
match z with
let rec tz (z : char list_zipper) =
match z with
the first `match` clause will fire, so the the variable `zipped` will
not be instantiated).
the first `match` clause will fire, so the the variable `zipped` will
not be instantiated).
-We have not named the functional argument `unzipped`, although that is
+We have not named the continuation argument `unzipped`, although that is
what the parallel would suggest. The reason is that `unzipped` (in
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
+`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
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
In the `tc` version of the task, we simply compose `k` with itself:
`k o k = fun tail -> k (k tail)`.
In the `tc` version of the task, we simply compose `k` with itself:
`k o k = fun tail -> k (k 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']` would yield a partially-applied function; it would still wait for another argument, a continuation of type `char list -> char list`. So we have to give it an "initial continuation" to get started. As mentioned above, we supply *the identity function* as the initial continuation. Why did we choose that? Again, if
+you have already constructed the result list `"ababd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"ababd"`? Clearly, the identity function.
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 applied to the argument `"Sd"`. Two choices: is it
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 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:
+`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);;
tc ['S'; 'd'] (fun tail -> 'a'::'b'::tail);;