A Taste of 2.8: Continuations

Tiark, it seems continuations are too obvious to you for you to chose good examples. :-) From your paper, the following two examples are far superior in getting the point accross:

 

reset {
  shift { k: (Int=>Int) =>
    k(k(k(7)))
  } + 1
} * 2 // result 20 

and

def foo() = {
  1 + shift(k => k(k(k(7))))
}
def bar() = {
  foo() * 2
}
def baz() = {
  reset(bar())
}
baz()  // result 70

 

Though my favorite example is 4.2. Only I can't wrap my head around it yet.

 

hi,

 

thanks for providing the "glimpse". i agree with the previous comment, i find it very hard to grasp how the whole thing works. can you explain the timertask example? what is it doing exactly, and why is the result that no threads are used?

This makes about zero sense.  I just spent some time on Wikipedia as well as a few other places to try to understand this.  From my perspective, these are convoluted ways of adding numbers and I have no idea what is being gained or accomplished.

 

Is there an actual use for this construct that you can explain to demonstrate how this makes code easier to read/write/maintain? 

 

Similar to the previous repliers, i also don't quite understand what's the use of all this.

Beaten with this kind of uncurable ignorance, i ask myself:

 

What kinds of problems are solved by continuations?

 

All the examples on http://en.wikipedia.org/wiki/Continuation and http://en.wikipedia.org/wiki/Continuation-passing_style seem to present way more complex solutions for problems that can be solved quite simply.

 

I guess what is missing here, are real good examples for problems solved by continuations.

Hi,

maybe somebody can post very simple example using println( "hello1" ), println( "hello2" ) ... to see how control flow goes ?

Thanks, Arthur.

Assume such use case (in scala-like pseudocode)

class My(array: Array[String]) {
    def next : String = for (s <- array) yield return s
}
val my = new My(Array("One", "Two", "Three"))
assert my.next == "One"
assert my.next == "Two"
assert my.next == "Three"

How this can be correctly formulated using Scala 2.8 continuation facility?

I do some continuation-passing style programming in the implementation of VeriFast, my program verifier prototype. It's written in O'Caml. It uses symbolic execution. The verification process forks at each conditional construct. Here's a simplified fragment:

let ($.) f x = f x
let rec verify_stmt h s c k =
  match c with
  | Call (f, args) =>
    eval_exprs h s args $. fun h values =>
    let (params, pre, post) = lookup_function f in
    let s' = zip params values in
    consume h s' pre $. fun h s' =>
    produce h s' post $. fun h _ =>
    k h s
  | If (cond, c1, c2) =>
    eval h s cond $. fun h value =>
    assume value (fun () => verify_stmt h s c1 k);
    assume (Not value) (fun () => verify_stmt h s c2 k)
let verify_function f params pre post body =
  let s = map (fun x => (x, fresh_symbol x)) params in
  let h = [] in
  produce h s pre $. fun h s =>
  verify_stmt h s body $. fun h _ =>
  consume h s post $. fun _ _ =>
  ()

By taking a continuation als the last argument, and by using a function application infix operator $., you can do sequential composition of CPS functions without an accumulation of braces or parentheses. Unfortunately, in Scala, lambda expressions cannot appear as infix operator arguments (without parentheses or braces), so you cannot do this in Scala.

If I understand correctly, the Scala version with shift-reset would look something like this:

def caseSplit[T](v: Term, branch1: => T, branch2: => T): T = {
  shift { k =>
    assume(v, k(branch1))
    assume(Not(v), k(branch2))
  }
}

def verifyStmt(h: Heap, s: Store, c: Command): (Heap, Store) = {
  c match {
    case Call(f, args) =>
      val (h0, values) = evalExprs(h, s, args)
      val (params, pre, post) = lookupFunction(f)
      val s0 = params zip values
      val (h1, s1) = consume(h0, s0, pre)
      val (h2, _) = produce(h1, s1, post)
      (h2, s)
    case If(cond, c1, c2) =>
      val (h0, value) = eval(h, s, cond)
      caseSplit(value, verifyStmt(h0, s, c1), verifyStmt(h0, s, c2))
  }
}

def verifyFunction(f: String, params: List[String], pre: Assertion, post: Assertion,
                   body: Command) {
  val s = params map (x => (x, freshSymbol(x)))
  val h = emptyHeap
  reset {
    val (h1, s1) = produce(h, s, pre)
    val (h2, _) = verifyStmt(h1, s1, body)
    consume(h2, s1, post)
  }
}

It's a bit of a pain that I can't redefine locals, but apart from that the Scala version is at least as clean as the O'Caml version.

Maybe someone could explain how continuations would be useful in combination with NIO through a simple example?

 

Hello, I'm a miscellaneous software developer out in the world, and I must add my voice to those clamoring about how confusing this article is.  :)

 

I think I would get it if I studied several of the examples at length.  A previous commenter says, "Contionuations makes complex thing possible, but one cannot expect simple thing easy, an tool to be used with care"--suggesting that it's not even possible to explain continuations to a neophyte in a way that doesn't require lengthy study!

 

But I learned about continuations in C#, which has a yield keyword that works as in another commenter's pseudocode:

class My(array: Array[String]) {
    def next : String = for (s <- array) yield return s
}
val my = new My(Array("One", "Two", "Three"))
assert my.next == "One"
assert my.next == "Two"
assert my.next == "Three"

 

In that example, the task being accomplished through the use of continuations is indeed simple, and it's also easy to understand:  It is the direct transformation of a "for" loop into something very similar to an Iterable.  This is just the sort of thing I did in C#, and when I'm working in Java, it's something I often wish I could do.  Here's the crux of it:  If you're calculating a bunch of things in sequence, via a loop or really in any old way, you can (in C#, according to my limited understanding) use this "yield" mechanism to make your loop stop at each step, and return the last value it calculated (as if you'd broken the loop via a return statement), while the rest of the loop, which is yet to be run, is still invisibly remembered somehow, so that the next time you ask for a value, it can start up again...  until it hits its next yield statement, at which time it returns its next value.

 

The simple way to transform a "for" loop into an iterable thing, in Java, is to make an ArrayList before you start your loop, and add the result of each loop iteration to the list.  Sometimes this is great.  But sometimes it's crazily stupid--for instance, when the number of iterations is very large and the result produced by each iteration takes up lots of memory.  Then, you wouldn't want to calculate every value, and store it in memory, before starting your iteration.  But you might still want to use the nice syntax for iterating over Iterables.  A C#-like "yield" keyword would allow this easily.  Study the examples above and you will probably figure out how to do a similar thing in Scala.  :)

 

(I don't mean to say that this idea of interrupting a loop to iterate over its results from outside is the only important aspect or use of continuations--it's just the one that's easy for me to understand.)

I wanted to post an example of continuations used on Android because the Android API (which is in Java) relies so heavily on asynchronous callbacks.

Callbacks tend to be harder to understand than synchronously blocking code because they force you to split logically sequential code into two chunks of non-contiguous code -- the code that makes the request, and the callback code. Continuations make it possible to express those two chunks as one contiguous chunk, hopefully making the code easier to understand (once you get your head around continuations). So I'm thinking continuations will be very useful on Android.

The callback in this example involves Android's TextToSpeech class. When you create an instance of TextToSpeech, it is not yet initialized, so you provide a callback that is called when the TextToSpeech is actually initialized. (No comment.)

Before we get to the example itself, here's a method it will use to build the required callback/listener object from a bit of code that will be turn out to be provided by a continuation:

  private def asInitListener(bodyOfListener:Unit=>Any) =
    new OnInitListener(){ override def onInit(ignored:Int){ bodyOfListener() } }

Now the example, a code fragment that creates a TextToSpeech and (later, after the TextToSpeech is initialized) uses it:

    reset{
      shift{ (continuation:Unit=>Any) =>
        textSpeaker = new TextToSpeech(..., asInitListener(continuation))
      }
      textSpeaker.speak("NOW textSpeaker is definitely initialized.", ...)
    }

Same example with some added comments about the continuation and what is happening when:

    reset{
      shift{ (continuation:Unit=>Any) =>
        textSpeaker = new TextToSpeech(..., asInitListener(continuation))
        // Can't use textSpeaker here -- it may not be initialized yet.
      }
      // The following line of code will be the continuation
      // that will be used to build the callback object.
      // It will not get executed in sequence here;
      // it will instead get executed when the callback object is called.
      textSpeaker.speak("NOW textSpeaker is definitely initialized.", ...)
    }
    // Can't use textSpeaker here -- it may not be initialized yet. 

I have to admit the above code is still hard for me to understand. However, if I'm interpreting this article correctly, reset and shift should be thought of as primitives that can be used in higher-level constructs that are more tailored to specific use cases.

Also, part of what makes this code awkward is interfacing with a Java API. Imagine if Android had a Scala API, taking advantage of Scala features like continuations wherever appropriate.

Mark

I think I am missing some small detail.  What is it?

$ scala -P:continuations:enable
Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).
Type in expressions to have them evaluated.
Type :help for more information.
 
scala> import scala.util.continuations._                                     
import scala.util.continuations._
 
scala> def foo() = { shift { k: (Int => Int) => k(7) } }                     
<console>:2: error: type mismatch;
 found   : Int @scala.util.continuations.cpsSynth @scala.util.continuations.cpsParam[Int,Int]
 required: Int
object RequestResult$line2$object {

Based on this article, I expected foo to be a function that I could invoke inside reset, but it seems I need to both define and invoke foo within the scope of the same reset.  What am I missing or misunderstanding? Thanks, Topher.

 

       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.