Tuesday, February 24, 2009

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.

11 comments:

dru said...

This delimited continuations stuff is very cool. It would be good to post a sample of how this would be used in OTP. BTW, you need a better contact page, i wanted to email you, but couldn't find your contact info anywhere. cheers.

Rich Dougherty said...

@dru: You can see a lot of fun async IO stuff over at my Github account. And I've updated my profile to include my email address, hope this helps.

Mushtaq said...

I am trying to understand why do we need reset. Can I use sleep outside reset something like:

def main...{
sleep(2000) {
println("After sleep")
}
}

Rich Dougherty said...

@Mushtaq: The reset is what makes the continuation "delimited", rather than a normal continuation.

A normal continuation, captured with call/cc, contains the entirety of the rest of the computation. A delimited continuation, captured with shift, contains the computation only up until the enclosing reset.

On a practical level, the Scala compiler uses the reset to mark the boundary of the code that needs to be translated into continuation-passing style.

Mushtaq said...

Oh ok. Does it mean that, in your example, sleep can only see the scope delimited by reset? Can we do:

def main...{
val a = 50
val b = "outer"
reset {
sleep(a) {
println("After sleep " + outer)
}
}

Rich Dougherty said...

Yes, it would only see the bit surrounded by a reset.

BTW, you don't need to use the { and } after the sleep. What you're doing there is manually passing a function for sleep to call. This will automatically happen anyway when the code inside the reset is converted into continuation-passing style.

def main...{
val a = 50
val b = "outer"
reset {
sleep(a)
println("After sleep " + outer)
}

sanity said...

Hmm, currently this doesn't seem to build - bug reported here: https://lampsvn.epfl.ch/trac/scala/ticket/2231

monisa said...

we are 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.

Rich Dougherty said...

@monisa: That sounds like an exciting project! Unfortunately I probably won't be able to help as it sounds like a big job.

greenhorn said...

the first link of the forum entry has been deleted. Why? Also, I found it hard to find information about this compiler plugin, scala api doesn't really help here (scala / util/ continuations).

here is some info:
http://stackoverflow.com/questions/1512930/what-are-scala-continuations-and-why-use-them

and

http://stackoverflow.com/questions/2683195/how-do-i-enable-continuations-on-scala-2-8

Rich Dougherty said...

@greenhorn: I agree documentation can be hard to find. Your second link will be useful for people who want to use the plugin now that it's included in Scala.

Not sure why the forum link is gone.