updates

diff --git a/topics/_coroutines_and_aborts.mdwn b/topics/_coroutines_and_aborts.mdwn
index ce525b3..d7c8b03 100644 (file)
--- a/topics/_coroutines_and_aborts.mdwn
+++ b/topics/_coroutines_and_aborts.mdwn
@@ -1,7 +1,8 @@
 [[!toc]]
 
 [[!toc]]
 

+Recall [[the recent homework assignment|/exercises/assignment12]] where you solved the same-fringe problem with a `make_fringe_enumerator` function, or in the Scheme version using streams instead of zippers, with a `lazy-flatten` 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*.
+The technique illustrated in those solutions 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:
 
 
 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:
 


@@ -33,9 +34,11 @@ If you want to read more about these kinds of threads, here are some links:
 <!-- * [[!wikipedia Green_threads]]
 *      [[!wikipedia Protothreads]] -->
 
 <!-- * [[!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.
+The way we built cooperative threads using `make_fringe_enumerator` 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 either required us to manually save and restore the thread's snapshotted state (a tree zipper); or else we had to use a mutable reference cell to save and restore that state for us. Using the saved state, the next invocation of the `next_leaf` function could start up again where the previous invocation left off.

 
 

-It's possible to build cooperative threads without using those tools, however. Some languages have a native syntax for them. Here's how we'd write the same-fringe solution above using native coroutines in the language Lua:
+It's possible to build cooperative threads without using those tools, however. Already our [[solution using streams|/exercises/assignment12#streams2]] uses neither zippers nor any mutation. Instead it saves the thread's state in explicitly-created thunks, and resumes the thread by forcing the thunk.
+
+Some languages have a native syntax for coroutines. Here's how we'd write the same-fringe solution above using native coroutines in the language Lua:

 
        > function fringe_enumerator (tree)
            if tree.leaf then
 
        > function fringe_enumerator (tree)
            if tree.leaf then


@@ -78,21 +81,21 @@ We're going to think about the underlying principles to this execution pattern,
 
 To get a better understanding of how that execution pattern works, we'll add yet a second execution pattern to our plate, and then think about what they have in common.
 
 
 To get a better understanding of how that execution pattern works, we'll add yet a second execution pattern to our plate, and then think about what they have in common.
 

-While writing OCaml code, you've probably come across errors. In fact, you've probably come across errors of two sorts. One sort of error comes about when you've got syntax errors or type errors and the OCaml interpreter isn't even able to understand your code:
+While writing OCaml code, you've probably come across errors. In fact, you've probably come across errors of several sorts. One sort of error comes about when you've got syntax errors and the OCaml interpreter isn't even able to parse your code. A second sort of error is type errors, as in:

 
        # let lst = [1; 2] in
          "a" :: lst;;
        Error: This expression has type int list
               but an expression was expected of type string list
 
 
        # let lst = [1; 2] in
          "a" :: lst;;
        Error: This expression has type int list
               but an expression was expected of type string list
 

-But you may also have encountered other kinds of error, that arise while your program is running. For example:
+Type errors are also detected and reported before OCaml attempts to execute or evaluate your code. But you may also have encountered a third kind of error, that arises while your program is running. For example:

 
        # 1/0;;
        Exception: Division_by_zero.
        # List.nth [1;2] 10;;
        Exception: Failure "nth".
 
 
        # 1/0;;
        Exception: Division_by_zero.
        # List.nth [1;2] 10;;
        Exception: Failure "nth".
 

-These "Exceptions" are **run-time errors**. OCaml will automatically detect some of them, like when you attempt to divide by zero. Other exceptions are *raised* by code. For instance, here is the implementation of `List.nth`:
+These "Exceptions" are **run-time errors**. OCaml will automatically detect some of them, like when you attempt to divide by zero. Other exceptions are *raised* by code. For instance, here is the standard implementation of `List.nth`:

 
        let nth l n =
          if n < 0 then invalid_arg "List.nth" else
 
        let nth l n =
          if n < 0 then invalid_arg "List.nth" else


@@ -102,7 +105,7 @@ These "Exceptions" are **run-time errors**. OCaml will automatically detect some
            | a::l -> if n = 0 then a else nth_aux l (n-1)
          in nth_aux l n
 
            | a::l -> if n = 0 then a else nth_aux l (n-1)
          in nth_aux l n
 

-Notice the two clauses `invalid_arg "List.nth"` and `failwith "nth"`. These are two helper functions which are shorthand for:
+(The Juli8 version of `List.nth` only differs in sometimes raising a different error.) Notice the two clauses `invalid_arg "List.nth"` and `failwith "nth"`. These are two helper functions which are shorthand for:

 
        raise (Invalid_argument "List.nth");;
        raise (Failure "nth");;
 
        raise (Invalid_argument "List.nth");;
        raise (Failure "nth");;


@@ -128,7 +131,7 @@ I said when you evaluate the expression:
 
        raise bad
 
 
        raise bad
 

-the effect is for the program to immediately stop. That's not exactly true. You can also programmatically arrange to *catch* errors, without the program necessarily stopping. In OCaml we do that with a `try ... with PATTERN -> ...` construct, analogous to the `match ... with PATTERN -> ...` construct:
+the effect is for the program to immediately stop. That's not exactly true. You can also programmatically arrange to *catch* errors, without the program necessarily stopping. In OCaml we do that with a `try ... with PATTERN -> ...` construct, analogous to the `match ... with PATTERN -> ...` construct. (In OCaml 4.02 and higher, there is also a more inclusive construct that combines these, `match ... with PATTERN -> ... | exception PATTERN -> ...`.)

 
        # let foo x =
            try
 
        # let foo x =
            try


@@ -154,7 +157,7 @@ So what I should have said is that when you evaluate the expression:
 
 *and that exception is never caught*, then the effect is for the program to immediately stop.
 
 
 *and that exception is never caught*, then the effect is for the program to immediately stop.
 

-Trivia: what's the type of the `raise (Failure "two")` in:
+**Trivia**: what's the type of the `raise (Failure "two")` in:

 
        if x = 1 then 10
        else raise (Failure "two")
 
        if x = 1 then 10
        else raise (Failure "two")


@@ -172,7 +175,9 @@ How about this:
 
        (fun x -> raise (Failure "two") : 'a -> 'a)
 
 
        (fun x -> raise (Failure "two") : 'a -> 'a)
 

-Remind you of anything we discussed earlier? /Trivia.
+Remind you of anything we discussed earlier? (At one point earlier in term we were asking whether you could come up with any functions of type `'a -> 'a` other than the identity function.)
+
+**/Trivia.**

 
 Of course, it's possible to handle errors in other ways too. There's no reason why the implementation of `List.nth` *had* to raise an exception. They might instead have returned `Some a` when the list had an nth member `a`, and `None` when it does not. But it's pedagogically useful for us to think about the exception-raising pattern now.
 
 
 Of course, it's possible to handle errors in other ways too. There's no reason why the implementation of `List.nth` *had* to raise an exception. They might instead have returned `Some a` when the list had an nth member `a`, and `None` when it does not. But it's pedagogically useful for us to think about the exception-raising pattern now.
 


@@ -200,7 +205,7 @@ The matching `try ... with ...` block need not *lexically surround* the site whe
 
 Here we call `foo bar 0`, and `foo` in turn calls `bar 0`, and `bar` raises the exception. Since there's no matching `try ... with ...` block in `bar`, we percolate back up the history of who called that function, and we find a matching `try ... with ...` block in `foo`. This catches the error and so then the `try ... with ...` block in `foo` (the code that called `bar` in the first place) will evaluate to `20`.
 
 
 Here we call `foo bar 0`, and `foo` in turn calls `bar 0`, and `bar` raises the exception. Since there's no matching `try ... with ...` block in `bar`, we percolate back up the history of who called that function, and we find a matching `try ... with ...` block in `foo`. This catches the error and so then the `try ... with ...` block in `foo` (the code that called `bar` in the first place) will evaluate to `20`.
 

-OK, now this exception-handling apparatus does exemplify the second execution pattern we want to focus on. But it may bring it into clearer focus if we simplify the pattern even more. Imagine we could write code like this instead:
+OK, now this exception-handling apparatus does exemplify the second execution pattern we want to focus on. But it may bring it into clearer focus if we **simplify the pattern** even more. Imagine we could write code like this instead:

 
        # let foo x =
            try begin
 
        # let foo x =
            try begin


@@ -221,8 +226,8 @@ Many programming languages have this simplified exceution pattern, either instea
            else
                return 20         -- abort early
            end
            else
                return 20         -- abort early
            end

-           return value + 100    -- in Lua, a function's normal value
-                                 -- must always also be explicitly returned
+           return value + 100    -- in a language like Scheme, you could omit the `return` here
+                                  -- but in Lua, a function's normal result must always be explicitly `return`ed

        end
        
        > return foo(1)
        end
        
        > return foo(1)


@@ -235,7 +240,7 @@ Okay, so that's our second execution pattern.
 
 ##What do these have in common?##
 
 
 ##What do these have in common?##
 

-In both of these patterns, we need to have some way to take a snapshot of where we are in the evaluation of a complex piece of code, so that we might later resume execution at that point. In the coroutine example, the two threads need to have a snapshot of where they were in the enumeration of their tree's leaves. In the abort example, we need to have a snapshot of where to pick up again if some embedded piece of code aborts. Sometimes we might distill that snapshot into a data structure like a zipper. But we might not always know how to do so; and learning how to think about these snapshots without the help of zippers will help us see patterns and similarities we might otherwise miss.
+In both of these patterns --- coroutines and exceptions/aborts --- we need to have some way to take a snapshot of where we are in the evaluation of a complex piece of code, so that we might later resume execution at that point. In the coroutine example, the two threads need to have a snapshot of where they were in the enumeration of their tree's leaves. In the abort example, we need to have a snapshot of where to pick up again if some embedded piece of code aborts. Sometimes we might distill that snapshot into a data structure like a zipper. But we might not always know how to do so; and learning how to think about these snapshots without the help of zippers will help us see patterns and similarities we might otherwise miss.

 
 A more general way to think about these snapshots is to think of the code we're taking a snapshot of as a *function.* For example, in this code:
 
 
 A more general way to think about these snapshots is to think of the code we're taking a snapshot of as a *function.* For example, in this code:
 


@@ -273,6 +278,11 @@ What would a "snapshot of the code outside the box" look like? Well, let's rearr
 
 and we can think of the code starting with `let foo_result = ...` as a function, with the box being its parameter, like this:
 
 
 and we can think of the code starting with `let foo_result = ...` as a function, with the box being its parameter, like this:
 

+    let foo_result = < >
+    in foo_result + 100
+
+or, spelling out the gap `< >` as a bound variable:
+

        fun box ->
            let foo_result = box
            in (foo_result) + 1000
        fun box ->
            let foo_result = box
            in (foo_result) + 1000


@@ -379,8 +389,7 @@ You can think of them as functions that represent "how the rest of the computati
 
 The key idea behind working with continuations is that we're *inverting control*. In the fragment above, the code `(if x = 1 then ... else snapshot 20) + 100`---which is written as if it were to supply a value to the outside context that we snapshotted---itself *makes non-trivial use of* that snapshot. So it has to be able to refer to that snapshot; the snapshot has to somehow be available to our inside-the-box code as an *argument* or bound variable. That is: the code that is *written* like it's supplying an argument to the outside context is instead *getting that context as its own argument*. He who is written as value-supplying slave is instead become the outer context's master.
 
 
 The key idea behind working with continuations is that we're *inverting control*. In the fragment above, the code `(if x = 1 then ... else snapshot 20) + 100`---which is written as if it were to supply a value to the outside context that we snapshotted---itself *makes non-trivial use of* that snapshot. So it has to be able to refer to that snapshot; the snapshot has to somehow be available to our inside-the-box code as an *argument* or bound variable. That is: the code that is *written* like it's supplying an argument to the outside context is instead *getting that context as its own argument*. He who is written as value-supplying slave is instead become the outer context's master.
 

-In fact you've already seen this several times this semester---recall how in our implementation of pairs in the untyped lambda-calculus, the handler who wanted to use the pair's components had *in the first place to be supplied to the pair as an argument*. So the exotica from the end of the seminar was already on the scene in some of our earliest steps. Recall also what we did with v2 and v5 lists. Version 5 lists were the ones that let us abort a fold early: 
-go back and re-read the material on "Aborting a Search Through a List" in [[Week4]].
+In fact you've already seen this several times this semester---recall how in our implementation of pairs in the untyped lambda-calculus, the handler who wanted to use the pair's components had *in the first place to be supplied to the pair as an argument*. So the exotica from the end of the seminar was already on the scene in some of our earliest steps. Recall also what we did with our [[abortable list traversals|/topics/week12_abortable_traversals]].

 
 This inversion of control should also remind you of Montague's treatment of determiner phrases in ["The Proper Treatment of Quantification in Ordinary English"](http://www.blackwellpublishing.com/content/BPL_Images/Content_store/Sample_chapter/0631215417%5CPortner.pdf) (PTQ).
 
 
 This inversion of control should also remind you of Montague's treatment of determiner phrases in ["The Proper Treatment of Quantification in Ordinary English"](http://www.blackwellpublishing.com/content/BPL_Images/Content_store/Sample_chapter/0631215417%5CPortner.pdf) (PTQ).