Scala implementation of a Non-deterministic Finite Automata (Finite State Machine), supporting ε-Transitions.

automata.scala

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(_))
	}
}