Máquina de estados finitos y señalización entre FSM

Question

Recomendaciones para idiomas con soporte nativo (por lo que no hay herramientas de generación FSM) para desarrollo de máquinas de estados y ejecución y transmisión 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, sugerencias sobre tutoriales, alternativas, en particular sobre frameworks basados ​​en Java. Tal vez Scala?

Solo fuente abierta. No estoy buscando soluciones relacionadas con UML o expresión regular.

Como esto es para la implementación de protocolos de telecomunicaciones, las FSM pueden ser no triviales. Muchos estados, muchas transiciones, basadas en señal, restricciones de entrada/guardias. La creación de instancias dinámicas sería un plus. Las declaraciones Switch están fuera de discusión, anida rápidamente en inutilizable. Es apenas mejor que si/else.

Preferiría no Depende del diseño gráfico; la descripción del formato FSM debe ser legible/editable/manejable por el ser humano.

-

que han decidido centrarse en una solución basada Actor para C++

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

Answer 1

Estoy de acuerdo en que las instrucciones de cambio deben estar fuera de cuestión ... finalmente conducen a pesadillas de mantenimiento. ¿No puedes usar el State Pattern para implementar tu 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 transmitir mensajes ya está allí.

Un ejemplo del 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 yo no sé más de los requisitos, que es lo máximo que puedo imaginar. La ventaja de State es que cada estado es autónomo en una clase.

Answer 2

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

Por ejemplo, indica que debe hacer esto para el desarrollo de telecomunicaciones y mencionar mensajes. Me gustaría ver los sistemas/idiomas que admiten el paso de mensajes distribuidos. Erlang hace esto, y estoy seguro de que casi todos los demás lenguajes comunes lo soportan a través de una API/biblioteca para el lenguaje.

Answer 3

No estoy de acuerdo en que los FSM sean triviales. Esto es muy corto de miras y muestra una la falta de familiaridad con las alternativas, o la falta de experiencia con máquinas de estado complejas.

el problema fundamental es que una máquina de estados gráfico es obvio, pero FSM código no lo es. una vez que llegue más allá de una docena de estados y una veintena de transiciones, el código FSM se vuelve feo y difícil de seguir.

Ther Son herramientas mediante las cuales dibujan la máquina de estados y generan código Java para ellas. Sin embargo, no conozco ninguna herramienta de código abierto para eso.

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

También hay una biblioteca de 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.

Voy a publicar un 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 keybinds predefinidos.

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

Esta aplicación 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 switches 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 OTP Documentation.

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

Aunque no puedo indicarle el código, sé que hay bastantes compañías de Erlang que venden productos orientados a telecomunicaciones: Corelatus, Synapse, Motivity entre otros.

Answer 5

No puedo pensar en ningún idioma donde implementar un FSM no es trivial. Tal vez this one.

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

Answer 6

El patrón de Estado (usando las enumeraciones de Java) es el que usamos en nuestra aplicación de telecomunicaciones, sin embargo usamos pequeña FSM de:

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