tweak advanced
[lambda.git] / miscellaneous_lambda_challenges_and_advanced_topics.mdwn
index 0342fc6..511135a 100644 (file)
@@ -378,19 +378,19 @@ can use.
 
                ; and so on             
                
-       Remarks: the `larger_computation_handler` should be supplied as both the
+       Remarks: the `larger_computation` handler should be supplied as both the
        `continue_leftwards_handler` and the `abort_handler` for the leftmost
-       application, where the head `5` is supplied to `f`. Because the result of this
+       application, where the head `5` is supplied to `f`; because the result of this
        application should be passed to the larger computation, whether it's a "fall
        off the left end of the list" result or it's a "I'm finished, possibly early"
-       result. The `larger_computation_handler` also then gets passed to the next
+       result. The `larger_computation` handler also then gets passed to the next
        rightmost stage, where the head `4` is supplied to `f`, 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 `f` to `4` etc given as
        an argument to the application of `f` to `5` etc. Instead, we pass
 
-               (\result_of_fold_over_4321. f 5 result_of_fold_over_4321 one_handler another_handler)
+               (\result_of_fold_over_4321. f 5 result_of_fold_over_4321 <one_handler> <another_handler>)
 
        *to* the application of `f` to `4` as its "continue" handler. The application of `f`
        to `4` can decide whether this handler, or the other, "abort" handler, should be
@@ -402,8 +402,8 @@ can use.
        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. At this stage, we don't have any way to prevent that. Later,
-       we'll see ways to semantically guarantee one evaluation order rather than
+       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
@@ -433,9 +433,6 @@ can use.
                                ; here's the abort_handler
                                larger_computation  in
                let extract_tail = ; left as exercise
-                       ;; for real efficiency, it'd be nice to fuse the apparatus developed
-                       ;; in these v5 lists with the ideas from the v4 lists, above
-                       ;; but that also is left as an exercise
 
        These functions are used like this:
 
@@ -449,12 +446,51 @@ can use.
        your reach. And once you have followed it, you'll be well on your way to
        appreciating the full terrible power of continuations.
 
-<!-- (Silly [cultural reference](http://www.newgrounds.com/portal/view/33440).) -->
+       <!-- (Silly [cultural reference](http://www.newgrounds.com/portal/view/33440).) -->
 
        Of course, like everything elegant and exciting in this seminar, [Oleg
        discusses it in much more
        detail](http://okmij.org/ftp/Streams.html#enumerator-stream).
 
+       *Comments*:
+
+       1.      The technique deployed here, and in the v2 lists, and in our implementations
+               of pairs and booleans, is known as **continuation-passing style** programming.
+
+       2.      We're still building the list as a right fold, so in a sense the
+               application of `f` to the leftmost element `5` is "outermost". However,
+               this "outermost" application is getting lifted, and passed as a *handler*
+               to the next right application. Which is in turn getting lifted, and
+               passed to its next right application, and so on. So if you
+               trace the evaluation of the `extract_head` function to the list `[5;4;3;2;1]`,
+               you'll see `1` gets passed as a "this is the head sofar" answer to its
+               `continue_handler`; then that answer is discarded and `2` is
+               passed as a "this is the head sofar" answer to *its* `continue_handler`,
+               and so on. All those steps have to be evaluated to finally get the result
+               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:
+       
+                       let make_list = \h t. \f z continue_handler abort_handler.
+                               f h z (\z. t f z continue_handler abort_handler) abort_handler
+
+               now `extract_head` can return the leftmost head directly, using its `abort_handler`:
+
+                       let extract_head = \lst larger_computation. lst
+                                       ; here's our f
+                                       (\hd sofar continue_handler abort_handler. abort_handler hd)
+                                       ; here's our z
+                                       junk
+                                       ; here's the continue_handler for the leftmost application of f
+                                       larger_computation
+                                       ; here's the abort_handler
+                                       larger_computation  in
+
+       3.      To extract tails efficiently, too, it'd be nice to fuse the apparatus developed
+               in these v5 lists with the ideas from the v4 lists, above.
+               But that also is left as an exercise.
 
 
 5.     Implementing (self-balancing) trees