6
\$\begingroup\$

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 => { S1 }
       case E1 => { S0 }
       case E2 => { S2 } } } }

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

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

 object S3 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S0 }
       case E1 => { S3 }
       case E2 => { 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ If you look for alternative implementations, Akka has an interesting FSM implementation (with actors, of course, but it is easy to reduce it without them, I did that for a lightweight program). \$\endgroup\$ – PhiLho Sep 7 '11 at 20:15
  • \$\begingroup\$ Wow, thank you very much, interesting. Akka is one of the reasons why I decided to learn Scala. I shall look at the Akka FSM in detail when mygrasp of Scala is more firm. \$\endgroup\$ – Martin Berger Sep 9 '11 at 10:59
3
\$\begingroup\$

Looks fine to me. You don't need so much parens:

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

But in this easy example I would use a Map to encode the transition rules (corrected):

sealed abstract class State {
  def m: Map[Event, State]
  def event ( e : Event ) : State = m(e)
}

object S0 extends State{ lazy val m = Map[Event, State](E0 -> S1, E1 -> S0, E2 -> S3) }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you, very interesting, and much simpler than my proposal, but when I compile it, I get "error: super constructor cannot be passed a self reference unless parameter is declared by-name". \$\endgroup\$ – Martin Berger Sep 6 '11 at 10:56
  • 1
    \$\begingroup\$ Sorry, I corrected my example. I overlooked that we have cyclic dependencies when constructing S0..S3. The easiest way to deal with this is using a lazy val. \$\endgroup\$ – Landei Sep 6 '11 at 12:12
  • \$\begingroup\$ Thanks, your program compiles now without modification. I wonder why though, as S1, S3, E0, E1 and E2 are undefined. My type-theoretic intuition tells me this should not type-check. Clearly, I still have a lot to learn about Scala. \$\endgroup\$ – Martin Berger Sep 6 '11 at 12:41
  • \$\begingroup\$ Of course you need the rest of the definitions as well. I guess the other class files are still there from your previous build. \$\endgroup\$ – Landei Sep 6 '11 at 20:19
  • \$\begingroup\$ Interesting. So you are saying that whether a Scala program type-checks or not does not just depend on the program but also on what kind of other files are around (without explicit imports)? That's rather surprising to me. \$\endgroup\$ – Martin Berger Sep 7 '11 at 8:02
4
\$\begingroup\$

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 => s1; case E1 => s2; case E2 => s0 }
  private val ( s1 : State ) = transitions { case E0 => s3; case E1 => s0; case E2 => s1 }
  private val ( s2 : State ) = transitions { case E0 => s2; case E1 => s1; case E2 => s0 }
  private val ( s3 : State ) = transitions { case E0 => s3; case E1 => s3; case E2 => 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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

A better way to implement your FSM is to use our company open source FSM implementation. It's strongly typed and invalid transitions won't compile. Your code will look some what like this:

// States
case object S0 extends State
case object S1 extends State
case object S2 extends State
case object S3 extends State

// Inputs
case object E0 extends Input
case object E1 extends Input
case object E2 extends Input

// Transitions
implicit val tS0S1 = Transition[S0.type, E0.type, S1.type]((_, _) => S1)
// more transitions

// State machine
Fsm(S0).transition(E0) // return Fsm(S1)
Fsm(S0).transition(E0).transition(E1).transition(E2) // return Fsm(S3)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.