blog.poucet.org Rotating Header Image

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.

Be Sociable, Share!

4 Comments

  1. Gleb says:

    Very interesting post, thanks!
    Now I have a vague idea of what is delimited continuation, but your post ended before I’ve developed deep understanding of the subject.
    There’s a lot of tutorials on continuations and call/cc on the Web, but when I try to google “delimited continuations”, I get links to hardcore CS articles (Kiselyov, Shan, etc). Do you have any pointers for beginners? Thanks!

  2. Christophe (vincenz) says:

    Hello,

    Thanks for the link. I do admit it was rather short, I might expand on it later. I actually didn’t know I had any readers :P . Suffice to say that I found ‘shift to control’ by Shan the most digestible for delimited continuations. It’s more implementation than formalization oriented.

  3. Gleb says:

    >I actually didn’t know I had any readers :P .
    Indeed you have. Didn’t you know that Planet Haskell aggregated your blog ;) ?

    >Suffice to say that I found ‘shift to control’ by Shan the most digestible for delimited continuations.
    Thanks, I’ll give that article a try (I must admit that I’m pretty dumb and Shan’s articles are usually too dense for me).

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>