FSA (finite state automaton) in Scala I'm a beginning Scala programmer with a strong background in functional programming (ML, Haskell, Scheme) and I've just written my first Scala program. It is an implementation of a FSA (finite state automaton). Below is a simplified version that has 3 events/actions/labels (E0, E1, E2) and four states (S0, S1, S2, S3).

 sealed abstract class Event

 case object E0 extends Event
 case object E1 extends Event
 case object E2 extends Event

 abstract class State { def event ( e : Event ) : State }

 object S0 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 =&gt; { S1 }
       case E1 =&gt; { S0 }
       case E2 =&gt; { S2 } } } }

 object S1 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 =&gt; { S1 }
       case E1 =&gt; { S2 }
       case E2 =&gt; { S0 } } } }

 object S2 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 =&gt; { S2 }
       case E1 =&gt; { S0 }
       case E2 =&gt; { S3 } } } }

 object S3 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 =&gt; { S0 }
       case E1 =&gt; { S3 }
       case E2 =&gt; { S3 } } } }

 class Fsa {
   private var state : State = S0
   def event ( e : Event ) : Unit = { state = state.event ( e ) } }


A typical use of Fsa objects would be like this:

val fsa = new Fsa
while ( true ) {
   fsa.event ( ... nextEvent () ) }


I'd be interested to know if you think this is a good, or at least reasonable way
of implmenting FSAs in Scala, and if not, why. I'm particularly interested in the memory consumption of solutions like this.
Following suggestions from Landei above, and this article on recursive type declarations in Scala, I've come up with a slightly different solution where states are directly modelled as state transitions.

trait StateFunc [ T ] extends PartialFunction [ T, StateFunc [ T ] ]

sealed abstract class Event

case object E0 extends Event
case object E1 extends Event
case object E2 extends Event

class FSA {
  private type State = StateFunc [ Event ]

  private def transitions [ T ] ( pf : PartialFunction [ T, StateFunc [ T ] ] ) = new StateFunc [ T ] {
    def apply( event : T ) = pf ( event )
    def isDefinedAt ( event : T ) = pf.isDefinedAt ( event ) }

  private val ( s0 : State ) = transitions { case E0 =&gt; s1; case E1 =&gt; s2; case E2 =&gt; s0 }
  private val ( s1 : State ) = transitions { case E0 =&gt; s3; case E1 =&gt; s0; case E2 =&gt; s1 }
  private val ( s2 : State ) = transitions { case E0 =&gt; s2; case E1 =&gt; s1; case E2 =&gt; s0 }
  private val ( s3 : State ) = transitions { case E0 =&gt; s3; case E1 =&gt; s3; case E2 =&gt; s1 }

  private var state = s0

  def handle ( e : Event ) { state = state ( e ) } }


I'm not saying that this is better than the other solutions proposed, but I wonder about memory usage. Clearly, as this is a highly recursive construct, if the compiler doesn't do tail-call optimisation, this solution will run out of memory eventually. I have no understanding of the Scala compiler, but I would imagine that in this simple case the tail calls are optimised to ensure constant stack space usage. But what if the transition functions do something more complicated (e.g. possibly throwing exceptions)? Can constant space usage still be guaranteed?

As an aside, is it really necessary to go through so many hoops to define a recursive type? Why can I not simply write e.g. type T = Map [ Int, T ]?

Edit 9.9.2011: I added @tailrec annotations to the program above with the following results: The compiler accepts @tailrec on s0, ..., s3 just fine. But it balks when I annotate the private definition of transitions, which is not surprising. What that means in practise for stack-space usage of this form of implementing FSAs I don't know.