scheme continuations for dummies

问题:

For the life of me, I can't understand continuations. I think the problem stems from the fact that I don't understand is what they are for. All the examples that I've found in books or online are very trivial. They make me wonder, why anyone would even want continuations?

Here's a typical impractical example, from TSPL, which I believe is quite recognized book on the subject. In english, they describe the continuation as "what to do" with the result of a computation. OK, that's sort of understandable.

Then, the second example given:

(call/cc
  (lambda (k)
    (* 5 (k 4)))) => 4 

How does this make any sense?? k isn't even defined! How can this code be evaluated, when (k 4) can't even be computed? Not to mention, how does call/cc know to rip out the argument 4 to the inner most expression and return it? What happens to (* 5 .. ?? If this outermost expression is discarded, why even write it?

Then, a "less" trivial example stated is how to use call/cc to provide a nonlocal exit from a recursion. That sounds like flow control directive, ie like break/return in an imperative language, and not a computation.

And what is the purpose of going through these motions? If somebody needs the result of computation, why not just store it and recall later, as needed.

回答1:

Forget about call/cc for a moment. Every expression/statement, in any programming language, has a continuation - which is, what you do with the result. In C, for example,

x = (1 + (2 * 3)); 
printf ("Done");

has the continuation of the math assignment being printf(...); the continuation of (2 * 3) is 'add 1; assign to x; printf(...)'. Conceptually the continuation is there whether or not you have access to it. Think for a moment what information you need for the continuation - the information is 1) the heap memory state (in general), 2) the stack, 3) any registers and 4) the program counter.

So continuations exist but usually they are only implicit and can't be accessed.

In Scheme, and a few other languages, you have access to the continuation. Essentially, behind your back, the compiler+runtime bundles up all the information needed for a continuation, stores it (generally in the heap) and gives you a handle to it. The handle you get is the function 'k' - if you call that function you will continue exactly after the call/cc point. Importantly, you can call that function multiple times and you will always continue after the call/cc point.

Let's look at some examples:

> (+ 2 (call/cc (lambda (cont) 3)))
5

In the above, the result of call/cc is the result of the lambda which is 3. The continuation wasn't invoked.

Now let's invoke the continuation:

> (+ 2 (call/cc (lambda (cont) (cont 10) 3)))
12

By invoking the continuation we skip anything after the invocation and continue right at the call/cc point. With (cont 10) the continuation returns 10 which is added to 2 for 12.

Now let's save the continuation.

> (define add-2 #f)
> (+ 2 (call/cc (lambda (cont) (set! add-2 cont) 3)))
5
> (add-2 10)
12
> (add-2 100)
102

By saving the continuation we can use it as we please to 'jump back to' whatever computation followed the call/cc point.

Often continuations are used for a non-local exit. Think of a function that is going to return a list unless there is some problem at which point '() will be returned.

(define (hairy-list-function list)
  (call/cc
    (lambda (cont)
       ;; process the list ...

       (when (a-problem-arises? ...)
         (cont '()))

       ;; continue processing the list ...

       value-to-return)))

回答2:

Here is text from my class notes: http://tmp.barzilay.org/cont.txt. It is based on a number of sources, and is much extended. It has motivations, basic explanations, more advanced explanations for how it's done, and a good number of examples that go from simple to advanced, and even some quick discussion of delimited continuations.

(I tried to play with putting the whole text here, but as I expected, 120k of text is not something that makes SO happy.

回答3:

TL;DR: continuations are just captured GOTOs, with values, more or less.

The exampe you ask about,

(call/cc
  (lambda (k)
    ;;;;;;;;;;;;;;;;
    (* 5 (k 4))                     ;; body of code
    ;;;;;;;;;;;;;;;;
    )) => 4 

can be approximately translated into e.g. Common Lisp, as

(prog (k retval)
    (setq k (lambda (x)             ;; capture the current continuation:
                    (setq retval x) ;;   set! the return value
                    (go EXIT)))     ;;   and jump to exit point

    (setq retval                    ;; get the value of the last expression,
      (progn                        ;;   as usual, in the
         ;;;;;;;;;;;;;;;;
         (* 5 (funcall k 4))        ;; body of code
         ;;;;;;;;;;;;;;;;
         ))
  EXIT                              ;; the goto label
    (return retval))

This is just an illustration; in Common Lisp we can't jump back into the PROG tagbody after we've exited it the first time. But in Scheme, with real continuations, we can. If we set some global variable inside the body of function called by call/cc, say (setq qq k), in Scheme we can call it at any later time, from anywhere, re-entering into the same context (e.g. (qq 42)).

The point is, the body of call/cc form may contain an if or a condexpression. It can call the continuation only in some cases, and in others return normally, evaluating all expressions in the body of code and returning the last one's value, as usual. There can be deep recursion going on there. By calling the captured continuation an immediate exit is achieved.

So we see here that k is defined. It is defined by the call/cc call. When (call/cc g) is called, it calls its argument with the current continuation: (g the-current-continuation). the current-continuation is an "escape procedure" pointing at the return point of the call/cc form. To call it means to supply a value as if it were returned by the call/cc form itself.

So the above results in

((lambda(k) (* 5 (k 4))) the-current-continuation) ==>

(* 5 (the-current-continuation 4)) ==>

; to call the-current-continuation means to return the value from
; the call/cc form, so, jump to the return point, and return the value:

4

回答4:

I won't try to explain all the places where continuations can be useful, but I hope that I can give brief examples of main place where I have found continuations useful in my own experience. Rather than speaking about Scheme's call/cc, I'd focus attention on continuation passing style. In some programming languages, variables can be dynamically scoped, and in languages without dynamically scoped, boilerplate with global variables (assuming that there are no issues of multi-threaded code, etc.) can be used. For instance, suppose there is a list of currently active logging streams, *logging-streams*, and that we want to call function in a dynamic environment where *logging-streams* is augmented with logging-stream-x. In Common Lisp we can do

(let ((*logging-streams* (cons logging-stream-x *logging-streams*)))
  (function))

If we don't have dynamically scoped variables, as in Scheme, we can still do

(let ((old-streams *logging-streams*))
  (set! *logging-streams* (cons logging-stream-x *logging-streams*)
  (let ((result (function)))
    (set! *logging-streams* old-streams)
    result))

Now lets assume that we're actually given a cons-tree whose non-nil leaves are logging-streams, all of which should be in *logging-streams* when function is called. We've got two options:

1. We can flatten the tree, collect all the logging streams, extend *logging-streams*, and then call function.
2. We can, using continuation passing style, traverse the tree, gradually extending *logging-streams*, finally calling function when there is no more tree to traverse.

Option 2 looks something like

(defparameter *logging-streams* '())

(defun extend-streams (stream-tree continuation)
  (cond
    ;; a null leaf
    ((null stream-tree)
     (funcall continuation))
    ;; a non-null leaf
    ((atom stream-tree)
     (let ((*logging-streams* (cons stream-tree *logging-streams*)))
       (funcall continuation)))
    ;; a cons cell
    (t
     (extend-streams (car stream-tree)
                     #'(lambda ()
                         (extend-streams (cdr stream-tree)
                                         continuation))))))

With this definition, we have

CL-USER> (extend-streams
          '((a b) (c (d e)))
          #'(lambda ()
              (print *logging-streams*)))
=> (E D C B A) 

Now, was there anything useful about this? In this case, probably not. Some minor benefits might be that extend-streams is tail-recursive, so we don't have a lot of stack usage, though the intermediate closures make up for it in heap space. We do have the fact that the eventual continuation is executed in the dynamic scope of any intermediate stuff that extend-streams set up. In this case, that's not all that important, but in other cases it can be.

Being able to abstract away some of the control flow, and to have non-local exits, or to be able to pick up a computation somewhere from a while back, can be very handy. This can be useful in backtracking search, for instance. Here's a continuation passing style propositional calculus solver for formulas where a formula is a symbol (a propositional literal), or a list of the form (not formula), (and left right), or (or left right).

(defun fail ()
  '(() () fail))

(defun satisfy (formula 
                &optional 
                (positives '())
                (negatives '())
                (succeed #'(lambda (ps ns retry) `(,ps ,ns ,retry)))
                (retry 'fail))
  ;; succeed is a function of three arguments: a list of positive literals,
  ;; a list of negative literals.  retry is a function of zero
  ;; arguments, and is used to `try again` from the last place that a
  ;; choice was made.
  (if (symbolp formula)
      (if (member formula negatives) 
          (funcall retry)
          (funcall succeed (adjoin formula positives) negatives retry))
      (destructuring-bind (op left &optional right) formula
        (case op
          ((not)
           (satisfy left negatives positives 
                    #'(lambda (negatives positives retry)
                        (funcall succeed positives negatives retry))
                    retry))
          ((and) 
           (satisfy left positives negatives
                    #'(lambda (positives negatives retry)
                        (satisfy right positives negatives succeed retry))
                    retry))
          ((or)
           (satisfy left positives negatives
                    succeed
                    #'(lambda ()
                        (satisfy right positives negatives
                                 succeed retry))))))))

If a satisfying assignment is found, then succeed is called with three arguments: the list of positive literals, the list of negative literals, and function that can retry the search (i.e., attempt to find another solution). For instance:

CL-USER> (satisfy '(and p (not p)))
(NIL NIL FAIL)
CL-USER> (satisfy '(or p q))
((P) NIL #<CLOSURE (LAMBDA #) {1002B99469}>)
CL-USER> (satisfy '(and (or p q) (and (not p) r)))
((R Q) (P) FAIL)

The second case is interesting, in that the third result is not FAIL, but some callable function that will try to find another solution. In this case, we can see that (or p q) is satisfiable by making either p or q true:

CL-USER> (destructuring-bind (ps ns retry) (satisfy '(or p q))
           (declare (ignore ps ns))
           (funcall retry))
((Q) NIL FAIL)

That would have been very difficult to do if we weren't using a continuation passing style where we can save the alternative flow and come back to it later. Using this, we can do some clever things, like collect all the satisfying assignments:

(defun satisfy-all (formula &aux (assignments '()) retry)
  (setf retry #'(lambda () 
                  (satisfy formula '() '()
                           #'(lambda (ps ns new-retry)
                               (push (list ps ns) assignments)
                               (setf retry new-retry))
                           'fail)))
  (loop while (not (eq retry 'fail))
     do (funcall retry)
     finally (return assignments)))

CL-USER> (satisfy-all '(or p (or (and q (not r)) (or r s))))
(((S) NIL)   ; make S true
 ((R) NIL)   ; make R true
 ((Q) (R))   ; make Q true and R false
 ((P) NIL))  ; make P true

We could change the loop a bit and get just n assignments, up to some n, or variations on that theme. Often times continuation passing style is not needed, or can make code hard to maintain and understand, but in the cases where it is useful, it can make some otherwise very difficult things fairly easy.