What are Scala continuations and why use them?

Question

I just finished Programming in Scala, and I've been looking into the changes between Scala 2.7 and 2.8. The one that seems to be the most important is the continuations plugin, but I don't understand what it's useful for or how it works. I've seen that it's good for asynchronous I/O, but I haven't been able to find out why. Some of the more popular resources on the subject are these:

• Delimited continuations and Scala
• Goto in Scala
• A Taste of 2.8: Continuations
• Delimited Continuations Explained (in Scala)

And this question on Stack Overflow:

• What are the biggest differences between Scala 2.8 and Scala 2.7?

Unfortunately, none of these references try to define what continuations are for or what the shift/reset functions are supposed to do, and I haven't found any references that do. I haven't been able to guess how any of the examples in the linked articles work (or what they do), so one way to help me out could be to go line-by-line through one of those samples. Even this simple one from the third article:

reset {
    ...
    shift { k: (Int=>Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8

Why is the result 8? That would probably help me to get started.

Answer 1

My blog does explain what reset and shift do, so you may want to read that again.

Another good source, which I also point in my blog, is the Wikipedia entry on continuation passing style. That one is, by far, the most clear on the subject, though it does not use Scala syntax, and the continuation is explicitly passed.

The paper on delimited continuations, which I link to in my blog but seems to have become broken, gives many examples of usage.

But I think the best example of the concept of delimited continuations is Scala Swarm. In it, the library stops the execution of your code at one point, and the remaining computation becomes the continuation. The library then does something -- in this case, transferring the computation to another host, and returns the result (the value of the variable which was accessed) to the computation that was stopped.

Now, you don't understand even the simple example on the Scala page, so do read my blog. In it I'm only concerned with explaining these basics, of why the result is 8.

Answer 2

I found the existing explanations to be less effective at explaining the concept than I would hope. I hope this one is clear (and correct.) I have not used continuations yet.

When a continuation function cf is called:

1. Execution skips over the rest of the shift block and begins again at the end of it
   • the parameter passed to cf is what the shift block "evaluates" to as execution continues. this can be different for every call to cf
2. Execution continues until the end of the reset block (or until a call to reset if there is no block)
   • the result of the reset block (or the parameter to reset() if there is no block) is what cf returns
3. Execution continues after cf until the end of the shift block
4. Execution skips until the end of the reset block (or a call to reset?)

So in this example, follow the letters from A to Z

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

This prints:

11
101

Answer 3

Given the canonical example from the research paper for Scala's delimited continuations, modified slightly so the function input to shift is given the name f and thus is no longer anonymous.

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

The Scala plugin transforms this example such that the computation (within the input argument of reset) starting from each shift to the invocation of reset is replaced with the function (e.g. f) input to shift.

The replaced computation is shifted (i.e. moved) into a function k. The function f inputs the function k, where k contains the replaced computation, k inputs x: Int, and the computation in k replaces shift(f) with x.

f(k) * 2
def k(x: Int): Int = x + 1

Which has the same effect as:

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

Note the type Int of the input parameter x (i.e. the type signature of k) was given by the type signature of the input parameter of f.

Another borrowed example with the conceptually equivalent abstraction, i.e. read is the function input to shift:

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

I believe this would be translated to the logical equivalent of:

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

I hope this elucidates the coherent common abstraction which was somewhat obfuscated by prior presentation of these two examples. For example, the canonical first example was presented in the research paper as an anonymous function, instead of my named f, thus it was not immediately clear to some readers that it was abstractly analogous to the read in the borrowed second example.

Thus delimited continuations create the illusion of an inversion-of-control from "you call me from outside of reset" to "I call you inside reset".

Note the return type of f is, but k is not, required to be the same as the return type of reset, i.e. f has the freedom to declare any return type for k as long as f returns the same type as reset. Ditto for read and capture (see also ENV below).

---

Delimited continuations do not implicitly invert the control of state, e.g. read and callback are not pure functions. Thus the caller can not create referentially transparent expressions and thus does not have declarative (a.k.a. transparent) control over intended imperative semantics.

We can explicitly achieve pure functions with delimited continuations.

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

I believe this would be translated to the logical equivalent of:

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

This is getting noisy, because of the explicit environment.

Tangentially note, Scala does not have Haskell's global type inference and thus as far as I know couldn't support implicit lifting to a state monad's unit (as one possible strategy for hiding the explicit environment), because Haskell's global (Hindley-Milner) type inference depends on not supporting diamond multiple virtual inheritance.