Конечный автомат и сигнализация между автоматами

Question

Рекомендации для языков с встроенной (поэтому без инструментов генерации FSM) поддержкой разработки конечных автоматов и исполнение и передачу сообщений/сигналов.Это для телекоммуникаций, например реализация автоматов такого уровня сложности.

Я рассматривал Erlang, но хотел бы получить отзывы, предложения, указатели на учебные пособия, альтернативы, особенно фреймворки на основе Java.Может быть, Скала?

Только с открытым исходным кодом.Я не ищу решения, связанные с UML или регулярными выражениями.

Поскольку речь идет о реализации телекоммуникационных протоколов, автоматы могут быть нетривиальными.Множество состояний, множество переходов, основанные на сигналах, входные ограничения/защиты.Динамическое создание экземпляров было бы плюсом.Об операторах переключения не может быть и речи, они быстро становятся непригодными для использования.Это едва ли лучше, чем если/иначе.

Я бы предпочел нет зависеть от графического дизайна;описание формата FSM должно быть удобочитаемым/редактируемым/управляемым человеком.

--

Я решил сосредоточиться на решении на основе актеров для C++.

Например, структура Theron обеспечивает отправную точку http://theron.ashtonmason.net/ и чтобы избежать операторов переключения в обработчике событий на основе FSM, эта платформа шаблонов C++ FSM выглядит полезной. http://satsky.spb.ru/articles/fsm/fsmEng.php

Answer 1

Я согласен, что операторы переключения не должны быть и речи...в конечном итоге они приводят к кошмарам при обслуживании.Не могли бы вы использовать Образец состояния реализовать свой FSM?В зависимости от вашей фактической реализации вы можете использовать актеров (если у вас сотрудничает несколько FSM - хм...это возможно?).Самое приятное в актерах то, что структура для передачи сообщений уже существует.

Примером использования State может быть:

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

Это очень простой код, но, поскольку я не знаю больше требований, это максимум, что я могу придумать.Преимущество государства в том, что каждое состояние замкнуто в одном классе.

Answer 2

Именно для этого конкретного приложения, реализации телекоммуникационного протокола, и был создан Erlang.Первыми приложениями Erlang в Ericsson были телефонные коммутаторы, а самыми ранними коммерческими продуктами были коммутаторы ATM, поддерживающие все виды телекоммуникационных протоколов.

OTP имеет стандартное поведение для реализации автоматов, называемое gen_fsm.В некоторых из них есть пример его использования в нетривиальном автомате. OTP-документация.

ОСЕРЛ представляет собой реализацию SMPP с открытым исходным кодом на Erlang и демонстрирует, как можно реализовать протокол телекоммуникации, используя gen_fsmс.Хорошим примером для рассмотрения может быть gen_esme_session.

Хотя я не могу указать вам на код, я знаю, что существует довольно много компаний Erlang, продающих продукты, ориентированные на телекоммуникации: Корелат, Синапс, Мотивация среди других.

Answer 3

Я не согласен с тем, что 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)
}

Answer 4

Я едва могу вспомнить какой-либо язык, в котором реализация FSM была бы нетривиальной.Может быть Вот этот.

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

Answer 5

Шаблон State (с использованием перечислений Java) — это то, что мы используем в нашем телекоммуникационном приложении, однако мы используем небольшие автоматы:

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 должен быть простым для реализации на любом языке, где есть оператор case. Выбор языка должен основываться на том, что должен делать этот конечный автомат.

Например, вы заявляете, что вам нужно это сделать для развития телекоммуникаций и упоминаете сообщения.Я бы посмотрел на системы/языки, которые поддерживают распределенную передачу сообщений.Erlang делает это, и я уверен, что почти любой другой распространенный язык поддерживает это через API/библиотеку для этого языка.