Macchina a stati finiti e segnalazione inter-FSM

Question

Consigli per le lingue con supporto nativo (quindi senza strumenti di generazione FSM) per lo sviluppo e lo esecuzione della macchina a stati e il passaggio di messaggi / segnali. Questo vale per le telecomunicazioni, ad esempio l'implementazione di FSM di questo livello di complessità.

Ho considerato Erlang, ma mi piacerebbe un po 'di feedback, suggerimenti, puntatore a tutorial, alternative, in particolare framework basati su Java. Forse Scala?

Solo open source. Non sto cercando UML o soluzioni correlate all'espressione regolare.

Poiché questo è per l'implementazione dei protocolli di telecomunicazione, gli FSM possono essere non banali. Molti stati, molte transizioni, basate sul segnale, vincoli / protezioni di ingresso. L'istanza dinamica sarebbe un vantaggio. Le istruzioni switch sono fuori questione, diventa rapidamente inutilizzabile. È appena meglio che if / else.

Preferirei non dipendere dal design grafico; la descrizione del formato FSM deve essere leggibile / modificabile / gestibile dall'uomo.

-

Ho deciso di concentrarmi su una soluzione basata su Actor per C ++

Ad esempio, il framework Theron fornisce un punto di partenza http://theron.ashtonmason.net/ e per evitare dichiarazioni switch nel gestore eventi basato su FSM, questo Framework modello FSM C ++ sembra utile http: // satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

Sono d'accordo sul fatto che le dichiarazioni degli switch dovrebbero essere fuori questione ... alla fine portano a incubi di manutenzione. Non puoi utilizzare la Pattern di stato per implementare il tuo FSM? A seconda della tua effettiva implementazione, potresti usare gli attori (se hai più collaborazioni di FSM - hm ... è possibile?). La cosa bella degli attori è che il framework per il passaggio dei messaggi è già lì.

Un esempio dell'utilizzo di State sarebbe:

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

Questo è un codice molto semplice, ma poiché non conosco più i requisiti, è il massimo che mi viene in mente. Il vantaggio di State è che ogni stato è autonomo in una classe.

Answer 2

Questa particolare applicazione, l'implementazione del protocollo telco, è stata creata per Erlang. Le applicazioni iniziali di Erlang presso Ericsson erano interruttori telefonici e i primi prodotti commerciali erano interruttori ATM che supportavano tutti i tipi di protocolli telco.

OTP ha un comportamento standard per l'implementazione di FSM chiamato gen_fsm . C'è un esempio del suo utilizzo in un FSM non banale in alcuni dei Documentazione OTP .

OSERL è un'implementazione SMPP di tipo open souce in Erlang e dimostra come è possibile implementare un protocollo telco usando gen_fsm s. Un buon esempio da guardare sarebbe gen_esme_session .

Anche se non posso indicarti il ??codice, so che ci sono alcune aziende Erlang che vendono prodotti orientati al telco: Corelatus , Synapse , Motivity tra gli altri.

Answer 3

Non sono d'accordo sul fatto che FSM sia banale da implementare. Questo è molto miope e mostra una mancanza di familiarità con le alternative o la mancanza di esperienza con macchine statali complesse.

Il problema fondamentale è che un grafico di una macchina a stati è ovvio, ma non lo è codice di FSM. Una volta superati una dozzina di stati e una ventina di transizioni, il codice FSM diventa brutto e difficile da seguire.

Esistono strumenti per cui disegna la macchina a stati e generi codice Java per essa. Non conosco alcuno strumento open source per questo, tuttavia.

Ora, tornando a Erlang / Scala, Scala ha anche attori e messaggi che passano, ed è basato sulla JVM, quindi potrebbe essere un'alternativa migliore di Erlang dati i tuoi vincoli.

C'è anche una libreria DFA / NFA su Scala, anche se non è particolarmente buona. Supporta la conversione da espressioni regolari arbitrarie (vale a dire, i letterali non devono necessariamente essere caratteri) in DFA / NFA.

Pubblicherò un po 'di codice qui sotto utilizzandolo. In questo codice, l'idea sta creando un FSM che accetterà qualsiasi combinazione sequenziale di prefissi arbitrari per un elenco di parole, con l'idea di cercare opzioni di menu senza combinazioni di tasti predefinite.

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

Non riesco quasi a pensare a nessun linguaggio in cui l'implementazione di un FSM non sia banale. Forse questo .

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

Answer 5

Il modello di stato (usando enumerazioni Java) è quello che usiamo nella nostra applicazione di telecomunicazione, tuttavia usiamo piccoli 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

La FSM dovrebbe essere banale da implementare in qualsiasi lingua che abbia una dichiarazione case. La tua scelta della lingua dovrebbe essere basata su ciò che deve fare quella macchina a stati finiti.

Ad esempio, dichiari di doverlo fare per lo sviluppo delle telecomunicazioni e di menzionare i messaggi. Vorrei esaminare sistemi / lingue che supportano il passaggio di messaggi distribuiti. Erlang fa questo, e sono sicuro che quasi ogni altro linguaggio comune lo supporta attraverso un'API / libreria per il linguaggio.