ass10 tweak

[lambda.git] / week4.mdwn

diff --git a/week4.mdwn b/week4.mdwn
index f3d7c03..58d6bc3 100644 (file)
--- a/week4.mdwn
+++ b/week4.mdwn
@@ -506,10 +506,9 @@ result. The `larger_computation` handler also then gets passed to the next
 rightmost stage, where the head `4` is supplied to `f2`, as the `abort_handler` to
 use if that stage decides it has an early answer.
 
 rightmost stage, where the head `4` is supplied to `f2`, as the `abort_handler` to
 use if that stage decides it has an early answer.
 

-Finally, notice that we don't have the result of applying `f2` to `4` etc given as
-an argument to the application of `f2` to `5` etc. Instead, we pass
+Finally, notice that we're not supplying the application of `f2` to `4` etc as an argument to the application of `f2` to `5` etc---at least, not directly. Instead, we pass

 
 

-       (\result_of_foldiing_over_4321. f2 5 result_of_folding_over_4321 <one_handler> <another_handler>)
+       (\result_of_folding_over_4321. f2 5 result_of_folding_over_4321 <one_handler> <another_handler>)

 
 *to* the application of `f2` to `4` as its "continue" handler. The application of `f2`
 to `4` can decide whether this handler, or the other, "abort" handler, should be
 
 *to* the application of `f2` to `4` as its "continue" handler. The application of `f2`
 to `4` can decide whether this handler, or the other, "abort" handler, should be


@@ -521,12 +520,11 @@ but really all we're in a position to mean by that are claims about the result
 of the complex expression semantically depending only on this, not on that. A
 demon evaluator who custom-picked the evaluation order to make things maximally
 bad for you could ensure that all the semantically unnecessary computations got
 of the complex expression semantically depending only on this, not on that. A
 demon evaluator who custom-picked the evaluation order to make things maximally
 bad for you could ensure that all the semantically unnecessary computations got

-evaluated anyway. We don't have any way to prevent that. Later,
-we'll see ways to *semantically guarantee* one evaluation order rather than
-another. Though even then the demonic evaluation-order-chooser could make it
-take unnecessarily long to compute the semantically guaranteed result. Of
-course, in any real computing environment you'll know you're dealing with a
-fixed evaluation order and you'll be able to program efficiently around that.
+evaluated anyway. We don't yet know any way to prevent that. Later, we'll see
+ways to *guarantee* one evaluation order rather than another. Of
+course, in any real computing environment you'll know in advance that you're
+dealing with a fixed evaluation order and you'll be able to program efficiently
+around that.

 
 In detail, then, here's what our v5 lists will look like:
 
 
 In detail, then, here's what our v5 lists will look like:
 


@@ -590,14 +588,29 @@ detail](http://okmij.org/ftp/Streams.html#enumerator-stream).
 >      that `5` is the outer/leftmost head of the list. That's not an efficient way
 >      to get the leftmost head.
 >      
 >      that `5` is the outer/leftmost head of the list. That's not an efficient way
 >      to get the leftmost head.
 >      

->      We could improve this by building lists as left folds when implementing them
->      as continuation-passing style folds. We'd just replace above:
+>      We could improve this by building lists as **left folds**. What's that?
+>      
+>      Well, the right fold of `f` over a list `[a;b;c;d;e]`, using starting value z, is:
+>      
+>                      f a (f b (f c (f d (f e z))))
+>      
+>      The left fold on the other hand starts combining `z` with elements from the left. `f z a` is then combined with `b`, and so on:
+>      
+>                      f (f (f (f (f z a) b) c) d) e
+>      
+>      or, if we preferred the arguments to each `f` flipped:
+>      
+>                      f e (f d (f c (f b (f a z))))
+>      
+>      Recall we implemented v3 lists as their own right-fold functions. We could
+>      instead implement lists as their own left-fold functions. To do that with our
+>      v5 lists, we'd replace above:

 >      
 >                      let make_list = \h t. \f2 z continue_handler abort_handler.
 >                              f2 h z (\z. t f2 z continue_handler abort_handler) abort_handler
 >      
 >      
 >                      let make_list = \h t. \f2 z continue_handler abort_handler.
 >                              f2 h z (\z. t f2 z continue_handler abort_handler) abort_handler
 >      

->      now `extract_head` should return the leftmost head directly, using its
->      `abort_handler`:
+>      Having done that, now `extract_head` can return the leftmost head
+>      directly, using its `abort_handler`:

 >      
 >                      let extract_head = \lst larger_computation. lst
 >                                      (\hd sofar continue_handler abort_handler. abort_handler hd)
 >      
 >                      let extract_head = \lst larger_computation. lst
 >                                      (\hd sofar continue_handler abort_handler. abort_handler hd)