Finite State Machine und inter FSM-Signalisierung

Question

Empfehlungen für Sprachen mit nativem (also keine FSM-Generierungs-Tool) Unterstützung für die Zustandsmaschine Entwicklung und Ausführung und Weitergabe von Nachrichten / Signalen. Dies ist für die Telekommunikation, beispiels Umsetzung von FSMs von dieser Komplexität.

Ich habe Erlang betrachtet, würde aber ein Feedback, Anregungen, Zeiger auf Tutorials, Alternativen, vor allem Java-basierter Frameworks lieben. Vielleicht Scala?

Open Source nur. Ich bin nicht für UML oder einen regulären Ausdruck bezogene Lösungen suchen.

Da dies für die Umsetzung der Telekommunikations ist Protokolle der FSMs nicht-trivial sein können. Viele Staaten, viele Übergänge, Signal basiert, Eingang Einschränkungen / Wächter. Dynamische Instantiierung wäre ein Plus. Switch-Anweisungen sind außer Frage, es schnell unbrauchbaren nistet. Es ist kaum besser, wenn / sonst.

Ich würde es vorziehen, nicht ist abhängig von Grafik-Design; das Format FSM Beschreibung sollte den Menschen lesbaren / editierbar / überschaubar sein.

-

Ich habe beschlossen, für C auf einen Schauspieler-basierte Lösung konzentrieren ++

Zum Beispiel das Theron Framework bietet einen Ausgangspunkt http://theron.ashtonmason.net/ und zu vermeiden Switch-Anweisungen in der FSM basierte Ereignishandler diese C ++ FSM Template Framework sieht nützlich http: // satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

Ich bin einverstanden, dass die Switch-Anweisungen aus der Frage sein sollte ... sie schließlich zu Wartung Alpträume führen. Können Sie nicht verwenden a href den <= "http://books.google.co.uk/books?id=LjJcCnNf92kC&lpg=PP1&dq=head%20first%20design%20patterns&pg=PA385#v=onepage&q=&f=false" rel = "nofollow noreferrer"> State-Muster Ihre FSM zu implementieren? Je nach Ihrer tatsächlichen Implementierung können Sie Schauspieler verwenden (wenn Sie mehrere FSM kollaborierenden haben - hm ... das möglich ist). Die nette Sache über Schauspieler ist, dass der Rahmen für die Weitergabe von Nachrichten bereits vorhanden ist.

Ein Beispiel Zustand der Verwendung wäre:

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

Dies ist sehr einfach Code, aber wie ich mehr von den Anforderungen nicht wissen, das ist das ich mir vorstellen kann. Der Vorteil des Staates ist, dass jeder Staat ist in einer Klasse in sich abgeschlossen.

Answer 2

Diese besondere Anwendung, Telco-Protokoll-Implementierung, ist das, was Erlang für gebaut wurde. Die Erstanträge von Erlang bei Ericsson waren Telefon-Switches und die ersten kommerziellen Produkte ATM wurden schaltet alle Arten von Telco-Protokolle unterstützen.

OTP hat ein Standardverhalten für FSMs genannt gen_fsm implementieren. Es ist ein Beispiel für seine Verwendung in einer nicht-trivialen FSM in einige der OTP Dokumentation .

OSERL ist eine offene Souce SMPP Implementierung in Erlang und zeigt, wie Sie ein Telco-Protokoll gen_fsms implementieren können. Ein gutes Beispiel zu betrachten wäre gen_esme_session .

Während ich nicht, dass Sie auf den Code zeigen kann, ich weiß, es gibt eine ganze Reihe von Erlang Unternehmen Telco-orientierte Produkte zu verkaufen: Corelatus , Synapse , Motivity unter anderem.

Answer 3

Ich bin nicht einverstanden, dass FSM trivial zu implementieren sind. Das ist sehr kurzsichtig, und zeigt entweder einen Mangel an Vertrautheit mit den Alternativen, oder den Mangel an Erfahrung mit komplexen Zustandsmaschinen.

Das grundlegende Problem ist, dass eine Zustandsmaschine Graph liegt auf der Hand, aber FSM Code ist es nicht. Sobald Sie über ein Dutzend Staaten und eine Punktzahl von Übergängen erhalten, FSM-Code wird hässlich und schwer zu folgen.

Es gibt Werkzeuge, wobei Sie zeichnen die Zustandsmaschine, und erzeugen Java-Code für sie. Ich weiß nicht von irgendwelchen Open-Source-Tool für das aber nicht.

Nun, um Erlang / Scala immer wieder, hat Scala Schauspieler und Botschaft als auch vorbei, und auf der JVM basiert, so könnte es eine bessere Alternative als Erlang Ihre Einschränkungen gegeben.

Es gibt eine DFA / NFA-Bibliothek auf Scala als auch, obwohl es nicht besonders gut ist. Es unterstützt die Konvertierung von beliebigen regulären Ausdrücken (dh müssen die Literale nicht Zeichen) in DFA / NFA.

Ich werde einige Code per Post unten. In diesem Code ist die Idee, einen FSM zu schaffen, die für eine Liste von Worten jede sequenzielle Kombination von beliebigen Präfixen akzeptieren wird, wobei die Suche die Idee Menüoptionen ohne vordefinierte keybinds auf.

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

kann ich glaube kaum, jede Sprache, wo ein FSM Implementierung ist nicht trivial. Vielleicht diese .

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

Answer 5

Das Zustandsmuster (mit Java Aufzählungen) ist das, was wir in unserer Telekom-Anwendung zu verwenden, aber wir kleine FSMs verwenden:

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

sollte FSM trivial sein in jeder Sprache zu implementieren, die einen Fall statement.Your Wahl der Sprache hat, sollte darauf basieren, was die Finite-State-Maschine zu tun braucht.

Zum Beispiel, geben Sie, dass Sie dies für Telekom-Entwicklung tun müssen, und Nachrichten zu erwähnen. Ich würde Blick auf Systeme / Sprachen, die Message-Passing verteilt unterstützen. Erlang tut dies, und ich "ist sicher, fast jede andere gemeinsame Sprache unterstützt dies durch eine API / Bibliothek für die Sprache.