blog.poucet.org Rotating Header Image

April 10th, 2007:

Delimited continuations revisited

I thought it would be interesting to return to delimited continuations and explain what they are.

First of all there is the word continuations. Continuations are, simply put, the remainder of a computation. Take for instance this simple piece of code:


(begin
(print 1)
(return)
(print 2)
)

Now, the print(2) is never reached. If, however, one used continuations, then one could capture the remainder of the computation after the return before returning and store this somewhere to invoke it at a later date.


(begin
(print 1)
(call/cc (lambda (x) (set! globalx x) (return))
(print 2)
)

If later one invokes the globalx, one is returned to where we left off and computation continues. So in essence, a continuation captures the return-path of where it was called, all the way to the end of the program (or in scheme, to the top-level). Notice that it captures the return-path in a dynamic sense, not a static sense. This means that if it is captured inside a loop, it will return to that specific loop-iteration.

Secondly there is the concept of ‘delimited’. If one thinks of a continuation, then one can see it has a beginning, namely when call/cc is called, but no end (the end is the end of the program). Therefore, one can represent it as a half-closed interval: [) where the start is obviously the return-path from call/cc while the end is the end of the program. One might argue that the end of the program can be seen as the end, but in the presence of continuations, this is not very well defined. Delimited continuations, however, are defined with a certain block, and this block has a very definitive end, namely the end of that block. Therefore, one can represent this as a fully-closed interval: []. This also explains why one needs two continuations to emulate delimited continuations.

Delimited continuations revisited

I thought it would be interesting to return to delimited continuations and explain what they are.

First of all there is the word continuations. Continuations are, simply put, the remainder of a computation. Take for instance this simple piece of code:


(begin
(print 1)
(return)
(print 2)
)

Now, the print(2) is never reached. If, however, one used continuations, then one could capture the remainder of the computation after the return before returning and store this somewhere to invoke it at a later date.


(begin
(print 1)
(call/cc (lambda (x) (set! globalx x) (return))
(print 2)
)

If later one invokes the globalx, one is returned to where we left off and computation continues. So in essence, a continuation captures the return-path of where it was called, all the way to the end of the program (or in scheme, to the top-level). Notice that it captures the return-path in a dynamic sense, not a static sense. This means that if it is captured inside a loop, it will return to that specific loop-iteration.

Secondly there is the concept of ‘delimited’. If one thinks of a continuation, then one can see it has a beginning, namely when call/cc is called, but no end (the end is the end of the program). Therefore, one can represent it as a half-closed interval: [) where the start is obviously the return-path from call/cc while the end is the end of the program. One might argue that the end of the program can be seen as the end, but in the presence of continuations, this is not very well defined. Delimited continuations, however, are defined with a certain block, and this block has a very definitive end, namely the end of that block. Therefore, one can represent this as a fully-closed interval: []. This also explains why one needs two continuations to emulate delimited continuations.