Copying and storing coroutine continuations for systematic analysis of behavioral programs

[jgreenyer]

Hi everyone,
I used Kotlin to implement a variant of the Behavioral Programming paradigm (
http://www.wisdom.weizmann.ac.il/~bprogram/). In a nutshell, a behavioral program consists of loosely coupled threads (or “scenarios”) that can each do their work, and regularly synchronize via requesting, waiting for, or blocking events. A central event selection mechanism repeatedly selects and executes events that are requested by some scenario, and are blocked by another. I found that this paradigm can be nicely implemented using Kotlin’s coroutines and channels. I provide a ~100 LOC minimal example in this gist; it does not implement the concept of blocking events in order to keep it simple for the purpose of the question coming below.

In the example, you see that there are three scenarios:

fun main() {

    val requestTwoAs: suspend Scenario.() -> Unit = {
        sync(setOf(A), setOf())
        sync(setOf(A), setOf())
    }
    val requestTwoBs: suspend Scenario.() -> Unit = {
        sync(setOf(B), setOf())
        sync(setOf(B), setOf())
    }
    val waitForABAB: suspend Scenario.() -> Unit = {
        sync(setOf(), setOf(A))
        sync(setOf(), setOf(B))
        sync(setOf(), setOf(A))
        sync(setOf(), setOf(B))
        println("success")
    }

    runBlocking {
        launch {
            ScenarioProgram(setOf(requestTwoAs, requestTwoBs, waitForABAB)).run()
        }
    }
}

Depending on the event selection, there are different possible executions (ABAB, BABA, AABB, BBAA), where ABAB is one that leads to “success” being printed.

I’m looking for a way to systematically explore the different executions that are possible for such programs, e.g., find which ones lead to success or failure.

There should be a way to grab a hold of each scenario’s continuation when they reach the sync point – the synch method is quite simple: send requested and waited-for events to the main program, and await notification by the main program about the event selected

suspend fun sync(requestedEvents: Collection<Event>, waitedForEvents: Collection<Event>): Event {
    syncChannel.send(SyncMessage(this, requestedEvents, waitedForEvents))
    return notifyOfEventChannel.receive()
}

Once I obtain all scenario continuations, it I’d have to store and copy them, for example, in order to do backtracking over possible executions.

I found something that may be related in this post here:

First class coroutine continuations?

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 continuat…

But, I can’t get my head around how to do it…

he first step, IMO, is to grab each the scenario’s continuation as they perform syncChannel.send, and then pass the continuation as part of the SyncMessage – but how can I do that?

Does anyone have any clues?

Thanks,
Joel