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 dft-node 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 (dft-node (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 (dft-node (cdr tree)) Now we cannot save a form (cc (dft-node (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 dft-node 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
Your comment will be posted after it is approved.
Leave a Reply. |
MeI am a 3D graphics software engineer. Archives
December 2011
Categories
All
|