Finite State Machine and inter-FSM signaling

Question

Recommendations for languages with native (so no FSM generation tools) support for state machine development and execution and passing of messages/signals. This is for telecoms, e.g implementation of FSMs of this level of complexity.

I have considered Erlang, but would love some feedback, suggestions, pointer to tutorials, alternatives, particularly Java based frameworks. Maybe Scala?

Open source only. I'm not looking for UML or regular expression related solutions.

As this is for the implementation of telecoms protocols the FSMs may be non-trivial. Many states, many transitions, signal based, input constraints/guards. Dynamic instantiation would be a plus. Switch statements are out of the question, it quickly nests to unusable. It's barely better that if/else.

I would prefer to not depend on graphical design; the format FSM description should be human readable/editable/manageable.

--

I have decided to focus on an Actor based solution for C++

For example, the Theron framework provides a starting point http://theron.ashtonmason.net/ and to avoid switch statements in the FSM based event handler this C++ FSM Template Framework looks useful http://satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

FSM should be trivial to implement in any language that has a case statement.Your choice of language should be based on what that finite state machine needs to do.

For example, you state that you need to do this for telecom development and mention messages. I would look at systems/languages that support distributed message passing. Erlang does this, and I"m sure just about every other common language supports this through an API/library for the language.

Answer 2

I disagree that FSM are trivial to implement. This is very short-sighted, and shows either a lack of familiarity with the alternatives, or the lack of experience with complex state machines.

The fundamental problem is that a state machine graph is obvious, but FSM code is not. Once you get beyond a dozen states and a score of transitions, FSM code becomes ugly and difficult to follow.

There are tools whereby you draw the state machine, and generate Java code for it. I don't know of any open source tools for that, however.

Now, getting back to Erlang/Scala, Scala has Actors and message passing as well, and is based on the JVM, so it might be a better alternative than Erlang given your constraints.

There's a DFA/NFA library on Scala as well, though it is not particularly a good one. It supports conversion from arbitrary regular expressions (ie, the literals need not be characters) into DFA/NFA.

I'll post some code below using it. In this code, the idea is creating a FSM which will accept any sequential combination of arbitrary prefixes for a list of words, the idea being looking up menu options without predefined keybinds.

import scala.util.regexp._
import scala.util.automata._

// The goal of this object below is to create a class, MyChar, which will
// be the domain of the tokens used for transitions in the DFA. They could
// be integers, enumerations or even a set of case classes and objects. For
// this particular code, it's just Char.
object MyLang extends WordExp {
  type _regexpT = RegExp
  type _labelT = MyChar

  case class MyChar(c:Char) extends Label
}

// We now need to import the types we defined, as well as any classes we
// created extending Label.    
import MyLang._

// We also need an instance (singleton, in this case) of WordBerrySethi,
// which will convert the regular expression into an automatum. Notice the
// language being used is MyLang.    
object MyBerrySethi extends WordBerrySethi {
  override val lang = MyLang
}

// Last, a function which takes an input in the language we defined,
// and traverses the DFA, returning whether we are at a sink state or
// not. For other uses it will probably make more sense to test against
// both sink states and final states.
def matchDet(pat: DetWordAutom[MyChar], seq: Seq[Char]): Boolean =
  !pat.isSink((0 /: seq) ((state, c) => pat.next(state, MyChar(c))))

// This converts a regular expression to a DFA, with using an intermediary NFA    
def compile(pat: MyLang._regexpT) = 
  new SubsetConstruction(MyBerrySethi.automatonFrom(pat, 100000)).determinize

// Defines a "?" function, since it isn't provided by the library
def Quest(rs: _regexpT*) = Alt(Eps, Sequ(rs: _*)) // Quest(pat) = Eps|pat = (pat)?


// And now, the algorithm proper. It splits the string into words
// converts each character into Letter[MyChar[Char]],
// produce the regular expression desired for each word using Quest and Sequ,
// then the final regular expression by using Sequ with each subexpression.
def words(s : String) = s.split("\\W+")
def wordToRegex(w : String) : Seq[MyLang._regexpT] = w.map(c => Letter(MyChar(c)))
def wordRegex(w : String) = Quest(wordToRegex(w) reduceRight ((a,b) => Sequ(a, Quest(b))))
def phraseRegex(s : String) = Sequ(words(s).map(w => wordRegex(w)) : _*)

// This takes a list of strings, produce a DFA for each, and returns a list of
// of tuples formed by DFA and string.
def regexList(l : List[String]) = l.map(s => compile(phraseRegex(s)) -> s)

// The main function takes a list of strings, and returns a function that will
// traverse each DFA, and return all strings associated with DFAs that did not
// end up in a sink state.
def regexSearcher(l : List[String]) = {
  val r = regexList(l)
  (s : String) => r.filter(t => matchDet(t._1, s)).map(_._2)
}

Answer 3

This particular application, telco protocol implementation, is what Erlang was built for. The initial applications of Erlang at Ericsson were telephone switches and the earliest commercial products were ATM switches supporting all manner of telco protocols.

OTP has a standard behaviour for implementing FSMs called gen_fsm. There's an example of its use in a non-trivial FSM in some of the OTP Documentation.

OSERL is an open souce SMPP implementation in Erlang and demonstrates how you can implement a telco protocol using gen_fsms. A good example to look at would be gen_esme_session.

While I can't point you to the code, I know there are quite a few Erlang companies selling telco oriented products: Corelatus, Synapse, Motivity among others.

Answer 4

I can hardly think of any language where implementing an FSM is non-trivial. Maybe this one.

...
if (currentState == STATE0 && event == EVENT0) return STATE1;
if (currentState == STATE1 && event == EVENT0) return STATE2;
...

Answer 5

I agree that switch statements should be out of the question... they eventually lead to maintenance nightmares. Can't you use the State Pattern to implement your FSM? Depending on your actual implementation, you could use actors (if you have multiple FSM collaborating - hm... is that possible?). The nice thing about actors is that the framework for passing messages is already there.

An example of using State would be:

trait State {
  def changeState(message: Any): State
}

trait FSM extends Actor {
  var state: State

  def processMessage(message: Any) {
    state = state.changeState(message)
  }

  override def act() {
    loop {
      react {
        case m: Any => processMessage(m)
      }
    }
  }
}

This is very basic code, but as I don't know more of the requirements, that's the most I can think of. The advantage of State is that every state is self-contained in one class.

-- Flaviu Cipcigan