General Finite State Machine (Transducer) in Scala

Question

What is the general way to implement a finite state machine (or finite state transducer) in Scala?

I often find myself in need for state machine implementation. My typical implementation looks like

object TypicalFSM { // actually — finite state transducer
  type State
  case object State1 extends State
  case object State2 extends State
  type Message
  case object Message1 extends Message
  type ResultMessage
  case object ResultMessage1 extends ResultMessage
}

import TypicalFSM._

class TypicalFSM extends ((Message) =>Seq[ResultMessage]){
  var state:State = State1

  def apply(message:Message):Seq[ResultMessage] = (state, message) match {
    case (State1, Message1) =>
      state = State2
      Seq(ResultMessage1, ResultMessage2)
  }
}

What I dislike is the mutable var which makes the solution thread unsafe. Also the FSM topology is not clear.

1. How to create FSMs in a functional way?

2. It also would be very good to draw FSM-graph in .dot format

3. Akka FSM has a good property of allowing to associate some Data with a State, not only giving an object name. This is also appreciated. (However, Akka FSM is not always convenient to use as it is asynchronous and sometimes a bit heavy-weight.)

Siskin

FSMs can be beautiful when expressed as mutually recursive functions. Real tail calls are key there, though, so Scala won't cut it. To avoid your var, just return the next state along with the messages, and keep feeding the function into itself. You're effectively constructing the State type. – Foreground

The Akka framework has a useful state machine implementation, but it is rather dependent on sending messages around an actor system. You can read more here – Felizio

Yeah, I can also say, Akka Finite State Machine is the best I know in Scala world, you can see the documentation here doc.akka.io/docs/akka/current/typed/fsm.html, if you want to see implementation example, I have a blog for it mehmetsalgar.wordpress.com/2022/04/18/… mehmetsalgar.wordpress.com/2022/05/17/… – Ferrocyanide

Answer 1

This is probably not what you are looking for, but I think it's an interesting concept.

object TypicalFSM {

  sealed trait State
  final class State1 extends State
  final class State2 extends State

  sealed trait Message
  case class Message1(s: String) extends Message
  case class Message2(s: String) extends Message

  sealed trait ResultMessage
  object ResultMessage1 extends ResultMessage
  object ResultMessage2 extends ResultMessage
}

import TypicalFSM._

case class Transformation[M <: Message, From <: State, To <: State](
    f:M => Seq[ResultMessage]) {

  def apply(m:M) = f(m)
}

object Transformation {

  implicit def `message1 in state1` =
    Transformation[Message1, State1, State2] { m =>
      Seq(ResultMessage1, ResultMessage2)
    }

  implicit def `message1 in state2` =
    Transformation[Message1, State2, State2] { m =>
      Seq(ResultMessage1)
    }

  implicit def `message2 in state2` =
    Transformation[Message2, State2, State1] { m =>
      Seq(ResultMessage2)
    }
}

class TypicalFSM[CurrentState <: State] {

  def apply[M <: Message, NewState <: State](message: M)(
    implicit transformWith: Transformation[M, CurrentState, NewState]) = {

    this.asInstanceOf[TypicalFSM[NewState]] -> transformWith(message)
  }
}

Usage would be like this:

def test() = {
  val s1 = new TypicalFSM[State1]
  // type of s1: TypicalFSM[State1]

  val (s2, r1) = s1(Message1("m1"))
  // type of s2: TypicalFSM[State2]

  val (s3, r2) = s2(Message1("m1"))
  // type of s2: TypicalFSM[State2]

  val (s4, r3) = s2(Message2("m2"))
  // type of s2: TypicalFSM[State1]

  // val (s5, r4) = s4(Message2("m2"))
  // Fails with:
  // 'No transformation available for TypicalFSM.Message2 in TypicalFSM.State1'
  // type of s5: TypicalFSM[State1]
}

Your use case would strongly determine the structure of the code in this concept. The use case really determines how much type information you want to keep.

I this concept because the state is kept using the type system and that illegal transitions are reported at compile-time.

Hasdrubal

Interesting approach. Strictly typed states. However, I think that signature of Transformation should be: case class Transformation[M <: Message, From <: State, To <: State]( f:M => (To, ResultMessage)) – Siskin

@ArseniyZhizhelev I agree, I just followed your example. Theoretically you could bind the type of output to the type of message. Really depends on the use case how far you want to go with types in Scala, haha. – Hasdrubal

Very interesting... but once I get back s1 or whatever else state, how do I check it? Let's assume a method like this: def typeOf[T: TypeTag](t: T) = reflect.runtime.universe.typeOf[T], who do I determine the state/response returned by TypicalFSM so that I can take an action? typeOf(s1) match { ??? } – Officiary