22. Delimited Continuation - RobertMakyla/scalaWiki GitHub Wiki

##Continuations

Key Points:

  • A continuation lets you go back to a previous point in a program.
  • You capture a continuation in a shift block.
  • A continuation function extends until the end of the enclosing reset block.
  • A continuation is the “rest of the computation” from the expression containing the shift to the end of the enclosing reset, with the shift replaced by a “hole.”
  • When you call a continuation with an argument, the “hole” is set to the argument.
  • Code containing shift expressions is rewritten in “continuation-passing style” (CPS), up to the enclosing reset.
  • A method containing a shift without a reset must be annotated with a CPS annotation.
  • Continuations can be used to turn a recursive visit of a tree structure into an iteration.
  • Continuations can undo the “inversion of control” in a web or GUI application.

Wiki definition

(https://en.wikipedia.org/wiki/Continuation-passing_style)

A function written in continuation-passing style CPS takes an extra argument: an explicit "continuation" i.e. a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument.

That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value. Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply call a procedure with the same continuation, unmodified, that was passed to the caller.

In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming.

##StackOverflow example

def f(k: Int => Int): Int = k(100)
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 end 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(100) * 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.

##Control Flow

var cont : (Unit => Unit) = null
reset {
  println("Before shift")
  shift {
    k: (Unit => Unit) => {
      cont = k
      println("Inside shift") // Jumps to end of reset
    }
  }
  println("After shift")
}
println("After reset")
cont()

If I call reset, it's body executes:

Before shift
Inside shift
After Reset

If I call shift, it's body is called with continuation function (cf) as argument. When shift completes, it goes to the end of reset

Before shift
Inside shift
After Reset

##The Value of a reset Expression

If the block of a reset exits because a shift is executed, then the value is the value of the shift block:

val res = reset { shift { k: (String => String) => "Exit" }; "End" }
// res is "Exit"

However, if the reset expression comes to its end, then the value of the reset is simply the value of the block—that is, the value of the last expression in the block:

val res = reset { if (false) shift { k: (String => String) => "Exit" }; "End" }
// res is "End"

In practice, either of the two may happen if the reset block contains a branch or loop:

val res = reset {
    if (scala.util.Random.nextBoolean()) {
        shift { k: (String => String) => "Exit" }
    }
    else "End"
}

In this case, result is randomly assigned "Exit" or "End".