Finite State Machine e inter-FSM sinalização

Question

Recomendações para idiomas com suporte nativo (por isso há ferramentas de geração FSM) para o desenvolvimento de máquina de estado e execução e passando de mensagens / sinais. Isto é para telecomunicações, p.ex. implementação de FSMs deste nível de complexidade.

Eu tenho considerado Erlang, mas adoraria algum feedback, sugestões, ponteiro para tutoriais, alternativas, particularmente os quadros baseados em Java. Talvez Scala?

Só Open source. Eu não estou à procura de UML ou soluções relacionadas com expressões regulares.

Como este é para a implementação de telecomunicações protocolos FSMs podem ser não-trivial. Muitos estados, muitas transições, sinal de base, as restrições de entrada / guardas. instanciação dinâmica seria um plus. instruções switch estão fora de questão, rapidamente ninhos para inutilizável. É quase melhor que if / else.

Eu preferiria não depender de design gráfico; a descrição formato FSM deve ser legível / editável / administrável.

-

Decidi foco em uma solução baseada Ator para C ++

Por exemplo, o quadro Theron fornece um ponto de partida http://theron.ashtonmason.net/ para evitar declarações switch no manipulador de eventos FSM com base neste FSM molde da estrutura C ++ parece útil http: // satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

Eu concordo que as declarações de switch deve estar fora de questão ... eles eventualmente levar a pesadelos de manutenção. você não pode usar o Estado padrão para implementar o seu FSM? Dependendo da sua implementação real, você poderia usar atores (se você tiver múltiplos FSM colaborador -? Hm ... isso é possível). A coisa agradável sobre atores é que o quadro de mensagens que passam já está lá.

Um exemplo do uso Estado seria:

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 é um código muito básico, mas como eu não sei mais dos requisitos, isso é o máximo que eu posso pensar. A vantagem de Estado é que cada estado é auto-suficiente em uma classe.

Answer 2

Esta aplicação particular, telco implementação do protocolo, é o que Erlang foi construído. As aplicações iniciais de Erlang na Ericsson foram centrais telefónicas e os primeiros produtos comerciais foram comutadores ATM apoiando todos os tipos de protocolos de telecomunicações.

OTP tem um comportamento padrão para implementar FSMs chamados gen_fsm. Há um exemplo de seu uso em um FSM não-trivial em alguns dos OTP Documentação .

OSERL é um souce implementação open SMPP em Erlang e demonstra como você pode implementar um protocolo telco usando gen_fsms. Um bom exemplo para olhar seria gen_esme_session .

Enquanto eu não posso apontar-lhe o código, eu sei que há muito poucas empresas que vendem produtos Erlang orientada telco: Corelatus , Synapse , Motivity entre outros.

Answer 3

Eu discordo que FSM são triviais de implementar. Isto é muito míope, e mostra uma falta de familiaridade com as alternativas, ou a falta de experiência com máquinas de estado complexos.

O problema fundamental é que uma máquina de estado gráfico é óbvio, mas FSM código não é. Quando você vai além de uma dúzia de estados e uma pontuação de transições, código FSM torna-se feio e difícil de seguir.

Existem ferramentas em que você desenhar a máquina do Estado, e gerar o código Java para ele. Eu não sei de quaisquer ferramentas de código aberto para que, no entanto.

Agora, voltando ao Erlang / Scala, Scala tem Atores e passagem de mensagens, bem como, e é baseado na JVM, por isso pode ser uma alternativa melhor do que Erlang dadas suas limitações.

Há uma biblioteca DFA / NFA em Scala, bem como, embora não seja particularmente boa. Ele suporta conversão de expressões regulares arbitrárias (ie, os literais não precisa ser caracteres) para DFA / NFA.

Vou postar algum código abaixo usá-lo. Neste código, a idéia é criar um FSM que irá aceitar qualquer combinação sequencial de prefixos arbitrárias para uma lista de palavras, a idéia é olhar para cima opções de menu sem 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

eu mal posso pensar em qualquer idioma em que a implementação de um FSM não é trivial. Talvez esta .

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

Answer 5

O padrão Estado (usando enums Java) é o que usamos em nossa aplicação de telecomunicações, no entanto, usar de pequeno 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 deve ser trivial para implementar em qualquer linguagem que tem um caso statement.Your escolha de linguagem deve ser baseada no que que finitos necessidades de máquina de estado a fazer.

Por exemplo, você indicar que você precisa fazer isso para mensagens de Desenvolvimento das Telecomunicações e mencionar. Eu olhava para sistemas / linguagens que o apoio distribuídos passagem de mensagens. Erlang faz isso, e eu "m certeza de quase todos os outros linguagem comum suporta isso através de uma API / biblioteca para o idioma.