Continuations in Scheme (draft)
(November 10, 2009): lol
(November 15, 2008): Maybe not...
(June 21, 2008): I just graduated and I have couple months before I start working on my PhD. Maybe this thing will actually get updated...
(February 10, 2008): Seriously, I'm going to be updating this thing...
(November 4, 2007): A new semester has started and I need to do some research for my thesis and a couple of presentations. After a few weeks, I'll try
to get back to updating this page and my site in general.
(August 3, 2007): Every month I receive traffic to this page from around the world and I occasionally follow the referral links to see where the traffic is coming from. In doing so, I have noticed that numerous people have actually found this page to be helpful. Since people keep coming, I wanted to let everyone know that the page has not been forgotten and I will be updating it in the future (hopefully, next semester). I did not want to update the page without doing some necessary reading and research (I wrote this long ago in one night without any kind of reference) and I simply have not had enough time.
Purpose- I am creating this document, because most of the information covering continuations that currently exists on the web seems to explain continuations from an unnecessarily complicated point of view. These in-depth explanations are not inherently bad and should be read for a more in depth understanding of continuations, but there doesn't seem to be a resource which gives a simplified explanation of what a continuation is that can be understood by beginners with little mental strain. Hopefully, this page will fill that void.
A continuation is basically any arbitrary point in a program where a value is expected. In the figure below, we see a simple expression which adds the two literal values 2 and 2 (a) . When this expression is evaluated, three values are expected: the procedure (+) and the two operands (2,2). Assuming that the procedure has already been determined, there exist two holes in the expression that need to be filled (b). These holes are two of the continuation points that exist in this expression. During evaluation, these holes will be filled with the literal values 2 and 2 (c). After all of these holes are filled in, the procedure is applied to the operands resulting in the value 4.
The importance of continuations in Scheme is that handles to these holes can be created. This means that we can re-use these holes after the evaluation of the expression has been completed. Below, we see the two empty holes from the figure above. One of these holes is being captured and linked to the hole-handle on the right. Below, we see that the holes have been filled, but the handle to the rightmost hole still exists.
In the figure below, we see that the evaluation of the expression results in the value 4. Remember, though, that we have saved a handle to one of the continuation points above. We take the handle to this continuation point and re-fill it with the value 6. This causes the data from the expression to be recalled and for the whole expression to be re-evaluated with the second 2 replaced by the new value 6. Clearly, this will evaluate to 8. This handle can be used to cause a re-evaluation of the expression with different values in at the saved continuation point as often as we want to use it.
Now, we will look at this example in actual Scheme code. First, we have to define a variable that will eventually be bound to the continuation (a). Next, we will write the expression as below (b). The subexpression (call/cc [...]) is used to capture the continuation that exists where the (call/cc [...]) expression will return (here, the second operand of the addition procedure)*. call/cc requires one argument--a procedure that also takes one argument. In the given example, the procedure passed to call/cc is (lambda (k) (set! handle k) 2). call/cc will take this procedure and pass it the captured continuation point. The procedure then uses set! to bind handle to the continuation point. As demonstrated graphically below, the continuation (the red box) is captured and passed to the provided procedure where the variable k is bound to the passed continuation (c). handle is then bound to k (the continuation) (d).
The value 2 which is returned from the procedure we passed to call/cc will also be returned by call/cc and used to fill the hole in order to complete the evaluation. So, the first evaluation will be equivalent to (+ 2 2), but we will have also captured the continuation that handle is bound to. Subsequently, we are able to pass values to handle which will be used to re-evaluate the expression with the newly provided value.
However, the use of continuations goes way beyond this simple example, which is why you should now find more complicated tutorials and study them. Hopefully, this simple example will allow you, though, to better understand the more complicated information.
From this simplistic viewpoint, continuations may seem like an overly complicated way to create procedures, because the same effect can seemingly be created by:
(+ 2 x)))
*call/cc is not defined in all implementations. If you receive an error when using call/cc, then use (call-with-current-continuation [...]) instead. Alternatively, you can preface your code with (define call/cc call-with-current-continuation) and use (call/cc [...]) as in the examples.