Delimited Continuations in Scala

First, the teaser:

Swarm is a framework allowing the creation of web applications which can scale transparently through a novel portable continuation-based approach. Like Map-Reduce, Swarm follows the maxim “move the computation, not the data”. However Swarm takes the concept much further, allowing it to be applied to almost any computation, not just those that can be broken down into map and reduce operations.

This is pretty cool. It is accomplished using Scala delimited continuations, which are confusing.

Delimited Continuations Explained (in Scala)

I found that link to be pretty helpful, but wanted to jot down my notes because otherwise I’ll have to start from the beginning when I try to understand it again. So this blog post is essentially just a journal entry. Read on if you dare!

In Scala, continuations will be used through two keywords: “reset” and “shift”. Like “catch” and “throw”, a “shift” always happen inside a “reset”, the latter being responsible for delimiting the scope of the continuation.

Wait. What?

“reset” is responsible for delimiting the scope of the continuation

Oh, that didn’t clear things up? How about an example:

def foo() = {
  println("Once here.")
  shift((k: Int => Int) => k(k(k(7))))
def bar() = {
  1 + foo()
def baz() = {
  reset(bar() * 2)
baz()  // result 70

The first thing to keep in mind is that shifts are functions taking a parameter. In this example, that parameter is the function k: Int => Int.

When the continuation function k is called (from within the shift block):

  1. Execution skips over the rest of the shift block and begins again at the end of it
  2. Execution continues until the end of the reset block
  3. Execution resumes within the shift block after k until the end of the shift block
  4. Execution skips to the end of the reset block

So what happens is:

  1. baz() is called, which calls bar(), and then foo()
  2. foo() prints Once here.
  3. The shift block is entered, defining function k and recursively calling k. The innermost call to k(7) occurs first, and execution skips to the end of the shift block. The result is 7.
  4. Now foo() is complete and we’re in bar(), adding 1 to 7 (the result) = 8
  5. Back in baz(), 8 (the result) * 2 = 16
  6. We reach the end of the reset block and resume execution in the shift block. The second call to k occurs with the current value of 16. Execution again skips to the end of the shift block and returns to bar() with this new result of 16
  7. 1 + 16 = 17
  8. 17 * 2 = 34
  9. Reach the end of the reset block again and resume at the end of the second call to k, leading to the third and final call to k with the current value of 34
  10. 1 + 34 = 35
  11. 35 * 2= 70

And the result is:

Once here.

Leave a Reply

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