Oleg's argument against call/cc links to one of his lesser known posts, Delimited continuations do dynamic-wind. In it he first shows how to implement yielding generators in terms of delimited control, and then shows how such generators lead to a natural definition of dynamic-wind, in userland, whereas with undelimited continuations, dynamic-wind has to be primitive.
(This is not entirely true. Kernel can implement dynamic-wind in userland, too, by means of its guarded undelimited continuations. And in Scheme 48, dynamic-wind is also implemented in userland with undelimited continuations, albeit in terms of a slightly lower level API than call/cc. Same is true for other Schemes, such as MIT Scheme. And probably the earliest definition of dynamic-wind, in Embedding Continuations in Procedural Objects is also in userland, so I'm a bit confused actually, as to why Oleg considers dynamic-wind primitive...)
Back to Oleg's generators in terms of delimited control. While one may argue against first-class continuations, whether delimited or not, I think having them in the language is great for quickly prototyping different ideas, such as generators. This has always been a forte of Lisp, and so high-powered control flow operations seem a good fit for the language, even if their runtime cost may be slightly higher than a more specialized, native implementation of some specific control feature, such as generators.
The basic ideas of generators are: you have a block of code, the generator, which may either normally return a value by means of reaching the end of the block, or it may intermittently yield a value. To call a generator, we need a boundary around it, so we wrap it in a prompt with reset. Yielding suspends the generator, capturing its delimited continuation up to the prompt, and delivers the value and this continuation to the caller, outside the boundary. Value and continuation are wrapped up in a special record type, so the caller can distinguish yields from an ordinary return, which doesn't wrap the value in any way (and neither provides a continuation for resuming, obviously). (This could probably be handled more elegantly with Racket's abort handlers.)
In this Gist, I've commented Oleg's implementation of generators and dynamic-wind.
I think it's a great example of how simple it is to add specific control flow features to a language with general (delimited) continuations.
Oh, and in typical Oleg style, the article then goes on about how you can implement call/cc in terms of generators, which makes his dynamic-wind compatible with existing Scheme examples using call/cc.
Manuel Simoni's blog about programming (languages).
I found a gif to represent continuations:
ReplyDeletehttp://i.imgur.com/7caDw.gif
(I'm borrowing this thread to comment on a tweet. Twitter does not allow non-members to respond directly. Pardon the intrusion.)
ReplyDeleteOn twitter Manuel asks whether TCO is needed in cases where the system provides incremental stack growth or where some kind of co-routine is an alternative.
I say the tail recursive programming style is more fundamental for many problems than co-routines. And that TCO is a more fundamental implementation technique than incremental stacks.
Finally, consider an infinite loop, e.g. a top-level event loop. This can be expressed most generally using recursion. Yet this cannot run forever using an incremental stack.
I now return you to delimited continuations. Puns intended.
I'm a bit confused actually, as to why Oleg considers dynamic-wind primitive...
ReplyDeleteI think it's because the implementation of dynamic-wind in terms of call/cc isn't compatible with the original call/cc — you can implement your own dynamic-wind, but it only works with you own modified call/cc; calls to the old one ignore wind thunks. An unreliable dynamic-wind is not very useful, so it effectively has to be primitive.