[[!toc]]
-Recall back in [[Assignment4]], we asked you to enumerate the "fringe" of a leaf-labeled tree. Both of these trees:
-
- . .
- / \ / \
- . 3 1 .
- / \ / \
- 1 2 2 3
-
-have the same fringe: `[1;2;3]`. We also asked you to write a function that determined when two trees have the same fringe. The way you approached that back then was to enumerate each tree's fringe, and then compare the two lists for equality. Today, and then again in a later class, we'll encounter two new ways to approach the problem of determining when two trees have the same fringe.
-
##List Zippers##
Say you've got some moderately-complex function for searching through a list, for example:
/ | \
leaf 1 leaf 2 leaf 3
-We'll call this new untargetted tree `node 20`. The result of moving upward from our previous targetter tree, targetted on `leaf 1`, would be the outermost `parent` element of that targetted tree, with `node 20` being the subtree that fills that parent's target position `*`:
+We'll call this new untargetted tree `node 20`. The result of moving upward from our previous targetted tree, targetted on `leaf 1`, would be the outermost `parent` element of that targetted tree, with `node 20` being the subtree that fills that parent's target position `*`:
{
parent = ...;
##Same-fringe using a tree zipper##
+Recall back in [[Assignment4]], we asked you to enumerate the "fringe" of a leaf-labeled tree. Both of these trees:
+
+ . .
+ / \ / \
+ . 3 1 .
+ / \ / \
+ 1 2 2 3
+
+have the same fringe: `[1;2;3]`. We also asked you to write a function that determined when two trees have the same fringe. The way you approached that back then was to enumerate each tree's fringe, and then compare the two lists for equality. Today, and then again in a later class, we'll encounter two new ways to approach the problem of determining when two trees have the same fringe.
+
+
Supposing you did work out an implementation of the tree zipper, then one way to determine whether two trees have the same fringe would be: go downwards (and leftwards) in each tree as far as possible. Compare the targetted leaves. If they're different, stop because the trees have different fringes. If they're the same, then for each tree, move rightward if possible; if it's not (because you're at the rightmost position in a sibling list), more upwards then try again to move rightwards. Repeat until you are able to move rightwards. Once you do move rightwards, go downwards (and leftwards) as far as possible. Then you'll be targetted on the next leaf in the tree's fringe. The operations it takes to get to "the next leaf" may be different for the two trees. For example, in these trees:
. .
you won't move upwards at the same steps. Keep comparing "the next leafs" until they are different, or you exhaust the leafs of only one of the trees (then again the trees have different fringes), or you exhaust the leafs of both trees at the same time, without having found leafs with different labels. In this last case, the trees have the same fringe.
-If your trees are very big---say, millions of leaves---you can imagine how this would be quicker and more memory-efficient than traversing each tree to construct a list of its fringe, and then comparing the two lists so built to see if they're equal. For one thing, the zipper method can abort early if the fringes diverge early, without needing to traverse or built a list containing the rest of each tree's fringe.
+If your trees are very big---say, millions of leaves---you can imagine how this would be quicker and more memory-efficient than traversing each tree to construct a list of its fringe, and then comparing the two lists so built to see if they're equal. For one thing, the zipper method can abort early if the fringes diverge early, without needing to traverse or build a list containing the rest of each tree's fringe.
Let's sketch the implementation of this. We won't provide all the details for an implementation of the tree zipper, but we will sketch an interface for it.
# type blah_record = { height : int; weight : int; char_tester : char -> bool };;
# let b2 = { height = 1; weight = 2; char_tester = fun c -> c = 'M' };;
val b2 : blah_record = {height = 1; weight = 2; char_tester = <fun>}
+ # let b3 = { height = 1; char_tester = (fun c -> c = 'K'); weight = 3 };; (* also works *)
+ val b3 : blah_record = {height = 1; weight = 3; char_tester = <fun>}
These were the strategies to extract the components of an unlabeled tuple:
The auxiliary `loop` function will keep calling itself recursively until a difference in the fringes has manifested itself---either because one fringe is exhausted before the other, or because the next leaves in the two fringes have different labels. If we get to the end of both fringes at the same time (`next1 (), next2 ()` matches the pattern `None, None`) then we've established that the trees do have the same fringe.
-The technique illustrated here with our fringe enumerators is a powerful and important one. It's an example of what's sometimes called **cooperative threading**. A "thread" is a subprogram that the main computation spawns off. Threads are called "cooperative" when the code of the main computation and the thread fixes when control passes back and forth between them. (When the code doesn't control this---for example, it's determined by the operating system or the hardware in ways that the programmer can't predict---that's called "preemptive threading.") With cooperative threads, one typically yields control to the thread, and then back again to the main program, multiple times. Here's the pattern in which that happens in our `same_fringe` function:
+The technique illustrated here with our fringe enumerators is a powerful and important one. It's an example of what's sometimes called **cooperative threading**. A "thread" is a subprogram that the main computation spawns off. Threads are called "cooperative" when the code of the main computation and the thread fixes when control passes back and forth between them. (When the code doesn't control this---for example, it's determined by the operating system or the hardware in ways that the programmer can't predict---that's called "preemptive threading.") Cooperative threads are also sometimes called *coroutines* or *generators*.
+
+With cooperative threads, one typically yields control to the thread, and then back again to the main program, multiple times. Here's the pattern in which that happens in our `same_fringe` function:
main program next1 thread next2 thread
------------ ------------ ------------
(paused) <-- return it (paused)
... and so on ...
+If you want to read more about these kinds of threads, here are some links:
+
+<!-- * [[!wikipedia Computer_multitasking]]
+* [[!wikipedia Thread_(computer_science)]] -->
+* [[!wikipedia Coroutine]]
+* [[!wikipedia Iterator]]
+* [[!wikipedia Generator_(computer_science)]]
+* [[!wikipedia Fiber_(computer_science)]]
+<!-- * [[!wikipedia Green_threads]]
+* [[!wikipedia Protothreads]] -->
+
The way we built cooperative threads here crucially relied on two heavyweight tools. First, it relied on our having a data structure (the tree zipper) capable of being a static snapshot of where we left off in the tree whose fringe we're enumerating. Second, it relied on our using mutable reference cells so that we could update what the current snapshot (that is, tree zipper) was, so that the next invocation of the `next_leaf` function could start up again where the previous invocation left off.
In coming weeks, we'll learn about a different way to create threads, that relies on **continuations** rather than on those two tools. All of these tools are inter-related. As Oleg says, "Zipper can be viewed as a delimited continuation reified as a data structure." These different tools are also inter-related with monads. Many of these tools can be used to define the others. We'll explore some of the connections between them in the remaining weeks, but we encourage you to explore more.
+##Introducing Continuations##
+
+A continuation is "the rest of the program." Or better: an **delimited continuation** is "the rest of the program, up to a certain boundary." An **undelimited continuation** is "the rest of the program, period."
+
+Even if you haven't read specifically about this notion (for example, even if you haven't read Chris and Ken's work on using continuations in natural language semantics), you'll have brushed shoulders with it already several times in this course.
+
+A naive semantics for atomic sentences will say the subject term is of type `e`, and the predicate of type `e -> t`, and that the subject provides an argument to the function expressed by the predicate.
+
+Monatague proposed we instead take subject terms to be of type `(e -> t) -> t`, and that now it'd be the predicate (still of type `e -> t`) that provides an argument to the function expressed by the subject.
+
+If all the subject did then was supply an `e` to the `e -> t` it receives as an argument, we wouldn't have gained anything we weren't already able to do. But of course, there are other things the subject can do with the `e -> t` it receives as an argument. For instance, it can check whether anything in the domain satisfies that `e -> t`; or whether most things do; and so on.
+
+This inversion of who is the argument and who is the function receiving the argument is paradigmatic of working with continuations. We did the same thing ourselves back in the early days of the seminar, for example in our implementation of pairs. In the untyped lambda calculus, we identified the pair `(x, y)` with a function:
+
+ \handler. handler x y
+
+A pair-handling function would accept the two elements of a pair as arguments, and then do something with one or both of them. The important point here is that the handler was supplied as an argument to the pair. Eventually, the handler would itself be supplied with arguments. But only after it was supplied as an argument to the pair. This inverts the order you'd expect about what is the data or argument, and what is the function that operates on it.
+
+Consider a complex computation, such as:
+
+ 1 + 2 * (1 - g (3 + 4))
+
+Part of this computation---`3 + 4`---leads up to supplying `g` with an argument. The rest of the computation---`1 + 2 * (1 - ___)`---waits for the result of applying `g` to that argument and will go on to do something with it (inserting the result into the `___` slot). That "rest of the computation" can be regarded as a function:
+
+ \result. 1 + 2 * (1 - result)
+
+This function will be applied to whatever is the result of `g (3 + 4)`. So this function can be called the *continuation* of that application of `g`. For some purposes, it's useful to be able to invert the function/argument order here, and rather than supplying the result of applying `g` to the continuation, we instead supply the continuation to `g`. Well, not to `g` itself, since `g` only wants a single `int` argument. But we might build some `g`-like function which accepts not just an `int` argument like `g` does, but also a continuation argument.
+
+Go back and read the material on "Aborting a Search Through a List" in [[Week4]] for an example of doing this.
+
+In very general terms, the strategy is to work with functions like this:
+
+ let g' k (i : int) =
+ ... do stuff ...
+ ... if you want to abort early, supply an argument to k ...
+ ... do more stuff ...
+ ... normal result
+ in let gcon = fun result -> 1 + 2 * (1 - result)
+ in gcon (g' gcon (3 + 4))
+
+It's a convention to use variables like `k` for continuation arguments. If the function `g'` never supplies an argument to its contination argument `k`, but instead just finishes evaluating to a normal result, that normal result will be delivered to `g'`'s continuation `gcon`, just as happens when we don't pass around any explicit continuation variables.
+
+The above snippet of OCaml code doesn't really capture what happens when we pass explicit continuation variables. For suppose that inside `g'`, we do supply an argument to `k`. That would go into the `result` parameter in `gcon`. But then what happens once we've finished evaluating the application of `gcon` to that `result`? In the OCaml snippet above, the final value would then bubble up through the context in the body of `g'` where `k` was applied, and eventually out to the final line of the snippet, where it once again supplied an argument to `gcon`. That's not what happens with a real continuation. A real continuation works more like this:
+
+ let g' k (i : int) =
+ ... do stuff ...
+ ... if you want to abort early, supply an argument to k ...
+ ... do more stuff ...
+ ... normal result
+ in let gcon = fun result ->
+ let final_value = 1 + 2 * (1 - result)
+ in end_program_with final_value
+ in gcon (g' gcon (3 + 4))
+
+So once we've finished evaluating the application of `gcon` to a `result`, the program is finished. (This is how undelimited continuations behave. We'll discuss delimited continuations later.)
+
+So now, guess what would be the result of doing the following:
+
+ let g' k (i : int) =
+ 1 + k i
+ in let gcon = fun result ->
+ let final_value = (1, result)
+ in end_program_with final_value
+ in gcon (g' gcon (3 + 4))
+
+<!-- (1, 7) ... explain why not (1, 8) -->
+
+