schemeracketcontinuationscallcc

how to analyze the equivalent receiver in call/cc?


I am reading the book Scheme and the Art of Programming, but cannot think of an answer to the following question:

If r is

(escaper (lambda (continuation) (continuation body))

in (... (call/cc r) ...), when can r be rewritten as

(lambda (continuation) body)

Solution

  • The answer is: always.

    escaper is not part of Scheme. It is defined by that book, Scheme and the Art of Programming, thus:

    " escaper turns its argument procedure into similarly defined 'escape' procedure (a.k.a. 'continuation'), which, when invoked, its result becomes the result of the entire computation. Anything awaiting the result [of that escape procedure's invocation] is ignored." (slightly copy-edited)

    The result of (continuation body) in the " escaper-ed" version of (lambda (c..n) (c..n body)) would be returned directly into the top level, except, continuation does not return. It jumps into its destination context (1), i.e. that which awaits the result of the (call/cc r) call, because this continuation is set up by that call to call/cc:

               ;; (0)   -- top level
                 (... 
                      ;; (1)  <-----------------------------------\
                        (call/cc r)  ;; r = (escaper (lambda (continuation)
                                     ;;                 (continuation body)))
                             ...)
    ===
               ;; (0)   -- top level
                 (... 
                      ;; (1)  
                        (continuation--0                       ;; set up by `escaper`
                          ((lambda (continuation)
                                (continuation body))
                            continuation--1))                   ;; set up by call/cc
                             ...)
    ===
               ;; (0)   -- top level
                 (... 
                      ;; (1)  
                        (continuation--0
                           (let ((continuation continuation--1))   ;; by application of `lambda`
                             (continuation body)))
                             ...)
    

    So if body returns, that result is passed into (1) by continuation--1; and if body calls continuation with a value, that value is passed into (1) by continuation--1. Nothing is returned to continuation--0, so its jump is never triggered.

    And in

               ;; (0)
                 (... 
                      ;; (1)
                        (call/cc (lambda (continuation) body))
                             ...)
    ===
               ;; (0)
                 (... 
                      ;; (1)
                        (let ((continuation continuation--1)) 
                           body)
                             ...)
    

    exactly the same thing happens: if body returns, that result is simply returned into (1); and if body calls continuation with a value, that value is passed into (1) by continuation--1.