We already know that delimited continuations are more expressive than undelimited ones (
call/cc). We can trivially express undelimited continuations by wrapping our entire program in a reset marker, while we need a mutable cell to express delimited continuations using
There’s another very handy construct in programming that uses the call stack: dynamic variables. We know that dynamic variables and delimited continuations don’t play nicely with each other. Rather, there are several reasonable semantics for how they could work together, which means there is no obviously correct semantics for how they should work together. Of course, Oleg’s worked all this out for us: we want delimited dynamic variables. What are those?
Let’s look at an example of the kind of trouble we might run into with normal dynamic variables. We’ll use Squeak, but Scala’s implementation has the same issue because it’s pretty much the same implementation. Note that Squeak’s implementation uses a class (not an instance! ) as a dynamic variable. (This is a handy and cheap way of declaring a globally visible thing without major changes like altering variable lookup.) Let’s see the problem:
What should the value of this expression be? Consider that shift cuts out part of the stack, from where we call shift up to where we call reset. In particular it captures part of the stack into a function that looks like this:
[:x | [TestDynamicVariable value: 2 during: [x]]]. In other words, it cuts out the inner change to
TestDynamicVariable. Note that we do not invoke this function in the example above! We just throw away that part of the stack. We thus expect
TestDynamicVariable value to evaluate to
1. Unfortunately, it doesn’t; it evaluates to
Let’s look at how dynamic variables are implemented in Squeak. A
ProcessSpecificVariable is a thread local variable. A
DynamicVariable is a
Each process has a dictionary mapping
DynamicVariable subclasses to values. During the execution of a block, we store the old value, run the block with the new value in the dictionary, and restore the old value. In other words, the variable bindings are not associated with the call stack: they’re changed, and then restored as the stack unwinds. But since the value has changed as a side effect, before the shift, we get the wrong value.
We see that with this implementation, the delimited continuation closes over the entire dynamic environment. Just like with
call/cc, this captures too much. How do we fix this?
There’s a common idiom in Smalltalk code, stemming from Smalltalk having resumable exceptions. (What’s a resumable exception, you ask? It’s something that turns
throw new Exception() into a statement that can return a value, making it possible for an exception handler to recover from an error and resume computing as though nothing happened, from the point where the original exception was thrown.) The idiom looks like this:
Gosh, that looks a lot like a dynamic variable. OK, let’s try formalise this ad hoc idiom:
With this in place, we can say things like this:
OK, but we have this already. So what?
What happens when we throw delimited continuations into the mix?
And here we see that a
DelimitedDynamicVariable captures part of the dynamic environment: precisely those changes between the shift and reset!
 Of course a class is itself an instance, but we won’t go into metaclasses today.