Continuations

The word "continuation" is quite important in understanding what Scheme is and what you can do in a Scheme program. Unhappily, that word is used in Scheme with at least two different meanings. The first is fairly informal, but the second one -- the important one -- is very precise. Yet the two meanings are related, and it will help to talk about both of them.

The first meaning is that "continuation" may refer rather vaguely to what is going to happen next in a Scheme program; that is, what will happen when the program continues onward from where it is now. That is vague because "what happens next" might be interpreted to include just the program instructions that are about to run, or it might also include some contents of the environment that the program will examine in order to make a decision about what to do next, or it might even include information similarly used but received through an input device -- perhaps the user is going to tell the program what to do next.

As a variant on the first meaning, the term "continuation" is sometimes used explicitly to refer to just the program instructions that are about to run. I had that meaning in mind when I created the variant on the "eval" function that I described in a previous tutorial; it is named "e::cons-with-continuation".

The precise meaning has to do with a Scheme object called a continuation, that encapsulates certain particular information about what is going to happen next, in a form in which it can be reused later. A program that uses such a continuation object can in effect restore a previous state of "what is going to happen next", and do it over again. Yet truth is in the details, and understanding just what a continuation does is a matter of being very precise about what information is stored.

These tutorials have mentioned all but one of the items stored in a continuation, so I am going to plunge boldly onward and just tell you what they are. A continuation stores away

• A pointer to the place in the list of instructions being executed, at which is the next instruction that is due for execution. The actual list of instructions is somewhere in Scheme main memory; the term "pointer" as used here merely means that the continuation keeps track of the location of a specific item in that list. The list itself will stay around, unmodified, even though in normal program operation Scheme executes the different instructions in it sequentially.

• A copy -- not a pointer -- of the entire procedure call stack, including both the application records and any other temporary variables that are stored on the stack.

• A pointer to the current environment list, which is also an object in Scheme main memory.

• A copy of another stack that reflects the state of the internal Wraith Scheme procedure that performs the evaluation of expressions. (This is the stored item that I have not mentioned previously; it is rather esoteric for these tutorials.)

The point to note here is that in normal operation it would be very difficult to modify either the list of instructions being executed or the copies of the two stacks, yet it is commonplace to modify the various bindings in the environment list. Thus when the previous state of "what is going to happen next" is restored from the continuation, the environment may be different, and if the list of instructions to be executed includes instructions that examine the environment in order to decide what to do next, the program may well do something different the second time around.

There is one further way in which the use of a continuation can influence the restored state of the world. It has to do with how continuations are created and used, and we will see more about how it works in a moment.

First, though, let's give an example of how continuations might work if you could use them in real life. They are a little bit like time travel, and a little bit like the use of the transporter in the various "Star Trek" stories, but neither of those is quite the right metaphor.

Suppose you are going out of your house to do some yard work. You have in your hand a list of chores to do -- it is part of your own environment. You lift up the hand that contains the list of chores, to wipe sweat from your brow, and at that very moment you make a continuation object (using your other hand, of course), and put it in your pocket.

You finish wiping off your brow with the hand that contains the list of chores, and then you look at the list of chores, to see what you have to do. The list has three items on it: Plant roses, mow the lawn, and haul the garbage out to the curb for pick-up the next day. So you plant roses, mow the lawn, and haul out the garbage. Standing there by the curb, next to the garbage cans, you pull the continuation out of your pocket and write a note on it. The note says, "Why don't you just go back inside and play computer games instead?"

Then you activate the continuation and -- poof! -- you are back standing on the porch, with one hand coming out of your pocket where you just put the continuation, and the other hand, with the list of chores, in the act of wiping sweat off your brow. As before, you finish wiping off your brow and then look down at your list of chores to see what you have to do. The same three items are still there: Plant roses, mow the lawn, and haul the garbage out to the curb for pick-up the next day. Yet as you look around the yard, wonder of wonders, the roses are all planted, the lawn is freshly mowed, and there is the garbage container, sitting out at the curb. There is no work to do! How mysterious -- you could have sworn that just a moment ago the grass was long and full of dandelions, but now it is neatly mowed, and there are freshly-planted roses in the garden, and the garbage cans are all out by the curb. It looks as if the environment has somehow miraculously changed, and all of your chores have been accomplished.

And there's one thing more: As you bring your hand down from wiping off your brow, you notice that there is something else written on your list of chores, that wasn't there when you put your hand up. There is a message in your own handwriting, that reads, "Why don't you just go back inside and play computer games instead?" That sounds like a fine idea, so you do.

This example isn't quite right: There is a specific way to create and use continuations that is hard to convert into a whimsical example. Yet I hope it will give you a feel for what it is that you do with a continuation, and how things can be different the second time around.

The procedure that you use to create and use a continuation is named "call-with-current-continuation". Many Scheme users find continuations difficult to understand, and the way you use "call-with-current-continuation" doesn't help: The problem is, using "call-with-current-continuation" correctly involves no fewer than three different procedures, each of which takes one argument, and it is easy to get mixed up about which procedure is being used where, and for what purpose.

So let's give a preview of what these three procedures are and do:

• First, your goal is to do something with a continuation object. What you have in mind is a procedure application something like this:

  (my-procedure <a continuation object>)
  

  Your own procedure, "my-procedure", is the first of the three procedures of one argument that you must deal with.

• Second, "call-with-current-continuation" is itself a procedure of one argument -- it is the second such procedure that you must deal with. The idea is that you pass "my-procedure" to "call-with-current-continuation" as an argument, like this:

  (call-with-current-continuation my-procedure)
  

  and then it is "call-with-current-continuation" itself that constructs the continuation object on your behalf and performs the procedure application, like this:

  (my-procedure <a continuation object>)
  

  for you. You might consider that "call-with-current-continuation" is acting as a go-between or an administrative assistant, doing some messy work -- creating the continuation object -- so that you won't have to worry about it. (Incidentally, don't get confused about one procedure being called with an argument that is another procedure: That is quite normal, and it happens a lot in Scheme.)

• Third, the continuation object that "call-with-current-continuation" creates and passes to "my-procedure" is also a procedure of one argument -- the third such that you must deal with. Recall that the actual continuation object is a complicated implementation-dependent structure; what is happening is that it gets wrapped up in a procedure that knows how to use it to restore the state of the program, and will do so on your behalf when called. We will see about the argument that you pass to the continuation procedure in a moment.

Let's run that by again. Suppose you evaluate

(call-with-current-continuation my-procedure)

in which "my-procedure" is a procedure that takes one argument. Procedure "call-with-current-continuation" will create a continuation object, and then, acting on your behalf, will evaluate

(my-procedure <the continuation object>)

Procedure "my-procedure" thereby "gets" the continuation object, and it is procedure "my-procedure" that must do something with it. Basically, there are three choices of what to do with the continuation object:

• Procedure "my-procedure" can ignore the continuation object completely, and return whatever value it likes. If that happens, the returned value will be passed back through "call-with-current-continuation", and will be returned as the return value from "call-with-current-continuation". (This action makes perfect sense if we remember to consider "call-with-current-continuation" as a go-between that assists you in using "my-procedure".) Thus if we have

  (define (my-procedure continuation-object) 42)    ;; ==> my-procedure
  

  and then call

  (call-with-current-continuation my-procedure)    ;; ==> 42
  

  we will get "42", as shown, and nothing will become of the continuation object that "call-with-current-continuation" so carefully constructed and passed to "my-procedure".

• Procedure "my-procedure" can ignore the continuation object and never return; for example, "my-procedure" might start a series of tail-recursive calls that went on forever, or "my-procedure" might do some useful work and then exit or return control to the top-level loop. That situation is not as contrived as it sounds: Perhaps the continuation object is only for some kind of emergency use, such as for backing out of an error condition. We will see how continuations can be used that way later in this tutorial.

• Procedure "my-procedure" might actually use the continuation, or set things up so that some other procedure eventually uses it. By "using the continuation" I mean that somewhere, somehow, code like this gets executed:

  (the-continuation-object return-value)
  

  What happens then is that the original code where "(call-with-current-continuation my-procedure)" was called, miraculously wakes up from whatever unknown dimension it has been hiding in, and continues execution, with "return-value" being the value returned from "call-with-current-continuation". If you think that sounds pretty weird, you are not alone. Keep reading, and feel free to go back and reread the last few paragraphs if you wish.

Let's go through things again with a few more technical details:

A continuation object is a procedure that takes one argument. To make use of it, something must call that procedure, and pass an argument to it. Thus in the previous example, of "(call-with-current-continuation my-procedure)", procedure "my-procedure" might alternatively have been defined to do something like this.

(define (my-procedure a-continuation-object)
  ;; 
  ;; "my-procedure" does other work here, perhaps ...
  ;;
  (a-continuation-object 137)
  )

Incidentally, the choice of name "call-with-current-continuation" can be a little confusing when you are learning about continuations: What "call-with-current-continuation" does is call some procedure with a continuation as its argument, and then the procedure thus called (or something else) ends up calling the continuation itself. Do not confuse "calling a procedure with a continuation" with "calling a continuation". There are quite different things going on in these two situations.

Let's go back to the procedure, the lambda expression, that is the continuation object. When it is called, most of what it does has nothing whatsoever to do with the argument that it is given. The lambda expression has embedded within it a way to access the four items that were stored when the continuation object was created. You will recall that those items were a pointer to the list of next instructions to be executed (and to add to the confusion, that list is sometimes also called "the continuation", using the word with its other meaning), a copy of the procedure call stack as it existed then, a pointer to the environment list that was in use at that time, and a copy of another stack that is used internally by Wraith Scheme.

The body of that lambda expression contains code that accesses the inner workings of Wraith Scheme. it restores the list of next instructions to be executed, the procedure call stack, the environment list, and the other stack, to the saved values. The lambda expression then deals with the argument that was passed to it: It puts that argument in the place in Wraith Scheme's inner workings that is reserved for the return values from functions. The lambda expression has then completed its job. Now consider carefully what has happened.

The effect of calling a continuation is as if the original procedure application of "call-with-current-continuation" had simply returned. Whatever code it was that originally started the evaluation of "(call-with-current-continuation <whatever>)" suddenly wakes up from limbo, finds that it has a return value from "call-with-current-continuation", and goes on about its business as if nothing unusual had happened. The return value -- the argument with which the continuation was called -- is the "note from the future" -- about playing computer games -- in the preceding whimsical example.

Note carefully that there are two ways to get "(call-with-current-continuation my-procedure)" to return something. First, procedure "my-procedure" may itself return a value -- as in the example above in which we defined "my-procedure" as follows:

(define (my-procedure continuation-object) 42)    ;; ==> my-procedure

Second, something -- not necessarily procedure "my-procedure" -- may call the continuation object, and pass an argument to it; that argument will be returned from "call-with-current-continuation" when it resumes execution. That was the case in the alternative definition of "my-procedure", which featured the line of code

  (a-continuation-object 137)    ;; Just for variety ...

I feel that I must apologize for the long, technical discussion of "call-with-current-continuation", but the simple fact of the matter is that I have never encountered or discovered an informal description that gets it right. If I ever do run across one, I will rewrite this tutorial and put it in.

I have some examples of using "call-with-current-continuation", that may make things clearer. I must stress that the first few examples are nothing special; they don't really do anything that you couldn't do just as easily without using "call-with-current-continuation" at all. They do not truly exploit the power of continuations; they are just to show you what is going on.

Here is a very simple example that demonstrates that "call-with-current-continuation" is indeed a procedure. In this example, nothing ever actually gets around to calling the continuation.

(define (report-if-procedure thing)
  (if (procedure? thing)
    (display "This thing is a procedure.\n")
    (display "This thing is not a procedure.\n"))
  'all-done
  )    ;; ==> report-if-procedure

(call-with-current-continuation report-if-procedure)
    ;; ==> This thing is a procedure.
    ;;     all-done

The point of that example is that "call-with-current-continuation" really did get "report-if-procedure" running -- that printout came from within the body of "report-if-procedure". So "call-with-current-continuation" is working as advertised: It actually does call the procedure that is its argument. Note also that "report-if-procedure" returns a value -- the symbol "all-done" -- which is in turn dutifully returned by "call-with-current-continuation".

Now let's try using the continuation object to return a value, and have the original caller at least tell us that it has received it.

(define (return-42 continuation)
  (display "return-42 is about to call the continuation with 42.\n")
  (continuation 42)
  'all-done)           ;; ==> return-42

(define (continuation-caller)
  (let ((returned-value #f))
    (display "continuation-caller is about to run \"call-with-current-continuation\".\n")
    (set! returned-value (call-with-current-continuation return-42))
    (display "\"call-with-current-continuation\" returned ")
    (display returned-value)    
    (display ".\n")
    (newline)))          ;; ==> continuation-caller

(continuation-caller)    ;; ==> The following gets printed:
;;     continuation-caller is about to run "call-with-current-continuation".
;;     return-42 is about to call the continuation with 42.
;;     "call-with-current-continuation" returned 42.
;;
;;     #t

This last example demonstrates that "call-with-current-continuation" does return, and returns the value that was passed as argument when the continuation object was called. Note in particular that "call-with-current-continuation" did not return "all-done"; that is because "return-42" called the continuation object before it got to its return value. Procedure "return-42" effectively disappeared from the flow of program execution when the continuation object restored that state of execution from its own, internal copies of the stacks, environment, and list of instructions. This example is not particularly spectacular, though: You certainly don't need to use "call-with-current-continuation" to return 42 from a procedure application.

Now let's try something a bit more unusual. When we invoke "call-with-current-continuation", the procedure called is going to store the continuation away in a top-level variable, and then call the continuation with a value. The procedure that called "call-with-current-continuation" will report the returned value that it eventually gets.

(define saved-continuation #f)             ;; ==> saved-continuation

(define (save-the-continuation the-continuation)
  (display "save-the-continuation is about to save the continuation and then call it with 0.\n")
  (set! saved-continuation the-continuation)
  (the-continuation 0))                    ;; ==> save-the-continuation

(define (continuation-caller)
  (let ((returned-value #f))
    (display "continuation-caller is about to run \"call-with-current-continuation\".\n")
    (set! returned-value (call-with-current-continuation save-the-continuation))
    (display "\"call-with-current-continuation\" returned \"")
    (display returned-value)    
    (display "\".\n")
    (newline)))                            ;; ==> continuation-caller

(continuation-caller)                      ;; ==> The following gets printed:
;;     continuation-caller is about to run "call-with-current-continuation".
;;     save-the-continuation is about to save the continuation and then call it with 0.
;;     "call-with-current-continuation" returned "0".
;;
;;     #t

(saved-continuation 'resurrected)          ;; ==> The following gets printed:
;; "call-with-current-continuation" returned "resurrected".
;;
;; #t

(saved-continuation 'resurrected-again)    ;; ==> The following gets printed:
;; "call-with-current-continuation" returned "resurrected-again".
;;
;; #t

In this example, we have done two new things: First, we have used the same continuation more than once. Second, we have used a continuation after the code to which it returned a value had already finished running and returned to top level. The second and third calls of the continuation -- that is, the two calls of "saved-continuation" -- each in effect resurrected the original procedure application of "continuation-caller" to a point in the middle of its execution, at which point it received the new value returned from the continuation, printed it out again, and once again exited. That should not be surprising, since you know just what was saved away when the continuation was created. The saved information was precisely what is required to reconstruct the middle of a procedure application -- that is what continuations are supposed to do.

The ability to jump to an arbitrary place in code by using a continuation has sometimes given continuations a bad name. I have heard it said that "A continuation is a go-to statement with a Ph.D. in computer science." If you have heard any of the preaching against go-to statements that has been common in the history of computer science, that accusation is just plain cruel! Yet it is definitely true that continuations are a powerful feature of Scheme, and with great power goes the ability to get into powerful trouble.

It is difficult to bring a procedure application back from the dead without using a continuation in this manner, but you might argue that if we wanted to create a special procedure that anyone could call repeatedly, we might just as well have written the procedure in the first place. Why bother with creating a continuation and then saving it? That argument has merit, but there are issues of style and simplicity that might favor a using a continuation.

For example, you might want to construct the special procedure dynamically, from within the body of another procedure, rather than typing or loading it in at top level. You can do that, but it takes a lot of typing in the original source code to put in all the syntax of the lambda expression that is going to be the body of the special procedure, plus any "let"s, "let*"s, or "letrec"s that might be required to bind the state that the procedure will need. Using a continuation might be simpler and easier to understand.

For another example, using a continuation sometimes facilitates making a complicated return from deep within a series of procedure applications. Perhaps procedure "main" calls procedure "foo", and decides what to do next depending on what "foo" returns. Procedure "foo" might in turn call "bar" and make a similar kind of decision, and "bar" might call "baz", and so on. In real-world applications, such chains of procedure calls might get pretty deep. Sometimes it is easier to pass continuations, to be used for returning values to various places, as arguments to the successive functions ("foo", "bar" and "baz"), or to bind those continuations to top-level variables for general use, than to mess with the logic involved in testing for complicated return conditions one return at a time.

That last issue often occurs when reporting error conditions. It is common to have some repetitive series of similar complicated tasks, in which each task might succeed or fail. In such cases the natural top-level structure is very likely something set up for tail-call optimized tail-recursion, like this, with several functions left to your imagination.

(define (do-tasks)
  (if (error? (do-one-task (get-next-task)))
    (display "This task failed.\n")
    (display "This task succeeded.\n"))
  (do-tasks))

in which you might be tempted to write

(define (do-one-task some-task)
  (if (error? (do-first-part some-task))
    error-type-1
    (if (error? (do-second-part some-task))
      error-type-2

       ...                          ;; Lots of nested "if"s here ...

       (if (error? (do-forty-second-part some-task))
         error-type-42
         success)))  ... )))        ;; Lots of right parentheses here ...

Now in the first place, that code is a mess. It would be much better to write each part of the task to call an error handler if it had a problem, and if not, just call the next part tail-recursively.

(define (do-nth-part some-task)
  ;;
  ;;   <Do some real work here.>
  ;;
  (if <I have a problem>
    (error-handler error-type-n)
    (do-n+1-th-part some-task)))

That is better, except that any error handler you create will eventually have to return, in which case your flow of execution is right back inside of "do-nth-part". At that point, "do-nth-part" itself had better be ready to return, because if you do any more work inside of "do-nth-part" after encountering an error, you are very likely causing some other error that is even more serious.

But if the error handler either is a continuation (perhaps one that was passed along as an argument through the chain of calls to the various parts), or else calls a continuation, then the error handler never returns, and you can use calls to it willy-nilly, anywhere in your code, with confidence that once the error handler has been called, nothing else in the entire procedure call stack, beyond the point where the continuation was created, will be executed. Look carefully at this next block of code to see what I mean; in it, I have not had to set things up so that the overall function returns after every call of the error handler.

(define (do-nth-part some-task)
  ;;
  ;;   <Do some real work here.>
  ;;
  (if <I have a problem of type A>
    (error-handler error-type-n-A))
  ;;
  ;;   <Do some more real work here.>
  ;;
  (if <I have a problem of type B>
    (error-handler error-type-n-B)
  ;;
  ;;   <Do some more real work here.>
  ;;
  (if <I have a problem of type C>
    (error-handler error-type-n-C))
  (do-n+1-th-part some-task))

Do you see how much simpler that code is than it would be if I had to set up a nest of "if"s to make sure that the overall procedure returned after every call to the error handler? This kind of use of a continuation makes life much easier if you need to deal with a variety of possible errors within a single procedure.

It also often turns out that using continuations makes it easier to write code that is properly tail-recursive. The general idea here is that if you have to test for the result of a procedure and decide on that basis what to return, like this

(define (big-function)
  (if (some-test (foo))
    (do-this)
    (do-that)))

Then the call to "foo" cannot be tail-call optimized, because the enclosing procedure, "big-function", has something to do after "foo" has returned. On the other hand, if you had decided to use continuations to return values through multiple levels of calls, you could have written your code from the beginning so that any function could decide for itself when to return a value, and to what level. In that case, the call to "foo" would probably not have to be part of the predicate of an "if", and it could have been tail-call optimized. The point here is that continuations and tail recursion often work well together. Unfortunately, newcomers to Scheme often have never heard of either one, so it sometimes take them a long time to understand the advantages of the combination.

There is no doubt that continuations are one of the most difficult parts of Scheme to understand, but there is also no doubt that they are one of its most powerful features. If you don't understand them right away, don't worry -- you are not alone -- but don't forget about them! Play around with them, try them out, and occasionally reread such documentation about them as you can find. Eventually you will probably be glad you did.

-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)