Saturday, July 4, 2009

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]))
}

24 comments:

  1. Thanks for a great article. The concept of continuations is finally beginning to make sense for me.

    For what areas/problems do you see yourself using continuations?

    ReplyDelete
  2. Well, from What I understood, shift and reset will be implemented as a library + compiler plugin. I'm still struggling with the "List Monad as continuation" example

    ReplyDelete
  3. All my links got broken. Blogger's doing, not mine.

    ReplyDelete
  4. Except for the "different" new syntax, how is this any better from defining functions that take callback functions as a parameter?

    ReplyDelete
  5. It is really not any different from that, in the same sense that Java is not really any different than machine code.

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

    Using delimited continations:
    List((left.reflect[Any], right.reflect[Any]))

    ReplyDelete
  6. This is by far the best explanation of continuations in Scala I have seen yet. I mostly understand what is going on now, but continuations as part of an expression is still a little mind warping, and seems to have no utility I can think of.

    It would be interesting to see if continuations could make User Interface implementation a little easier by replacing SwingUtilities.invokeLater() and/or SwingWorker with something more light weight or more readable.

    ReplyDelete
  7. Wait.

    That's WRONG.

    A "Continuation", as I understand it, works like this:

    reset {
    val y = shift { (k : Int => Unit)
    val x = 2 + 3
    println("Inside call/cc")
    k( x )
    println("This never gets printed.")
    }
    println("2 + 3 = " + y)
    }

    Should output

    Inside call/cc
    2 + 3 = 5

    Not

    Inside call/cc
    2 + 3 = 5
    This never gets printed.

    ReplyDelete
  8. Well, it outputs what you think it shouldn't. The question is, why do you think it is wrong? Perhaps you read all about general continuations and not enough of delimited continuations? Or was it something in my text that lead you to expect otherwise?

    ReplyDelete
  9. Oh. Never mind.


    How did I do so much research on continuations, call/cc, and continuation passing style in order to wrap my head around it, and miss this?

    Sorry.

    ReplyDelete
  10. "Programming Languages: Application and Interpretation" has some beautiful examples on general continuations, using them for a micro-web-framework. For that purpose, continuations are already used in practice in various cases. A success story about this was written by Paul Graham:

    http://www.paulgraham.com/avg.html
    http://lib.store.yahoo.net/lib/paulgraham/bbnexcerpts.txt

    I would really like, however, to understand how to do the same with delimited continuations. It seems to me (with my current limited understanding) that one needs to use reify to save the continuation, which looks even scarier!

    ReplyDelete
  11. Is it possible to explain simply what is the motivationon this brain twisting non-sense ?

    ReplyDelete
  12. Please could you explain what is the motivation of continuations ?

    ReplyDelete
  13. I also agree that it is quite mind twisting, and I have been unable to get any of the examples to work in Eclipse with the latest Scala plugin.

    From what I understand, continuations are another form of control like if, while, try, etc. The motivation is to make it easier to express some forms of control in distributed or parallel applications. Unfortunately I don't understand well enough to give a clear example.

    ReplyDelete
  14. An interesting thing you could do with continuations is: stop a process send it over the the network to an other computer and then continue at the point where you left of. There is a Framework that implements this behavior on top of scala using continuations.

    http://code.google.com/p/swarm-dpl/

    ReplyDelete
  15. the example:

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

    would not work as expected using your transformation "rule":

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

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

    i think the example should be "translated" to:

    println(1); ((c: Unit => Unit) => { c(); c(); println(2) }) ((x: Unit) => println(3))

    ?

    ReplyDelete
  16. You are correct. "Before" should be moved outside the function call to be strictly correct. I'll consider how to rewrite that explanation.

    ReplyDelete
  17. I am planning to use continuation support in the scala language through shift and reset to track the users who are logged in(We are trying to use this instead of using session or cookie to track the users logged in). So please provide us any sample programe to implement the continuation support through shift and reset to track the logged users in scala.

    ReplyDelete
  18. "Deprecating the Observer Pattern (Maier, Rompf, and Oderksy, http://lamp.epfl.ch/~imaier/pub/DeprecatingObserversTR2010.pdf) is a good article for seeing how continuations can be more than just a way to tie your brain in knots. It shows how you can use continuations to write event-handling code without having to break it up into a bunch of separate event handlers.

    ReplyDelete
  19. I agree that "Deprecating the Observer Pattern" is a good article, but that article also ties my brain in knots.

    I would really like to see a non trivial example of how continuations can work in the UI that I can follow.

    ReplyDelete
  20. @Eric Kolotyluk: Continuations weren't necessarily intended for use at the UI layer..

    ReplyDelete
  21. Great explanation on continuations.

    Thanks !

    @Seth : Thanks ... that paper really helps!

    ReplyDelete
  22. Great article! I did it almost instantly

    def a(x: Int) = shift { k: (Int=>Int) => k(x) }

    def fib(n: Int): Int @cps[Int] = n match {
    case x if (x > 2) => fib(x - 2) + fib(x - 1)
    case x => a(x)
    }

    reset {
    fib(5)
    }

    Now, continue reading... ^)

    ReplyDelete
    Replies
    1. A previous post is not quite correct, but trying this:

      def fib(n: Int): Int @cps[Int] = {
      def fib0(n: Int, sub1: Int, sub2: Int): Int @cps[Int] = n match {
      case x if (math.abs(x) < 2) => shift { k: (Int=>Int) => k(x) }
      case x => fib0(x - sub1, sub1, sub2) + fib0(x - sub2, sub1, sub2)
      }
      val s = math.signum(n)
      fib0(n - s, s, s * 2)
      }

      throws java.lang.StackOverflowError:

      reset { fib(15) }

      Is it possible to handle this, using continuations?

      Delete