What are Scala continuations and why use them?

continuation passing style
when to use continuation passing style
continuation recursion
continuation passing style java
lisp continuation passing style
cps scala
cps lambda calculus
continuation passing style scheme

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:

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.

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.

What are Scala continuations and why use them?, There won't be any new API's for these use cases in Scala 2.8, but we expect them to emerge once the underlying continuation machinery is in� Continuations in Scala differ from those available in languages like Scheme or ML, in that Scala's continuations are composable (or "delimited"). This means that they embody not the whole rest of the program, but just a partial rest, up to a programmer-defined outer boundary. Continuations are manipulated by means of two primitives, shift and reset.

A Taste of 2.8: Continuations, that continuations in Scala are “powerful …but useless”. It's a bit like explaining how a combustion engine works, but not that it could be used� 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

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.

Continuations in Scala (without a PhD), It is now read-only. the Scala delimited continuations plugin and library which covers what was once the most common use case for the continuations plugin� Scala’s continuations are most commonly used in scala’s async library which is a way for implementing the asynchronous block of code just like Future. Currently scala is supporting the continuations but as they have stated in the news letter

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.

scala/scala-continuations: the Scala delimited , 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� Scala currently supports only delimited continuations and this is done by means of a dedicated compiler plugin. This plugin transforms specially annotated Scala methods (@cps) into the CPS form, as far as I understand.

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

Time Travel in Scala: CPS in Scala (scala's continuation)., Scala-arm can make use of delimited continuations to simplify code. an echo server that listens on a port and echos back every full line of text it receives. scala-continuations is a library and a compiler plugin for Scala language that provides support for CPS transformations. This library is community-maintained. The lead maintainer is @danslapman. You may also be interested in https://github.com/scala/async, which covers the most common use case for the continuations plugin.

ARM with Continuations -, As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a run-� scala-continuations is a library and a compiler plugin for Scala language that provides support for CPS transformations. This library is community-maintained. The lead maintainer is @danslapman. You may also be interested in https://github.com/scala/async, which covers the most common use case for the continuations plugin.

Continuation-passing style, MiniScala compiler (which is used for teaching compiler construction at one of our institutions), it suffers from two kinds of inflexibility. First, the IR does not give� What are Scala continuations and why use them? 22. Don't understand the typing of Scala's delimited continuations (A @cpsParam[B,C]) 4. nested CPS “reset”

[PDF] Compiling with Continuations, or without? Whatever., scala documentation: Continuations Library. delimiting reset block, it can be used to create functions that themselves create continuations inside a reset block . By saving the continuation we can use it as we please to 'jump back to' whatever computation followed the call/cc point. Often continuations are used for a non-local exit. Think of a function that is going to return a list unless there is some problem at which point '() will be returned.

Comments
  • scala-lang.org/api/current/…
  • I re-read your blog entry and this time I stuck with it -- I think I have a better idea of what is going on. I didn't get much from the Wikipedia page (I already know Lisp continuations) but the reset/shift deferred style or whatever its called had me stumped. For the impatient (ie myself) your description was ok but people will have to make sure to stick with it up to the "The result of reset is the result of the code inside shift." paragraph... I was hopelessly lost until that point but it does get clearer! I will have a look at Swarm because I'm still curious what this is for. Thx!
  • Yes, it does take time until things start making sense. I didn't feel I could get away making the explanation any faster.
  • It all came together for my when I came to the realization that "reset delimits the scope of the continuation. (ie: the variables and statements to be included.)
  • Your explanation was verbose and did not get to the essence of the understanding. The examples were long, I didn't get enough understanding in first paragraphs to inspire me to read it all. So I voted it down. SO displays a msg after I vote, asking me to add a comment, so I am complying. Apologies for my frankness.
  • I've blogged about this with a focus on understanding control flow (without discussing the details of the implementation). wherenullpoints.com/2014/04/scala-continuations.html
  • i've got an error saying "cannot compute type for CPS-transformed function result" when i tried to compile it.. i'm not sure what it is neither how to fix it
  • @Fabio Veronez Add a return statement to the end of the shift: change println(oneHundredOne) } to, say, println(oneHundredOne); oneHundredOne }.
  • Nice explanation for a horrible syntax. The declaration of the continuation function is strangely detached from its body. I would be reluctant to share such head-scratching code with others.
  • To avoid the cannot compute type for CPS-transformed function result error, +1 shall follow immediately after oneHundredOne}. The comments currently residing between them break the grammar somehow.
  • I am proposing that reset/shift be changed to delimit/replace. And by convention, that f and read be with, and k and callback be replaced, captured, continuation, or callback.
  • with is a keyword. P.S. Some of your resets have () which should be {} Anyway great writeup!
  • @nafg thank you, so I will propose replacement instead of with. Afaik, () is also allowed? Afaik, {} is "Scala's lightweight syntax for closures", which is hiding an underlying function call. For example, see how I rewrote Daniel's sequence (note that code was never compiled or tested, so please feel free to correct me).
  • A block -- that is, an expression containing multiple statements -- requires curly braces.
  • @nafg, correct. Afaik shift reset are library functions, not keywords. Thus {} or () can be used when the function expects only one parameter. Scala has By-name parameters (see section "9.5 Control Abstractions" of Programming in Scala, 2nd ed. pg. 218), where if the parameter is of type () => ... the () => can be eliminated. I assume Unit and not by-name because the block should evaluate before reset is invoked, but I need {} for multiple statements. My usage for shift is correct, because it obviously inputs a function type.