X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;f=week11.mdwn;h=b48dd5f410d314554c6fad96293592be0f855d96;hb=44bcb5340c6c85c2fbd05b28c8837f57529faf31;hp=8eae2ccd4202bf0d4f55a3cf276989a39d3c5d81;hpb=767dc2f1f56176d59b16840613d6c0b170a229f3;p=lambda.git diff --git a/week11.mdwn b/week11.mdwn index 8eae2ccd..b48dd5f4 100644 --- a/week11.mdwn +++ b/week11.mdwn @@ -648,8 +648,40 @@ Okay, so that's our second execution pattern. ##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 datastructure 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: + let foo x = + try + (if x = 1 then 10 + else abort 20) + 1 + end + in (foo 2) + 1;; + +we can imagine a box: + + let foo x = + +---------------------------+ + | try | + | (if x = 1 then 10 | + | else abort 20) + 1 | + | end | + +---------------------------+ + in (foo 2) + 1;; + +and as we're about to enter the box, we want to take a snapshot of the code *outside* the box. If we decide to abort, we'd be aborting to that snapshotted code. + + @@ -799,13 +831,15 @@ Aparently, this task, as simple as it is, is a form of computation, and the order in which the `'S'`s get evaluated can lead to divergent behavior. -For now, we'll agree to always evaluate the leftmost `'S'`. +For now, we'll agree to always evaluate the leftmost `'S'`, which +guarantees termination, and a final string without any `'S'` in it. This is a task well-suited to using a zipper. We'll define a function -`tz`, which accomplished the task by mapping a char list zipper to a -char list. We'll call the two parts of the zipper `unzipped` and -`zipped`; we start with a fully zipped list, and move elements to the -zipped part by pulling the zipped down until the zipped part is empty. +`tz` (for task with zippers), which accomplishes the task by mapping a +char list zipper to a char list. We'll call the two parts of the +zipper `unzipped` and `zipped`; we start with a fully zipped list, and +move elements to the zipped part by pulling the zipped down until the +entire list has been unzipped (and so the zipped half of the zipper is empty). 
 type 'a list_zipper = ('a list) * ('a list);;
@@ -826,13 +860,13 @@ Note that this implementation enforces the evaluate-leftmost rule.
 Task completed.
 
 One way to see exactly what is going on is to watch the zipper in
-action by tracing the execution of `t1`.  By using the `#trace`
+action by tracing the execution of `tz`.  By using the `#trace`
 directive in the Ocaml interpreter, the system will print out the
-arguments to `t1` each time it is (recurcively) called.  Note that the
+arguments to `tz` each time it is (recurcively) called.  Note that the
 lines with left-facing arrows (`<--`) show (recursive) calls to `tz`,
 giving the value of its argument (a zipper), and the lines with
 right-facing arrows (`-->`) show the output of each recursive call, a
-list.  
+simple list.  
 
 
 # #trace tz;;
@@ -869,7 +903,7 @@ The recipe for constructing the list goes like this:
 -----------------------------------------
 (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)
-
+

 
 What is the type of each of these steps?  Well, it will be a function
 from the result of the previous step (a list) to a new list: it will
@@ -885,9 +919,15 @@ describing how to finish building the list.  We'll write a new
 function, `tc` (for task with continuations), that will take an input
 list (not a zipper!) and a continuation and return a processed list.
 The structure and the behavior will follow that of `tz` above, with
-some small but interesting differences:
+some small but interesting differences.  We've included the orginal
+`tz` to facilitate detailed comparison:
 
 
+let rec tz (z:char list_zipper) = 
+    match z with (unzipped, []) -> List.rev(unzipped) (* Done! *)
+               | (unzipped, 'S'::zipped) -> tz ((List.append unzipped unzipped), zipped) 
+               | (unzipped, target::zipped) -> tz (target::unzipped, zipped);; (* Pull zipper *)
+
 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))
@@ -925,18 +965,23 @@ the recipe to produce the desired result (which is the same list,
 
 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 
+`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 you're right is to execute the following 
+command and see what happens:
+
+    tc ['S'; 'd'] (fun x -> 'a'::'b'::x);;
 
 There are a number of interesting directions we can go with this task.
 The task was chosen because the computation 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`.  &sset; &integral; In the analogy, the list
-portrays a string 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.
+often called `shift`.  In the analogy, the list portrays a string 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 `'#'`,
 and then the task would be to copy from the target `'S'` only back to