Here I attempt to apply my sketch of continuations to understand the code which does depth first traversal of a tree using continuations. This code is from Paul Graham’s On Lisp book chapter 20 which you can find on the page here in Figure 20.3. First let us look at the definition of the function dft which does depth first traversal (dft) without continuations. Now we want to do this traversal using continuations so that we can explore the cdr of a tree at a later point in time. The first step in applying the sketch is to find out when to pause so that a continuation can be fetched and stored for a later restart. Obviously this point is when you are about to traverse the cdr of the tree. As such the call to (dft (cdr tree)) should be enclosed by call/cc expression.This is what you will find in the dftnode function. Now we want to find out what should be next step of the computation when it is invoked? What you want is that when the continuation is restarted, the form (dftnode (cdr tree)) be invoked. And we know that the argument v that is passed to the continuation is what decides the future of the computation. As such the argument to the saved continuation cc will be (dftnode (cdr tree)) Now we cannot save a form (cc (dftnode (cdr tree))) for later restart. Hence it is surrounded by another lambda form which can be stored away. Thus you see (lambda () being saved in a list of continuations. Thus the only question that remains now is how are we going to invoke the continuation? In this case it is already enclosed within a lambda form. So the way to restart it is (cont) where cont is a variable pointing to the continuation. And this is what is done in restart function. But we also know that when a continuation is invoked, the current callstack is replaced by that which existed when the continuation was saved! This is what exactly happens when restart function calls the continuation via (cont). The callstack that is active when restart is being executed is replaced by that which was existing when the continuation was saved. As such any code after (cont) in restart will not execute. Visualizing ContinuationsNow let us apply the visual representation of continuations to this example. You can find the visual below. The dftnode is the function where we pause and store the continuation. restart is the function where we invoke the continuation. And when it is invoked, the previous callstack replaces the current one.
Thus you can see that reading and writing code that uses continuations is not so difficult especially when you have a simple underlying sketch in your head.
0 Comments
A simple sketch of continuations in programming that makes them easy to understand I always try to derive a simple sketch of any concept that I can then carry around in my head. Let me describe you my sketch of the hard to understand continuations. Let me begin with an example of a simple expression. (+ 3 (* 3 7)) When you evaluate this expression at the top level, it returns 24. Now let us assume that you have this intention to pause the computation at a certain point and to restart the computation at a later time from where you paused it. Let us denote the inner expression (* 3 7) in above expression as e. Let us denote the entire expression as E. After evaluating this expression, what is the next evaluation? Obviously it is (+ 3 21). Now assume that we want to pause the computation when e was evaluated. Then how could we represent the next computation? We could represent it as follows. (lambda (v) (+ 3 v)) where v is the value of expression e. But the above lambda expression could be stored in a variable and invoked later. So if k is a variable representing the above expression, then (funcall k 21) gives us 24 when e evaluates to 21. However we can invoke k as many times as we want with different values. Okay, you may say what is so great about it? This is just normal day to day lisp stuff. Let us go back to your requirement. The requirement is that the computation must restart from where it was paused. In the above case of k, it is not a real restart. A real restart can happen only when you can switch to the same callstack that was existent when you were computing the expression E in question. So we need to have k such that when we invoke k it switches to the same callstack for E. Then we can safely say that when k is invoked the computation continued from where it was left off and the argument v specifying the future (or next step) of the computation. Hence k is a continuation. Thus a continuation for an expression e in a surrounding expression E can be defined as a computation that takes place only when it gets the value for e. In terms of implementation then k is a function of one argument v such that v is the value with which future (next) compuatation is done and that when it is invoked it replaces the current callstack by that which was existent when the continuation was saved. Continuations never returnThe thing to remember about continuations is that the callstack is replaced. What is the consequence? The consequence is that when you invoke the continuation, you cannot return back to the point of invocation since you are now switched to a different (old) callstack. This is what I think makes continuations a bit harder to understand especially when you come from the expereience of writing code where it is assumed to return. C long jumpers (longjmp) should not find continuations difficult to understand! MechanicsAll this sounds nice but it is equally imporatant to write code that makes use of continuations all the while understanding what is happening beneath. The first thing you want to find out is when to pause. After you identify this point you need to get hold of the continuation (basically a copy of callstack) and store it away so that you can invoke (or restart) it later. Getting hold of a continuation depends upon the language. So if you are in Scheme, you are lucky, because it has inbuilt support for continuations. There is a construct called as call/cc or callwithcurrentcontinuation that expects a function of one argument which it invokes with the continuation object. You can then save this object for later restarts. You can find an example of doing this in Schemehere If you are in common lisp, you can refer to On Lisp chapter 20 which explains how continuations can be added to common lisp using macros. This is a must read chapter as it also shows how the internal implemenation of continuations is a chain of lexical closures. You can read this chapter here. Visual RepresentationVisually we can imagine the saving and restart of a continuation as depicted below. Actually I liedLet us first deal with an example going back to our old expression. (+ 3 (* 3 7)) Let the continuation for this be defined as follows (on the REPL). (define saved #f) Now what do you think will be result of the following expression? (saved (saved 21)) If you think 27, then I am sorry to say it is wrong. The answer is still 24. Why? Go back to the replacement of the callstack concept. The current callstack is replaced by the callstack for outer saved which in turned is replaced by that for the inner one. No returns are happening here! Hence the answer is 24. So if you want a continuation to return you could do that. Such continuations are called partial or delimited continauations. The thing then to remember about partial continuations is that you return to the current callstack from where you invoked the continuation. Obviously the consequence is that you can now compose continuations as in (saved (saved 21)) example. As such they are also known as composable continuations. You can find about Scheme support of delimited continuations here. Delimited continatuations can be built on top of continuations. In Common Lisp, clcont library adds support for delimited continuations using a code walker. Alternatively one could write these operators in CL using macros. Partial Continuations?Simply because the concepts are in opposition. While continuations do not return, partial continuations return. KaBoom! Anyways, if I had to return the control, why not use continuation itself? If a function f2 invokes a continuation for function f1, I might as well write code that invokes the continuation for f2! That way it is explicit and conforming to the definition of continuation. Alternatively, it could be that partial continuations need to be renamed something else!. Further whenever I apply my sketch of continuations to code that uses continuations it works pretty well. Even when I applied it to code which uses delimited continuations (assuming it were continuations) it worked fine. I still think that partial continuations are an open area for me. The above example of partial continuations has been inspired from the one that appears in Lisp in Small Pieces in section 3.7 within chapter 3. Even this book does not find partial continuations interesting. How to apply the sketch?While working with code that uses continuations, you can apply this sketch as follows. Find out the point at which you pause the computation. At this point you will store the continuation. Also figure out what value you need to pass when you restart the continuation. That will also tell you how you are going to invoke the continuation. And remember that the callstack when the continuation is invoked will be replaced by that which existed when the continuation was stored. Applications of the sketchHere you can find an application of the sketch on depth first traversal of a tree using continuations.
Overall the sketch says the following:

MeI am a polyglot software engineer specializing in shipping iOS and 3d scientific visualization applications. Archives
December 2011
Categories
All
