X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=cps_and_continuation_operators.mdwn;h=72b0034235e0c2be0e891c350ed168dee3b6360f;hp=fadd34d316d57471331419cdc49d76e36088f6e4;hb=399197e0af7c4b80f326be60ff2c0caae74b3687;hpb=8f043cd83b65c90928ab884d52be168b93d23a6c;ds=sidebyside diff --git a/cps_and_continuation_operators.mdwn b/cps_and_continuation_operators.mdwn index fadd34d3..72b00342 100644 --- a/cps_and_continuation_operators.mdwn +++ b/cps_and_continuation_operators.mdwn @@ -357,10 +357,10 @@ Here is the hardest example. Try to figure out what this function does: ; is this the only case where walk returns a non-atom? [(null? l) '()] [(atom? (car l)) (begin - (let/cc k2 + (let/cc k2 (begin (set! resume k2) ; now what will happen when resume is called? ; when the next line is executed, what will yield be bound to? - (yield (car l))) + (yield (car l)))) ; when will the next line be executed? (walk (cdr l)))] [else (begin @@ -368,10 +368,10 @@ Here is the hardest example. Try to figure out what this function does: (walk (car l)) (walk (cdr l)))]))] [next (lambda () ; next is a thunk - (let/cc k3 + (let/cc k3 (begin (set! yield k3) ; now what will happen when yield is called? ; when the next line is executed, what will resume be bound to? - (resume 'blah)))] + (resume 'blah))))] [check (lambda (prev) (let ([n (next)]) (cond @@ -380,11 +380,11 @@ Here is the hardest example. Try to figure out what this function does: ; when will n fail to be an atom? [else #f])))]) (lambda (lst) - (let ([fst (let/cc k1 + (let ([fst (let/cc k1 (begin (set! yield k1) ; now what will happen when yield is called? (walk lst) ; when will the next line be executed? - (yield '()))]) + (yield '())))]) (cond [(atom? fst) (check fst)] ; when will fst fail to be an atom? @@ -397,11 +397,13 @@ Here is [the answer](/hints/cps_hint_4), but again, first try to figure it out f Delimited control operators =========================== -Here again is the CPS for `callcc`: +Here again is the CPS transform for `callcc`: [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v) -`callcc` is what's known as an *undelimited control operator*. That is, the continuations `outk` that get bound into our `k`s include all the code from the `call/cc ...` out to *and including* the end of the program. Calling such a continuation will never return any value to the call site. (See the technique employed in the `delta` example above, with the `(begin (let/cc k2 ...) ...)`, for a work-around.) +`callcc` is what's known as an *undelimited control operator*. That is, the continuations `outk` that get bound into our `k`s include all the code from the `call/cc ...` out to *and including* the end of the program. Calling such a continuation will never return any value to the call site. + +(See the technique employed in the `delta` example above, with the `(begin (let/cc k2 ...) ...)`, for a work-around. Also. if you've got a copy of *The Seasoned Schemer*, see the comparison of let/cc vs. "collector-using" (that is, partly CPS) functions at pp. 155-164.) Often times it's more useful to use a different pattern, where we instead capture only the code from the invocation of our control operator out to a certain boundary, not including the end of the program. These are called *delimited control operators*. A variety of these have been formulated. The most well-behaved from where we're coming from is the pair `reset` and `shift`. `reset` sets the boundary, and `shift` binds the continuation from the position where it's invoked out to that boundary. @@ -493,9 +495,9 @@ You can make the lambda evaluator perform the required CPS transforms with these You use these like so: -* [reset m] is `reset M` where `M` is [m] -* [shift k M] is `shift (\k. M)` where `M` is [m] -* and [abort M] is `abort M` where `M` is [m] +* [reset body] is `reset BODY` where `BODY` is [body] +* [shift k body] is `shift (\k. BODY)` where `BODY` is [body] +* and [abort value] is `abort VALUE` where `VALUE` is [value] There are also `reset` and `shift` and `abort` operations in the Continuation monad in our OCaml [[monad library]]. You can check the code for details.