Etats finis et signalisation inter-FSM

Question

Recommandations pour les langues avec support natif (donc pas d'outils de génération FSM) pour le développement de la machine à états, ainsi que pour l'exécution et la transmission de messages / signaux. C’est le cas pour les télécommunications, par exemple pour la mise en œuvre de FSM de ce niveau de complexité.

J'ai envisagé Erlang, mais j'aimerais avoir des retours, des suggestions, des liens vers des tutoriels, des alternatives, en particulier des frameworks basés sur Java. Peut-être Scala?

Open source uniquement. Je ne cherche pas de solutions UML ou liées aux expressions régulières.

Comme il s’agit de l’implémentation de protocoles de télécommunication, les FSM peuvent ne pas être triviaux. De nombreux états, de nombreuses transitions, basés sur le signal, les contraintes / protections d'entrée. L'instanciation dynamique serait un plus. Les instructions Switch sont hors de question, il est rapidement inutilisable. C'est à peine mieux que si / sinon.

Je préférerais ne pas ne pas dépendre de la conception graphique; le format de la description FSM doit être lisible / modifiable / gérable.

-

J'ai décidé de me concentrer sur une solution basée sur Actor pour C ++

Par exemple, le cadre Theron fournit un point de départ http://theron.ashtonmason.net/ et pour éviter les instructions switch dans le gestionnaire d'événements basé sur FSM, cette structure de modèles FSM C ++ semble utile http: // satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

Je suis d'accord pour dire que les déclarations de commutateur devraient être hors de question ... elles finissent par entraîner des cauchemars d'entretien. Vous ne pouvez pas utiliser le Modèle d'état pour implémenter votre FSM? Selon votre implémentation réelle, vous pouvez utiliser des acteurs (si vous avez plusieurs FSM qui collaborent - hm ... est-ce possible?). La bonne chose à propos des acteurs est que le cadre pour la transmission de messages est déjà là.

Un exemple d'utilisation de State serait:

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

C’est un code très basique, mais comme je ne connais pas plus la configuration requise, c’est tout ce que je peux imaginer. L’avantage de State est que chaque Etat est autonome dans une classe.

Answer 2

Cette application particulière, l’implémentation du protocole telco, est ce pour quoi Erlang a été conçu. Les premières applications d’Erlang chez Ericsson étaient les commutateurs téléphoniques et les premiers produits commerciaux étaient des commutateurs ATM prenant en charge toutes sortes de protocoles de télécommunication.

OTP a un comportement standard pour la mise en œuvre des FSM appelé gen_fsm . Il existe un exemple de son utilisation dans un FSM non trivial dans certains des cas suivants: Documentation OTP .

OSERL est une implémentation ouverte de SMPP à Erlang et montre comment vous pouvez implémenter un protocole telco à l'aide de gen_fsm s. Un bon exemple à examiner serait gen_esme_session .

Bien que je ne puisse vous indiquer le code, je sais qu'il existe de nombreuses sociétés d'Erlang vendant des produits orientés télécoms: Corelatus , Synapse , Motivité , entre autres.

Answer 3

Je ne suis pas d'accord pour dire que les États fédérés de Micronésie sont faciles à mettre en œuvre. C'est une vision à très courte vue qui montre soit un manque de familiarité avec les alternatives, soit un manque d'expérience avec des machines à états complexes.

Le problème fondamental est qu’un graphe de la machine à états est évident, mais pas le code FSM . Une fois que vous avez dépassé une douzaine d’états et une vingtaine de transitions, le code FSM devient laid et difficile à suivre.

Il existe des outils pour dessiner la machine à états et générer le code Java correspondant. Je ne connais cependant aucun outil open source pour cela.

Maintenant, pour revenir à Erlang / Scala, Scala a également des acteurs et un message qui passe et est basé sur la machine virtuelle, ce qui pourrait être une meilleure alternative à Erlang compte tenu de vos contraintes.

Il existe également une bibliothèque DFA / NFA sur Scala, bien qu’elle ne soit pas particulièrement bonne. Il prend en charge la conversion d'expressions régulières arbitraires (les littéraux ne doivent pas nécessairement être des caractères) en DFA / NFA.

Je posterai du code ci-dessous en l'utilisant. Dans ce code, l’idée est de créer un FSM qui acceptera toute combinaison séquentielle de préfixes arbitraires pour une liste de mots, l’idée étant de rechercher des options de menu sans liens de clé prédéfinis.

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 4

Je peux difficilement penser à un langage où la mise en œuvre d’un FSM n’est pas triviale. Peut-être que celui-ci .

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

Answer 5

Le modèle d'état (utilisant des énumérations Java) correspond à ce que nous utilisons dans notre application de télécommunication. Cependant, nous utilisons de petits FSM:

public class Controller{
    private State itsState = State.IDLE;

    public void setState(State aState){
        itsState = aState;
    }

    public void action1(){
        itsState.action1(this);
    }

    public void action2(){
        itsState.action2(this);
    }

    public void doAction1(){
        // code
    }

    public void doAction2(){
        // code
    }
}

public enum State{
    IDLE{
        @Override
        public void action1(Controller aCtx){
            aCtx.doAction1();
            aCtx.setState(State.STATE1);
        }
    },

    STATE1{
        @Override
        public void action2(Controller aCtx){
            aCtx.doAction2();
            aCtx.setState(State.IDLE);
        }
    },

    public void action1(Controller aCtx){
        throw new IllegalStateException();
    }

    public void action2(Controller aCtx){
        throw new IllegalStateException();
    }
}

Answer 6

Les FSM doivent être faciles à implémenter dans toutes les langues ayant une instruction case.Votre choix de langue doit être basé sur ce que cette machine à états finis doit faire.

Par exemple, vous indiquez que vous devez le faire pour le développement des télécommunications et mentionner des messages. J'examinerais les systèmes / langages qui prennent en charge le transfert de messages distribué. Erlang le fait, et je suis sûr que presque tous les autres langages courants le supportent via une API / bibliothèque pour le langage.