Delimited Continuations Explained (in Scala)

One of the promised features for Scala 2.8 is a delimited continuations plugin. A brief description was given in the Scala site, though the examples were, in my opinion, badly chosen.

Though my understanding is still pretty bare, I intend to shed a bit of light on it here. This is not directed at the experts, the people who will actually use them regularly, but at the people who will see them occasionally and will wonder what the heck is happening. Also, I might quite possibly have made mistakes below. If you do find mistakes, please correct me and I’ll fix the post.

First, let’s discuss why Scala is adopting continuations, and what, exactly, are them.

Continuations are, in essence, a program flow control structure, like conditional statements, loops, exceptions, etc. As mentioned in Scala’s Continuations Paper, classical, or full, continuations can be seen as a functional version of GOTO statements. If you haven’t heard of GOTO statements before, it’s enough to know they are essentially extinct for good reason.

Still quoting, delimited continuations are more like regular functions and less like GOTOs, and this makes them more powerful than the classical ones. So, basically, we are looking into a way of changing the execution flow of a program.

Using continuations is not easy. In fact, it’s difficult and error-prone, according to some references. But they can be very efficient performance-wise, and they allow one to build libraries with some interesting flow control abstractions built on top of continuations.

For these reasons, I doubt most Scala users will have much contact with them, and I suspect the ones who do will regret the necessity. The people writing libraries and frameworks, though, will likely be grateful that they are available. In that respect, continuation is not unlike some other advanced Scala features.

Ok, so let’s get to them. In Scala, continuations will be used through two keywords (or functions?), “reset” and “shift”. Like “catch” and “throw”, a “shift” always happen inside a “reset”, the later being responsible for delimiting the scope of the continuation. Before we proceed, let’s give some usage examples, which I’ll then try to explain.

Example 1:

reset {
shift { k: (Int=>Int) =>
 k(7)
} + 1
}
// result: 8

Example 2:

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

Example 3:

reset {
 println(1)
}
//prints: 1

reset {
 println(1)
 shift { (cont: Unit => Unit) => }
 println(2)
}
//prints: 1

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     println(2)
 }
 println(3)
}
//prints: 1 2

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     cont()
     println(2)
 }
 println(3)
}
//prints: 1 3 2

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     cont()
     cont()
     println(2)
 }
 println(3)
}
//prints: 1 3 3 2

So we have two examples of continuations as expressions, and one as purely flow control. The first example seems pretty simple: the whole shift is replaced with “7”, and, therefore, reset returns “7+1”. The third example shows that, in fact, the code before shift is executed once, the code after shift as many times as the function inside shift is repeated, and the code inside the shift itself is executed once, going back and forth to the code after it.

So we look at the second example, and see that… the code before shift seems to get executed many times! Actually, the method receiving the result of shift is being executed many times, once for each time “shift” return, but the statement right before shift only gets executed once.

These examples were probably enough to… make things more confusing, right? So let’s understand what is happening. Scala’s continuations are based on a selective Continuation Passing Style (CPS) transformation. The Wikipedia page on CPS is actually pretty good, so, please, take a moment to peruse it, and understand the examples given at the beginning, and then come back here.

Ready? Well, one thing that immediately came to mind is that this looks like programming backwards! They call it “inside-out” in that page, which is more appropriate, I suppose, but one has to pay attention to first impressions. :-)

What is happening there is that the innermost functions of normal programming style are outmost, and vice versa. You’ll see that this is what is happening with shift and reset.

I’ll now explain a bit of what is happening in a continuation. Notice, first, that the code associated with the shifts are functions: they are all in the form { k => … }. So, the first thing to keep in mind is that shifts are functions taking a parameter.

Now, pay attention, again, to the very first example. It defines the type of k as being “Int => Int”. In the first example, then, shift is a function which takes as parameter another function. This is actually true of all shifts, even if the function being passed to shift takes no parameters and returns Unit.

So a shift is a function which receives another function as parameter. As the body of the shift gets executed, that function-parameter may get called or not. From the second example, it is pretty obvious that the code after the shift only gets executed if that function-parameter is called.

By now you probably have an uneasy intuition that that parameter is, in fact, the code after the shift. That’s essentially right, but let’s further into this.

The result of reset is the result of the code inside shift. So, in the first example, “8”, the result of reset, is also the result of the shift code, “k: (Int => Int) => k(7)”. It should be obvious, then, that the value passed to “k” is “x: Int => x + 1”, which is a function of Int => Int, as required. Now, take a look at the two lines below:

shift { k: (Int=>Int) => k(7) } + 1
x                               + 1

So, the function being passed as parameter is formed by taking the whole code from the shift on, and replacing shift with “x”. In effect, when k(7) is executed, this is like replacing the whole shift with 7, and then continuing until the end of reset. At that point, though, the execution resumes inside the shift. In this example there is nothing more in there, so the result is 8.

What is actually happening is this:

((k: Int => Int) => k(7))((x: Int) => x + 1)

As said before, we are passing a function to another. You can paste that code inside REPL and it will work as expected. You may also try this code here:

((k: Int => Int) => k(k(k(7))))((x: Int) => (1 + x) * 2)

Are you getting a feeling now for it? So, whenever you see reset/shift, first think of the whole reset expression, replacing the shift inside it with an unknown variable – we’ll keep calling it x for now:

Reset { before shift { k => ... k(something) ... } after }
Reset { before x after }

Now replace Reset with a function declaration of one parameter:

Reset { before x after }
x => { before x after }

What type is “x” supposed to be? You can find it inside the shift, by looking into what is being passed to “k” – the “something” in the example. We can now rewrite the whole reset statement, placing first the shift code, then the reset code as parameter, like we did before:

( k => ... k(something) ... ) {x => { before x after }}

And this is pretty much what happens when you use continuations.

As for the second example, though the “1 + “ looks to be to the “left” of shift, it actually gets executed after shift returns, so it is part of the function being passed to shift. You find the same situation when making tail recursive functions. If you tried “1 + recurse()”, it would not be tail recursive, because “+” would only be executed after the call to “recurse” returned.

Pretty easy, right? Let’s try something with two shifts:

type Monadic[+U, C[_]] = {
def flatMap[V](f: U => C[V]): C[V]
}

class Reflective[+A, C[_]](xs: Monadic[A,C]) {
def reflect[B](): A @cps[C[B], C[B]] = {
 shift { k:(A => C[B]) =>
   xs.flatMap(k)
 }
}
}

implicit def reflective[A](xs:Iterable[A]) =
new Reflective[A,Iterable](xs)

reset {
val left = List("x","y","z")
val right = List(4,5,6)

List((left.reflect[Any], right.reflect[Any]))
}
// result: List[(String, Int)] = List((x,4), (x,5), (x,6), (y,4), (y,5), (y,6), (z,4), (z,5), (z,6)

Don’t hate me, it is in good cause. :-) If you can understand this… well, you can understand this. But I’m sure you’ll start to really get a grip in it.

First, let’s discard the irrelevant parts of the code above. Everything but the “reflect” definition and the reset code is irrelevant. They are there just to make “reflect” available to a List, it’s plain-old Enrich My Library pattern, though the use of a structural type is cool. :-)

Now, let’s replace left.reflect and right.reflect with the actual code getting executed – I’ll change k into k1 and k2 so as not to confuse both, so we are left only with the reset code:

reset {
val left = List("x","y","z")
val right = List(4,5,6)

List((shift { k1:(String => List[Any]) => left.flatMap(k1)}, shift { k2:(Int => List[Any]) => right.flatMap(k2)}))
}

Since there are two shifts, should we have two unknowns being passed to shift? If you look at the type signatures for k1 and k2, the answer is no. Each shift gets a single parameter.

You may think that the “Any” type means one list is formed by a single element, and the other by a tuple, but that’s not true. You can change both types to “List[(String,Int)]”, and it would still work. No, the type signatures are right, the trick is in how they are composed together.

If you think it through simply in terms of flow control, the first shift will return a value (“x”), and then the second shift will return a value (4), producing a list. The flow then returns to the last shift, which will return another value (5), and then another still (6). At this point, the flow returns once again to the first shift, which will produce it’s next value (“y”). So the trick is in how we compose the functions.

Let’s see, first, both shifts:

((k1: String => List[(String,Int)]) => left.flatMap(k1))
((k2: Int => List[(String,Int)]) => right.flatMap(k2))

These can’t and won’t be changed. The trick is how we compose them:

((k1: String => List[(String,Int)]) => left.flatMap(k1))
((x: String) => ((k2: Int => List[(String,Int)]) => right.flatMap(k2))
             ((y: Int) => List((x,y)))
)

So what happens is that the function which takes a String and returns a List of (String,Int) that gets passed to the first shift is composed of both the reset function and the second shift function.

The function passed to the second shift does not need an additional String parameter because the string is already bound.

Now you have seen both the control flow of reset/shift, and how to translate them into common functions to understand what values they will produce. I hope it will be of help when the time comes in which you need to understand these structures.

Note: many things have changed since I wrote this blog. Continuations have gone through minor changes in the annotations, and collections have gone through big changes. I haven't checked out all examples yet, but I know the one with the two lists doesn't work anymore. The following code will work for that example, though I wish I could make it more general than it presently is:

type Monadic[+U, C[_]] = {
  def flatMap[V, That](f: U => C[V])(implicit cbf: collection.generic.CanBuildFrom[C[U], V, That]): That
}

class Reflective[+A](xs: Monadic[A,Traversable]) {
  def reflect[B](): A @cps[Traversable[B]] = {
    shift { k:(A => Traversable[B]) =>
      xs.flatMap(k)(collection.breakOut) : Traversable[B]
    }
  }
}

implicit def reflective[A](xs:Traversable[A]) = new Reflective[A](xs)

reset {
  val left = List("x","y","z")
  val right = List(4,5,6)

  List((left.reflect[Any], right.reflect[Any]))
}