Skip to content

Instantly share code, notes, and snippets.

@ryanonsrc
Last active Jun 7, 2019
Embed
What would you like to do?
Scala implementation of a Non-deterministic Finite Automata (Finite State Machine), supporting ε-Transitions.
package io.nary.automata
// Models a transition, tied to a specific StateMachine sub-type. The guard condition is not required.
class Transition[S, M <: StateMachine[S, M]](start: S, end :S, guard: Option[M => Boolean]) {
val startState = start
val endState = end
// Given a state machine and whether a guard is expected, should we follow this transition?
def willFollow(stateMachine: M, withGuard : Boolean) =
if (!withGuard && guard == None) true;
else if(withGuard && guard == None) false;
else (withGuard && guard.get(stateMachine))
override def toString = start + "->" + end
}
// A Transition that has no guard is an Epsilon Transition
class EpsilonTransition[S, M <: StateMachine[S, M]](start: S,end :S) extends Transition[S, M](start, end, None)
// Defines an abstract state-machine which must operate within the context of its effective sub-class.
// any state for this state machine must reside within the context, as transition guards have access to this context.
abstract class StateMachine[S, M <: StateMachine[S, M]](transitions: Set[Transition[S, M]], initialStates: Set[S]) { this: M =>
private var activeStates = initialStates
private val stateDrains = transitions.groupBy(_.startState); // All transitions grouped by their starting state
// Perform state machine actions (transitions will
// be followed per the current state)
def act() = {
var entryStates = Set[S]()
var exitStates = Set[S]()
// Follow non-epsilon transitions
transitionsToFollow(activeStates, true).foreach {transition =>
exitStates += transition.startState
entryStates += transition.endState
}
// Follow epsilon transitions
entryStates = entryStates ++ transitionsToFollow(entryStates, false).map(_.endState)
// Exclude only exit states which we have not re-entered then include newly entered states
activeStates = ((activeStates -- (exitStates -- entryStates)) ++ entryStates)
}
// Start with a set of states, and map those states to a collection of transition sets, which
// is in-turn flattened. Finally we filter by transitions that we should follow (withGuard == true
// if a guard condition needs to be checked.
def transitionsToFollow(states : Set[S], withGuard : Boolean) =
states.flatMap(stateDrains.getOrElse(_, Set())).filter(_.willFollow(this, withGuard))
override def toString = activeStates.toString
}
// An example set of states
object HvacState extends Enumeration {
type HvacState = Value
val aircon, heater, fan = Value
}
import HvacState._
// A singleton containing an example set of fully defined transitions
object HvacTransitions {
val all = Set(
new EpsilonTransition[HvacState, HVac](aircon, fan),
new Transition[HvacState, HVac](aircon, fan, Some(_.temperature < 75)),
new Transition[HvacState,HVac](heater, fan, Some(_.temperature > 50)),
new Transition[HvacState, HVac](aircon, heater, Some(_.temperature < 50)),
new Transition[HvacState, HVac](heater, aircon, Some(_.temperature > 75)),
new Transition[HvacState, HVac](heater, fan, Some(_.temperature > 50)),
new Transition[HvacState, HVac](fan, heater, Some(_.temperature < 50)),
new Transition[HvacState, HVac](fan, aircon, Some(_.temperature > 75)))
}
// A sample StateMachine implementation with a single state value (temperature) and a utility
// function for changing it, invoking act() and print the resulting active states
class HVac extends StateMachine[HvacState, HVac](HvacTransitions.all, Set(heater)) {
var temperature = 40
def update(temperature : Int) = {
this.temperature = temperature
act
println(this)
}
}
object StateMachineTest {
def main(args : Array[String]) = {
val m = new HVac
println(m.toString)
// Change the temperature and see if the StateMachine is correctly updated.
List(30, 80, 60, 30, 60, 100).foreach(m.update(_))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment