technology from back to front

Direct implementation of shift/reset in Smalltalk

My work on zippers led me to a very strange thought, which I’ve constructed from Oleg Kiselyov‘s and Chung-Chieh Shan‘s papers: “a zipper is a suspended walk is a delimited continuation”. That was too intriguing to let go, so I started reading.

That in turn led me to the “control operators”, things that let us create and compose continuations. I thought I’d try my hand at implementing shift/reset, mainly because I figured that the lexically-scoped shift would be an easier place to start than control/prompt. (It turns out you can happily implement the one in the other.)

So here’s the one-liner summary of what shift/reset does: first, reset is a function that takes an expression e. It evaluates e and returns it… and, more importantly, marks the stack. At some point within e, something calls the shift function. This is a binary function taking a name and an expression. Shift then cuts out part of the stack – precisely those activation frames between it and the “nearest” reset – and turns them into a function. It then evaluates the expression given it and, during the scope of that expression, one may use the first parameter (the name) as the name of the stack-slice-as-function.

So how to translate this into Smalltalk?

Let’s take the easy problem: how do we mark the stack? Well, it turns out that Smalltalk does that in a number of places… by declaring exception handlers:

  [self my: computation] on: Error do: [self cleanUp].
  [self my: computation] on: Error do: [ :e | self reportException: e].

BlockClosure>>on:do: will exactly what we need:

  on: exception do: handlerAction
    "Evaluate the receiver in the scope of an exception handler."

    | handlerActive |
  "just a marker, fail and execute the following"
    handlerActive := true.
    ^ self value

(What’s handlerActive? It’s a flag used to prevent an Exception from handling its own signal. See Pharo By Example’s chapter on exceptions for the full details (section 1.15).)

The syntax I have in mind is this:

  "Stack reified as [:x | 2 + x] so the expression reduces to
    (1 + (3 + [:x | 2 + x] value: 4))
    ==> (1 + (3 + (2 + 4)))
    ==> 10."
  1 + [ 2 + [ :k | 3 + (k value: 4) ] shift ] reset.

  "Stack again reified as [:x | 2 + x] so the expression reduces to
    (1 + (3 + [:x | 2 + x] value: 5 + [:x | 2 + x] value: 1))
    ==> (1 + (3 + (2 + 5) + (2 + 1)))
    ==> 14."
  1 + [ 2 + [ :k | 3 + (k value: 5) + (k value: 1) ] shift ] reset.

So without further ado, BlockClosure>>reset:

    "Mark the call stack. The handler says 'Exception, this is where the nearest reset is."
    ^ self on: DelimitedControlException do: [:e | e resume: thisContext home].

where DelimitedControlException is a Notification. (As its name suggest, a Notification tells us that something interesting happened, rather than an error. It’s a resumable exception.)

So now, within some block (or code called from within this context, more correctly) we will need to find our way back to the marked context. And it’s easy: if we raise a DelimitedControlException we will enter the handler in #reset. There’s a subtlety here: “thisContext home”. When we enter the method, we have a MethodContext at the top of the call stack. When the block sends #on:do: to itself, a new context appears on the call stack, an instance of a BlockContext. BlockContext>>home returns the context in which the block was defined; in this case, that’s the context representing the execution of the #reset.

  shift: aUnaryBlock
    "Turn the call stack down to the nearest #reset, and reify this partial
     continuation as a function. Then, pass this function to aUnaryBlock."

    | currentCtxt fun resetCtxt |
    currentCtxt := thisContext.
    resetCtxt := DelimitedControlException signal.
    resetCtxt ifNil: [^ MissingResetException signal].

    fun := PartialContinuation from: currentCtxt sender downTo: resetCtxt sender.

    "Throw away the stack down to the context that called the reset."
    currentCtxt swapSender: resetCtxt sender.

    ^ aUnaryBlock value: fun.

As a convenience method we also define BlockClosure>>shift as

    "I am a unary block. Take the call stack to the nearest reset, reifying that
     partial continuation as a function F. Then evaluate myself with F as an argument.

    Note that this is a convenience method for Object>>shift:. See that method's
    comments for details."
    ^ self shift: self.

A PartialContinuation simply stores the contexts and their states. When we actually invoke the reified function, this is what happens:

  value: anObject
    "Deserialise the continuation, returning the first/bottom-most context. Stitch
    the continuation onto the current call stack by telling this bottom context that
    thisContext's sender called it. 'thisContext sender' because thisContext refers
    to the context of the #value: call."
    (self deserialiseFrom: values) swapSender: thisContext sender.

    "Then, tell thisContext that its sender was actually the last/top-most context."
    thisContext swapSender: values first.

    "Finally, 'return' anObject from the caller context... which thanks to the line
    above, is actually values first. This effectively sets anObject as the parameter
    to the reified partial continuation, because instead of 'returning' to our caller
    we 'return' to the next part of the computation - our
    ^ anObject.

The code itself is in the usual place.

Frank Shearar

seven + = 14

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