Rich Dougherty ⬦ rd.nz

Delimited continuations in Scala

In a recent thread on scala-user it was announced that Tiark Rompf is writing a Scala compiler plugin for working with delimited continuations. The plugin is still in development, but it is scheduled to be included in Scala 2.8.

The plugin transforms the parts of the program contained within a call to reset into continuation-passing form. Within the transformed part of the program, continuations can be accessed by calling shift.

All of this is done (rather elegantly, I think) by introducing a new @cps type annotation. At compile time the plugin converts anything that produces a value of type A @cps(B,C) into a ControlContext[A,B,C] object that contains the computation. The A here represents the output of the computation, which is also the input to its continuation. The B represents the return type of that continuation, and the C represents its “final” return type—because shift can do further processing to the returned value and change its type. (Hopefully someone will read this and let me know if I’m wrong about any of this!)

I’m excited about this plugin because I think it is going to be very helpful for the asynchronous IO work I’m doing as part of Scala OTP. For some time now I’ve been manually converting parts of Scala OTP to use continuation-passing style (so that those parts can be suspended while waiting for IO). This is painstaking work, and also makes the code very hard to read. Using the plugin will simultaneously make my life a lot easier and make the code more accessible for others.

The main shortcoming I can see with the plugin at the moment is that it doesn’t really handle exceptions. However, I’ve been looking at the plugin’s source and I think it should be possible to add exception support without too much trouble.

Building the plugin

This is pretty easy to do.

First you will need a recent build of Scala. You can either install a nightly binary or build it from source yourself.

$ wget http://www.scala-lang.org/archives/downloads/distrib/files/nightly/scala-2.8.0.r17146-b20090219020925.tgz
$ tar xzf scala-2.8.0.r17146-b20090219020925.tgz

Once you have a build, set the SCALA_HOME environment variable to point to your new installation.

$ export SCALA_HOME=.../scala-2.8.0.r17146-b20090219020925

Next get the source for the continuations plugin.

$ svn co http://lampsvn.epfl.ch/svn-repos/scala/compiler-plugins/continuations/trunk continuations
$ cd continuations

Then build it.

$ ANT_OPTS=-Xmx512m ant test

You should see the plugin’s JAR being built (selectivecps-plugin.jar) and its tests should run and pass.

Trying it out

You might want to have a go at writing code that uses delimited continuations. At the moment there isn’t any documentation for the plugin, so the best way to work things out is to look at the code in doc/examples and in test.

It’s also sometimes helpful to pass -Xprint:selectivecps to scalac when you’re compiling your programs. This option tells the compiler to print out the program immediately after the plugin has done its work. By this point in the compilation all the continuation-passing has been made explicit so you’re looking at normal Scala code again. This can make it a lot easier to work out what’s going on.

Here’s an example that demonstrates how an asynchronous alternative to Thread.sleep can be written by using shift and reset. The call to shift inside the sleep method captures the continuation up to the end of reset. shift starts a new thread that first sleeps, then runs the continuation.

import scala.continuations.ControlContext._

object Example {
  def sleep(delay: Long) = shift { k: (Unit => Unit) =>
    val runnable = new Runnable {
      def run = {
        Thread.sleep(delay)
        k()
      }
    }
    val thread = new Thread(runnable)
    thread.start
  }
  def main(args: Array[String]) {
    println("Before reset")
    reset {
      println("Before sleep")
      sleep(2000)
      println("After sleep")
    }
    println("After reset")
  }
}

First we compile the program. We need to tell the compiler to run the new plugin.

$ $SCALA_HOME/bin/scalac -Xplugin:build/pack/selectivecps-plugin.jar -classpath build/build.library example.scala

Then we run it.

$ $SCALA_HOME/bin/scala -classpath build/build.library:. Example
Before reset
Before sleep
After reset
After sleep

Look at the output. You can see that the order of After sleep and After reset has been reversed. This is because After sleep has been captured by shift and runs later, in a different thread.

Finally, you can see exactly what the plugin has done to the program by compiling with -Xprint:selectivecps. I won’t explain the transformation here, but I do recommend you try to understand it if you’re going to do serious work with delimited continuations.

object Example {
  def sleep(delay: Long) = ControlContext.shift[Unit, Unit, Unit](((k: (Unit) => Unit) => {
    val runnable: new Runnable {
      def run: Unit = {
        Thread.sleep(delay);
        k(())
      }
    }
    val thread = new Thread(runnable);
    thread.start()
  }))
  def main(args: Array[String]): Unit = {
    println("Before reset");
    ControlContext.reset[Unit, Unit]({
      println("Before sleep");
      sleep(2000L).map[Unit](((tmp1: Unit) => {
        println("After sleep")
      }))
    })
    println("After reset")
  }
}

So that’s a simple example of using the plugin. shift and reset are extremely powerful primitives (this example doesn’t really do them justice). By supporting delimited continuations natively, Scala 2.8 will make it possible for users to extend the language in new and exciting ways.

Update: Fixed repository URL.