tweak advanced

[lambda.git] / miscellaneous_lambda_challenges_and_advanced_topics.mdwn

diff --git a/miscellaneous_lambda_challenges_and_advanced_topics.mdwn b/miscellaneous_lambda_challenges_and_advanced_topics.mdwn
index 0342fc6..ea7799c 100644 (file)
--- a/miscellaneous_lambda_challenges_and_advanced_topics.mdwn
+++ b/miscellaneous_lambda_challenges_and_advanced_topics.mdwn
@@ -378,19 +378,19 @@ can use.
 
                ; and so on             
                
 
                ; 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
        `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"
        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
 
        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
 
        *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
        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
        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
                                ; 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:
 
 
        These functions are used like this:
 


@@ -449,12 +446,47 @@ 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.
 
        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).
 
 
        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` should 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)
+                                       junk
+                                       larger_computation
+                                       larger_computation
+
+       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
 
 
 5.     Implementing (self-balancing) trees