유한 상태 기계 및 FSM 간 신호

StackOverflow https://stackoverflow.com/questions/1441077

문제

기본 (FSM 생성 도구 없음)이있는 언어에 대한 권장 사항 상태 기계 개발 및 실행 메시지/신호 전달. 이것은 통신을위한 것이며, 예를 들어이 수준의 복잡성의 FSM을 구현합니다.

나는 Erlang을 고려했지만 피드백, 제안, 튜토리얼에 대한 포인터, 대안, 특히 Java 기반 프레임 워크를 좋아할 것입니다. 아마 스칼라?

오픈 소스 만. 나는 UML 또는 정규 표현 관련 솔루션을 찾고 있지 않습니다.

이는 통신 프로토콜의 구현을위한 것이므로 FSM은 사소한 일 수 있습니다. 많은 주, 많은 전환, 신호 기반, 입력 제약 조건/경비원. 동적 인스턴스화는 플러스 일 것입니다. 스위치 명세서는 의문의 여지가 없으며 빠르게 사용할 수 없습니다. If/else보다 간신히 낫습니다.

나는 선호합니다 ~ 아니다 그래픽 디자인에 의존합니다. 형식 FSM 설명은 사람을 읽을 수있는/편집 가능/관리 가능해야합니다.

--

C ++에 대한 배우 기반 솔루션에 집중하기로 결정했습니다.

예를 들어, Theron 프레임 워크는 출발점을 제공합니다. http://theron.ashtonmason.net/ FSM 기반 이벤트 핸들러의 스위치 설명을 피하려면이 C ++ FSM 템플릿 프레임 워크가 유용합니다. http://satsky.spb.ru/articles/fsm/fsmeng.php

도움이 되었습니까?

해결책

나는 스위치 진술이 의문에서 벗어나야한다는 데 동의한다. 그들은 결국 유지 보수 악몽으로 이어진다. 당신은 사용할 수 없습니다 상태 패턴 FSM을 구현하려면? 실제 구현에 따라 배우를 사용할 수 있습니다 (여러 FSM 협업이있는 경우 -HM ... 가능합니까?). 배우의 좋은 점은 메시지를 전달하기위한 프레임 워크가 이미 있다는 것입니다.

상태를 사용하는 예는 다음과 같습니다.

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

이것은 매우 기본적인 코드이지만, 더 많은 요구 사항을 알지 못한 것처럼, 그것이 내가 생각할 수있는 가장 많은 것입니다. 상태의 장점은 모든 주가 한 클래스에 독립적이라는 것입니다.

다른 팁

이 특정 응용 프로그램 인 Telco Protocol 구현은 Erlang을 위해 구축 된 것입니다. Ericsson에서 Erlang의 초기 응용 프로그램은 전화 스위치였으며 최초의 상업용 제품은 모든 방식의 통신 프로토콜을 지원하는 ATM 스위치였습니다.

OTP는 호출 된 FSM을 구현하기위한 표준 동작을 가지고 있습니다 gen_fsm. 일부에서 사소한 FSM에서 사용하는 예가 있습니다. OTP 문서.

오서 Erlang에서 Open Souce SMPP 구현이며, Telco Protocol을 구현하는 방법을 보여줍니다. gen_fsm에스. 보기 좋은 예는 될 것입니다 gen_esme_session.

코드를 지적 할 수는 없지만 Telco 지향 제품을 판매하는 Erlang 회사가 꽤 많다는 것을 알고 있습니다. Corelatus, 시냅스, 모호함 무엇보다도.

FSM이 구현하기가 사소한 것에 동의하지 않습니다. 이것은 매우 근시안적이며 대안에 대한 친숙 함이 없거나 복잡한 상태 기계에 대한 경험이 부족하다는 것을 보여줍니다.

근본적인 문제는 상태 기계입니다 그래프 분명하지만 FSM 암호 아니다. 12 개 주와 많은 전환을 넘어서면 FSM 코드는 추악하고 따라 가기가 어려워집니다.

당신을 찾는 도구가 있습니다 그리다 상태 머신을 사용하여 Java 코드를 생성합니다. 그러나 그에 대한 오픈 소스 도구는 모릅니다.

이제 Erlang/Scala로 돌아가서 Scala는 배우와 메시지가 통과되며 JVM을 기반으로하므로 제약 조건을 감안할 때 Erlang보다 더 나은 대안이 될 수 있습니다.

스칼라에는 DFA/NFA 라이브러리도 있지만 특히 좋은 것은 아닙니다. 임의의 정규 표현식 (즉, 리터럴이 문자 일 필요는 없음)에서 DFA/NFA로 전환을 지원합니다.

아래에 코드를 게시하겠습니다. 이 코드에서 아이디어는 단어 목록에 대한 임의의 접두사의 순차적 조합을 수용하는 FSM을 생성하는 것입니다.

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

FSM을 구현하는 것이 사소하지 않은 언어를 거의 생각할 수 없습니다. 아마도 이 하나.

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

상태 패턴 (Java Enums 사용)은 통신 응용 프로그램에서 사용하는 것이지만 작은 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();
    }
}

FSM은 사례 진술이있는 모든 언어로 구현하기 위해 사소해야합니다. 언어 선택은 유한 상태 기계가 필요한 일을 기반으로해야합니다.

예를 들어, 통신 개발 및 메시지를 위해이 작업을 수행해야한다고 말합니다. 분산 메시지 전달을 지원하는 시스템/언어를 살펴 보겠습니다. Erlang 은이 작업을 수행하며, 나는 다른 모든 공통 언어가 언어의 API/라이브러리를 통해 이것을 지원합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top