concurrent-composition.kt

interface State {
    val subStates: List<State>
}

interface Event

data class Transition(val event: Event, val state: State) {
    override fun toString() = "$event -> $state"
}

fun concurrentComposition(
        syncEvents: Set<Event>,
        initialState: List<State>,
        transitions: Map<State, Set<Transition>>
): Map<State, Set<Transition>> {

    data class CompositeState(override val subStates: List<State>) : State {
        override fun toString() = "(${subStates.joinToString("||")})"
    }

    val result = mutableMapOf<State, Set<Transition>>()
    val frontier: MutableSet<State> = mutableSetOf(CompositeState(initialState))

    while (frontier.isNotEmpty()) {
        val newTransitions = mutableSetOf<Transition>()
        val state = frontier.popFirst()
        val transitionSet = state.subStates.map { transitions.getOrDefault(it, setOf()) }

        // 同期イベントによる遷移を展開する
        syncEvents.forEach { event ->
            // event での全遷移の組み合わせを追加
            transitionSet
                    .map { transitions -> transitions.filter { it.event == event }.map { it.state } }
                    .directProduct()
                    .map(::CompositeState)
                    .map { Transition(event, it) }
                    .let { newTransitions += it }
        }

        // 非同期イベントの遷移を展開する（インターリーブ）
        transitionSet
                // 同期イベント集合に含まれない遷移を対象にする
                .map { it.filterNot { transition -> syncEvents.contains(transition.event) } }
                .mapIndexed { i, asyncTransitions -> asyncTransitions.map { i to it } }
                .flatten()
                .forEach { (i, transition) ->
                    state.subStates.altered(i, transition.state)
                            .let(::CompositeState)
                            .let { Transition(transition.event, it) }
                            .let { newTransitions += it }
                }

        result[state] = result.getOrDefault(state, setOf()) + newTransitions
        frontier.addAll(newTransitions.map { it.state } - result.keys)
    }

    return result
}

fun <E> MutableCollection<E>.popFirst() = first().also { remove(it) }

fun <E> List<E>.altered(atIndex: Int, byValue: E) = take(atIndex) + byValue + drop(atIndex + 1)

fun <E> Collection<Collection<E>>.directProduct(): List<List<E>> =
        if (isEmpty()) {
            listOf()
        } else {
            val (head, rest) = first() to drop(1)
            head.map(::listOf).let {
                if (rest.isEmpty())
                    it
                else
                    rest.directProduct().flatMap { tail -> it.map { h -> h + tail } }
            }
        }

open class BaseState : State {
    override val subStates: List<State> = listOf()
}
object P0 : BaseState() { override fun toString() = "P0" }
object P1 : BaseState() { override fun toString() = "P1" }
object P2 : BaseState() { override fun toString() = "P2" }
object Q0 : BaseState() { override fun toString() = "Q0" }
object Q1 : BaseState() { override fun toString() = "Q1" }
object Q2 : BaseState() { override fun toString() = "Q2" }
object Q3 : BaseState() { override fun toString() = "Q3" }

object A : Event { override fun toString() = "a" }

concurrentComposition(setOf(A), listOf(P0, Q0), mapOf(
    P0 to setOf(Transition(A, P1), Transition(A, P2)),
    Q0 to setOf(Transition(A, Q1), Transition(A, Q2), Transition(A, Q3))
))