First class coroutine continuations?


#1

Hi, I’m trying to implement a simple inference engine for stochastic programming using the new coroutine support, à la webppl. I need to be able to call resume on continuations multiple times (each time certain suspended functions are called), which is not currently supported. The documentation states:

However, first-class continuations can be implemented as a separate library by cloning the state of the coroutine that is captured in continuation, so that its clone can be resumed again. This mechanism may be efficiently provided by the standard library in the future.

Is there an example I can follow for this? CoroutineImpl and other related classes have private state that I don’t know how to clone. How much of the existing library do I need to duplicate & tweak to get it working? Does this require modifying the compiler? I did try calling suspendCoroutineOrReturn multiple times in a suspension to create multiple continuations, but the way CoroutineImpl currently works leads to some very very strange results…

Thanks!
-cj


#2

The is no easy-way to resume coroutine multiple times, as it involves copying its full state and you must make all the non-trivial decision on what part of its state really needs copying. However, let me quote a great paper “Resivisiting Coroutines” by Moura and Ierusalimschy (you can find it here http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf):

The observation that in most contexts continuations are actually invoked only once motivated Bruggeman et al. [1996] to introduce one-shot continuations, which are limited to a single invocation and thus eliminate the copying overhead associated with multi-shot continuations. One-shot continuations can replace multi-shot continuations in practically all their useful applications.

In particular, use-case like “inteference engine” seem to express themselves quite nicely with one-shot continuations. For example, the above paper gives an example on how to implement a parser (with backtracking) using one-short continuations. This is the kind of thing typically implemented in pure languages with full-blown continuations, but there is no actual need to have them, because you can create new coroutines at the backtracking points instead.


#3

Let me be a bit more concrete – I would like to support the following syntax:

infer(method="enumerate") { if flip() 1 else if flip() 2 else 3 }

The behavior of the enumeration inference method is to explore all possible executions of the program; in this case, the possible return values of true or false for each invocation of flip (a suspending function). The end result would be a distribution mapping 1 to 0.5, 2 to 0.25, and 3 to 0.25. flip could have been implemented by calling its continuation multiple times if multi-shots were allowed.

The approach given by the paper’s parser example relies on lifting patterns to generators and using special combinators… kind of like LINQ syntax. That approach does work to implement an inference engine, but it is not the webppl-like abstraction above that I was hoping to get by using Kotlin’s coroutines.


#4

It could be made to work by manually implementing multi-shot continuations by cloning state. Take a look at the example in this gist: https://gist.github.com/elizarov/ddee47f927dda500dc493e945128d661 It implements the crude approach to cloning coroutine state and show-cases that by using it to compute various outcomes and probabilities of a non-deterministic computation that uses discrete random variables. The end result is that the following code:

enumerate { if (flip("A")) 1 else if (flip("B")) 2 else 3 }

when given a definition of a flip function that simulates a flip of a fair coin with name (for ease of debugging):

suspend fun Distribution.flip(name: String): Boolean = variable(name) {
    it.yield(0.5, true)
    it.yield(0.5, false)
}

Produces the following output:

value = 1 with probability=0.5 for variables={A=true}
value = 2 with probability=0.25 for variables={A=false, B=true}
value = 3 with probability=0.25 for variables={A=false, B=false}

However, this approach, while could be considered a great showcase, is not easy to generalize. The key difficulty is to figure out how deep the state shall be cloned. It works well with a shallow clone for this example, but it will fail with a more complex code. The underlying conceptual problem is that Kotlin is an imperative non-pure language (with mutable data). Mutli-shot continuations do not work well without purity. They do fit nicely in pure languages and even better in lazily evaluated pure languages (like Haskell).


#5

Thank you!!! I got it to work with nested calls to suspend by tweaking clone to recursively clone any Continuation<*> field it finds and keeping a map of cloned objects to prevent cycles. This should be enough for my prototyping…