technology from back to front

Resumable exceptions can macro-express delimited dynamic variables

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 call/cc.

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! [1]) 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:

TestDynamicVariable value: 1 during: [
    [TestDynamicVariable value: 2 during: [
        [:k| TestDynamicVariable value ] shift ]] reset]

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 2. Why?

Let’s look at how dynamic variables are implemented in Squeak. A ProcessSpecificVariable is a thread local variable. A DynamicVariable is a ProcessSpecificVariable

ProcessSpecificVariable >> value
    "Answer the current value for this variable in the current context."
    ^Processor activeProcess environmentAt: self ifAbsent: [self default].

DynamicVariable >> value: anObject during: aBlock
    | p oldValue |
    p := Processor activeProcess.
    oldValue := p environmentAt: self ifAbsent: [self default].
    ^[
        p environmentAt: self put: anObject.
        aBlock value ]
            ensure: [ p environmentAt: self put: oldValue ].

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:

ExceptionTester >> simpleResumeTest
    "see if we can resume twice"
   
    [ | it |
    self doSomething.
    "Throw an exception"
    it := MyResumableTestError signal.
    "it now contains the value 3 because of the wrapping exception handler"
    it = 3 ifTrue: [self doSomethingElse].
    "Just for kicks, show that we can resignal the resumed exception."
    it := MyResumableTestError signal.
    "Again, the exception handler resumes the exception"
    it = 3 ifTrue: [self doSomethingElse].
    ]
        on: MyResumableTestError
        do:
            [:ex |
            self doYetAnotherThing.
            "The magic spot: turn the throwing of an exception into
             a value-returning expression."

            ex resume: 3]

Gosh, that looks a lot like a dynamic variable. OK, let’s try formalise this ad hoc idiom:

Object subclass: #DelimitedDynamicVariable
    instanceVariableNames: 'default'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Control-Core'.

DelimitedDynamicVariable class >> default: anObject
    ^ self new default: anObject.

DelimitedDynamicVariable >> default
    ^ default.

DelimitedDynamicVariable >> default: anObject
    default := anObject

DelimitedDynamicVariable >> dlet: anObject in: aBlock
    "I know which exceptions to handle. See #handle: for details."
    ^ [aBlock value] on: self do: [:e | e resume: anObject]

DelimitedDynamicVariable >> dref
    ^ (DelimitedDynamicVariableRef dynVar: self) signal
        ifNil: [default]

DelimitedDynamicVariable >> handles: anException
    "When the exception is raised, the exception searches for a handler.
     It does this by finding the nearest stack frame marked with primitive
     199, and sends the #handles: message to the object (almost always a
     class) to find out if that stack frame handles this exception.
     In order for us to have one kind of exception for dereferencing a
     dynamic variable, we need to 'parameterise' the handler. This will only
     handle the given exception if that exception has been associated with
     this delimited dynamic variable."

    ^ (anException isKindOf: DelimitedDynamicVariableRef)
        and: [anException dynVar == self]

With this in place, we can say things like this:

| p |
p := DelimitedDynamicVariable default: 0.
p dlet: 3 in: [
    p dlet: 2 in: [
        p dref "=> 2"
    ]
].

OK, but we have this already. So what?

What happens when we throw delimited continuations into the mix?

"A shift not capturing a change in a dynamic binding."
| p f v1 v2 v3 v4|
p := DelimitedDynamicVariable default: #uninitialized.
p dlet: 1 in: [
    f := p dlet: 2 in: [
        "Capture part of the stack, but nothing interesting. k
         becomes the function [:x | x + p dref]."

        [[:k | v1 := p dref. k] shift + p dref] reset ].
    v2 := p dref.
    v3 := f value: 100.
    v4 := p dref].
"Inside shift, outside shift, inside again, outside again."
{v1. v2. v3. v4} "=> #(2 1 101 1)"

"A shift capturing a change in a dynamic binding."
| p f v1 v2 v3 v4 |
p := DelimitedDynamicVariable default: #uninitialized.
p dlet: 1 in: [
    f := [p dlet: 2 in: [
            "k becomes the function [:x | p dlet: 2 in: [ x + p dref ]]"
            [:k | v1 := p dref. k] shift + p dref]] reset.
    v2 := p dref.
    v3 := f value: 100.
    v4 := p dref].
"Inside shift, outside shift, inside again, outside again."
{v1. v2. v3. v4} "=> #(1 1 102 1)"

And here we see that a DelimitedDynamicVariable captures part of the dynamic environment: precisely those changes between the shift and reset!

[1] Of course a class is itself an instance, but we won’t go into metaclasses today.

by
Frank Shearar
on
27/06/12
 
 


− six = 1

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us