Máquina de estado finito y señalización entre FSM

Question

Recomendaciones para idiomas con soporte nativo (por lo que no hay herramientas de generación de FSM) para el desarrollo de máquinas de estado y ejecución y el paso de mensajes / señales. Esto es para telecomunicaciones, por ejemplo, implementación de FSM de este nivel de complejidad.

He considerado Erlang, pero me encantaría recibir comentarios, sugerencias, punteros a tutoriales, alternativas, particularmente marcos basados ??en Java. Tal vez Scala?

Solo de código abierto. No estoy buscando soluciones relacionadas con UML o expresiones regulares.

Como esto es para la implementación de protocolos de telecomunicaciones, los FSM pueden no ser triviales. Muchos estados, muchas transiciones, basadas en señales, restricciones / protecciones de entrada. La creación de instancias dinámicas sería una ventaja. Las declaraciones de cambio están fuera de la cuestión, rápidamente se anida en inutilizable. Es apenas mejor que si / si no.

Preferiría no depender del diseño gráfico; la descripción del formato FSM debe ser legible / editable / manejable para humanos.

-

He decidido centrarme en una solución basada en actor para C ++

Por ejemplo, el marco Theron proporciona un punto de partida http://theron.ashtonmason.net/ y para evitar sentencias de cambio en el controlador de eventos basado en FSM, este marco de plantilla FSM de C ++ parece útil http: // satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

Estoy de acuerdo en que las declaraciones de cambio deben estar fuera de discusión ... eventualmente conducen a pesadillas de mantenimiento. ¿No puede utilizar el Patrón de estado para implementar su FSM? Dependiendo de su implementación real, podría usar actores (si tiene múltiples FSM colaborando, hm ... ¿es eso posible?). Lo bueno de los actores es que el marco para pasar mensajes ya está allí.

Un ejemplo de uso de Estado sería:

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

Este es un código muy básico, pero como no conozco más de los requisitos, es lo máximo que se me ocurre. La ventaja de State es que cada estado es autónomo en una clase.

Answer 2

Esta aplicación en particular, la implementación del protocolo de telecomunicaciones, es para lo que se construyó Erlang. Las aplicaciones iniciales de Erlang en Ericsson fueron conmutadores telefónicos y los primeros productos comerciales fueron conmutadores ATM que admiten todo tipo de protocolos de telecomunicaciones.

OTP tiene un comportamiento estándar para implementar FSM llamado gen_fsm . Hay un ejemplo de su uso en un FSM no trivial en algunos de los Documentación OTP .

OSERL es una implementación SMPP de fuente abierta en Erlang y demuestra cómo puede implementar un protocolo de telecomunicaciones usando gen_fsm s. Un buen ejemplo para mirar sería gen_esme_session .

Si bien no puedo señalarle el código, sé que hay bastantes empresas de Erlang que venden productos orientados a las telecomunicaciones: Corelatus , Synapse , Motividad entre otros.

Answer 3

No estoy de acuerdo con que FSM sea trivial de implementar. Esto es muy miope y muestra una falta de familiaridad con las alternativas o la falta de experiencia con máquinas de estado complejas.

El problema fundamental es que un gráfico de máquina de estado es obvio, pero el código de FSM no lo es. Una vez que supere una docena de estados y una gran cantidad de transiciones, el código FSM se vuelve feo y difícil de seguir.

Existen herramientas mediante las cuales dibuja la máquina de estado y genera código Java para ella. Sin embargo, no conozco ninguna herramienta de código abierto para eso.

Ahora, volviendo a Erlang / Scala, Scala también tiene actores y mensajes que pasan, y se basa en la JVM, por lo que podría ser una mejor alternativa que Erlang dadas sus limitaciones.

También hay una biblioteca DFA / NFA en Scala, aunque no es particularmente buena. Admite la conversión de expresiones regulares arbitrarias (es decir, los literales no necesitan ser caracteres) en DFA / NFA.

Publicaré algún código a continuación usándolo. En este código, la idea es crear un FSM que acepte cualquier combinación secuencial de prefijos arbitrarios para una lista de palabras, la idea es buscar opciones de menú sin teclas predefinidas.

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

Casi no puedo pensar en ningún lenguaje en el que implementar un FSM no sea trivial. Tal vez este .

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

Answer 5

El patrón de estado (usando enumeraciones Java) es lo que usamos en nuestra aplicación de telecomunicaciones, sin embargo usamos pequeños 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

FSM debe ser trivial de implementar en cualquier lenguaje que tenga una declaración de caso. Su elección de lenguaje debe basarse en lo que esa máquina de estados finitos necesita hacer.

Por ejemplo, usted declara que necesita hacer esto para el desarrollo de telecomunicaciones y menciona mensajes. Me gustaría ver los sistemas / idiomas que admiten el paso de mensajes distribuidos. Erlang hace esto, y estoy seguro de que casi cualquier otro idioma común lo admite a través de una API / biblioteca para el idioma.