14

ステート マシンの開発と実行、およびメッセージ/シグナルの受け渡しをサポートするネイティブ (FSM 生成ツールがない) 言語の推奨事項。これはテレコム用です。たとえば、このレベルの複雑さの FSM の実装などです。

私は Erlang を検討しましたが、フィードバック、提案、チュートリアルへのポインタ、代替案、特に Java ベースのフレームワークを歓迎します。もしかしてスカラ？

オープンソースのみ。UML や正規表現に関連するソリューションは探していません。

これは通信プロトコルの実装のためのものであるため、FSM は自明ではない可能性があります。多くの状態、多くの遷移、信号ベース、入力制約/ガード。動的なインスタンス化はプラスになります。switch ステートメントは問題外です。すぐにネストして使用できなくなります。if/else よりもかろうじて優れています。

グラフィックデザインに依存したくない。形式の FSM 記述は、人間が判読可能/編集可能/管理可能でなければなりません。

--

C++ のアクター ベースのソリューションに集中することにしました。

たとえば、Theron フレームワークは開始点http://theron.ashtonmason.net/を提供し、FSM ベースのイベント ハンドラーで switch ステートメントを回避するには、この C++ FSM テンプレート フレームワークが役立ちますhttp://satsky.spb.ru/articles/ fsm/fsmEng.php

4

6 に答える 6

10

この特定のアプリケーション、電話会社のプロトコルの実装は、Erlang が構築されたものです。Ericsson における Erlang の最初のアプリケーションは電話交換機であり、初期の商用製品はあらゆる種類の通信プロトコルをサポートする ATM スイッチでした。

OTP には、 と呼ばれる FSM を実装するための標準的な動作がありますgen_fsm。一部のOTP ドキュメントには、重要な FSM での使用例があります。

OSERLは、Erlang でのオープン ソースの SMPP 実装であり、s を使用して電話会社のプロトコルを実装する方法を示していますgen_fsm。見る良い例はgen_esme_sessionです。

コードを紹介することはできませんが、Corelatus、Synapse、Motivityなど、通信事業者向けの製品を販売している Erlang 企業がかなりあることは知っています。

于 2009-09-18T00:53:44.163 に答える
4

私は、FSM の実装が簡単ではないことに同意しません。これは非常に近視眼的であり、代替手段に精通していないか、複雑なステート マシンの経験が不足していることを示しています。

根本的な問題は、ステート マシングラフは明らかですが、FSMコードはそうではないことです。ダースの状態と多数の遷移を超えると、FSM コードは見苦しく、理解するのが難しくなります。

ステート マシンを描画し、そのための Java コードを生成するツールがあります。ただし、そのためのオープンソースツールは知りません。

さて、Erlang/Scala に戻ると、Scala にはアクターとメッセージ パッシングもあり、JVM に基づいているため、制約を考えると、Erlang よりも優れた代替手段になる可能性があります。

Scala にも 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)
}
于 2009-09-17T21:14:41.777 に答える
0

FSM の実装が自明ではない言語はほとんど考えられません。たぶんこれ。

...
if (currentState == STATE0 && event == EVENT0) return STATE1;
if (currentState == STATE1 && event == EVENT0) return STATE2;
...
于 2009-09-18T09:45:08.627 に答える
0

State パターン (Java enum を使用) は、テレコム アプリケーションで使用するものですが、小さな 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();
    }
}
于 2011-02-04T05:34:53.137 に答える
-1

FSMは、caseステートメントを含む任意の言語で実装するのは簡単である必要があります。言語の選択は、その有限状態マシンが実行する必要があることに基づいている必要があります。

たとえば、テレコム開発のためにこれを行う必要があると述べ、メッセージに言及します。分散メッセージパッシングをサポートするシステム/言語を調べます。Erlangはこれを行い、他のほぼすべての一般的な言語がその言語のAPI/ライブラリを介してこれをサポートしていると確信しています。

于 2009-09-17T20:15:14.777 に答える