What are Scala continuations and why use them?

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.

---

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:

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 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 Execution continues after cf until the end of the shift block 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

---

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.

---

Continuation capture the state of a computation, to be invoked later.

Think of the computation between leaving the shift expression and leaving the reset expression as a function. Inside the shift expression this function is called k, it is the continuation. You can pass it around, invoke it later, even more than once.

I think the value returned by the reset expression is the value of the expression inside the shift expression after the =>, but about this I'm not quite sure.

So with continuations you can wrap up a rather arbitrary and non-local piece of code in a function. This can be used to implement non-standard control flow, such as coroutining or backtracking.

So continuations should be used on a system level. Sprinkling them through your application code would be a sure recipe for nightmares, much worse than the worst spaghetti code using goto could ever be.

Disclaimer: I have no in depth understanding of continuations in Scala, I just inferred it from looking at the examples and knowing continuations from Scheme.

---

From my point of view, the best explanation was given here: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

One of examples:

To see the control flow a little more clearly, you can execute this code snippet:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

Here's the output the above code produces:

A
B
D
E
G
F
C

---

Another (more recent -- May 2016) article on Scala continuations is:
"Time Travel in Scala: CPS in Scala (scala’s continuation)" by Shivansh Srivastava (shiv4nsh).
It also refers to Jim McBeath's article mentioned in Dmitry Bespalov's answer.

But before that, it describes Continuations like so:

A continuation is an abstract representation of the control state of a computer program. So what it actually means is that it is a data structure that represents the computational process at a given point in the process’s execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. To explain it further we can have one of the most classic example, Say you’re in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there’s a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :-) In this description, the sandwich is part of the program data (e.g., an object on the heap), and rather than calling a “make sandwich” routine and then returning, the person called a “make sandwich with current continuation” routine, which creates the sandwich and then continues where execution left off.

That being said, as announced in April 2014 for Scala 2.11.0-RC1

We are looking for maintainers to take over the following modules: scala-swing, scala-continuations. 2.12 will not include them if no new maintainer is found. We will likely keep maintaining the other modules (scala-xml, scala-parser-combinators), but help is still greatly appreciated.

---

Scala Continuations via Meaningful Examples

Let us define from0to10 that expresses the idea of iteration from 0 to 10:

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

Now,

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

prints:

0 1 2 3 4 5 6 7 8 9 10 

In fact, we do not need x:

reset {
  print(s"${from0to10()} ")
}
println()

prints the same result.

And

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

prints all pairs:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

Now, how does that work?

There is the called code, from0to10, and the calling code. In this case, it is the block that follows reset. One of the parameters passed to the called code is a return address that shows what part of the calling code has not yet been executed (**). That part of the calling code is the continuation. The called code can do with that parameter whatever it decides to: pass control to it, or ignore, or call it multiple times. Here from0to10 calls that continuation for each integer in the range 0..10.

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

But where does the continuation end? This is important because the last return from the continuation returns control to the called code, from0to10. In Scala, it ends where the reset block ends (*).

Now, we see that the continuation is declared as cont: Int => Unit. Why? We invoke from0to10 as val x = from0to10(), and Int is the type of value that goes to x. Unit means that the block after reset must return no value (otherwise there will be a type error). In general, there are 4 type signatures: function input, continuation input, continuation result, function result. All four must match the invocation context.

Above, we printed pairs of values. Let us print the multiplication table. But how do we output \n after each row?

The function back lets us specify what must be done when control returns back, from the continuation to the code that called it.

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

back first calls its continuation, and then performs the action.

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

It prints:

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

Well, now it's time for some brain-twisters. There are two invocations of from0to10. What is the continuation for the first from0to10? It follows the invocation of from0to10 in the binary code, but in the source code it also includes the assignment statement val i =. It ends where the reset block ends, but the end of the reset block does not return control to the first from0to10. The end of the reset block returns control to the 2nd from0to10, that in turn eventually returns control to back, and it is back that returns control to the first invocation of from0to10. When the first (yes! 1st!) from0to10 exits, the whole reset block is exited.

Such method of returning control back is called backtracking, it is a very old technique, known at least from the times of Prolog and AI-oriented Lisp derivatives.

The names reset and shift are misnomers. These names should better have been left for the bitwise operations. reset defines continuation boundaries, and shift takes a continuation from the call stack.

Note(s)

(*) In Scala, the continuation ends where the reset block ends. Another possible approach would be to let it end where the function ends.

(**) One of the parameters of the called code is a return address that shows what part of the calling code has not yet been executed. Well, in Scala, a sequence of return addresses is used for that. How many? All of the return addresses placed on the call stack since entering the reset block.

UPD Part 2 Discarding Continuations: Filtering

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

This prints:

0 2 4 6 8 10 

Let us factor out two important operations: discarding the continuation (fail()) and passing control on to it (succ()):

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

Both versions of succ() (above) work. It turns out that shift has a funny signature, and although succ() does nothing, it must have that signature for type balance.

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

as expected, it prints

0 2 4 6 8 10

Within a function, succ() is not necessary:

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

again, it prints

0 2 4 6 8 10

Now, let us define onOdd() via onEven():

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

Above, if x is even, an exception is thrown and the continuation is not called; if x is odd, the exception is not thrown and the continuation is called. The above code prints:

1 3 5 7 9 

---