Реализация конечного автомата

Я ищу какого-то общего

  1. Оптимизация
  2. Правильность
  3. Расширяемость

совет по моей текущей реализации иерархического конечного автомата C++.

Образец

variable isMicOn = false
variable areSpeakersOn = false
variable stream = false
state recording
{
        //override block for state recording
        isMicOn = true //here, only isMicOn is true              
        //end override block for state recording
}
state playback
{
        //override block for state playback
        areSpeakersOn = true //here, only areSpeakersOn = true
        //end override block for state playback
        state alsoStreamToRemoteIp
        {
                //override block for state alsoStreamToRemoteIp
                stream = true //here, both areSpeakersOn = true and stream = true
                //end override block for state alsoStreamToRemoteIp
        }
}

goToState(recording)
goToState(playback)
goToState(playback.alsoStreamToRemoteIp)

Реализация

В настоящее время HSM реализован в виде древовидной структуры, в которой каждое состояние может иметь различное количество дочерних состояний.

Каждое состояние содержит переменное количество блоков «переопределения» (в std::map), которые переопределяют базовые значения. В корневом состоянии конечный автомат имеет набор переменных (функций, свойств...), инициализированных некоторыми значениями по умолчанию. Каждый раз, когда мы входим в дочернее состояние, список «переопределений» определяет переменную и значения, которые должны заменить переменные и значения с тем же именем в родительском состоянии. Обновленный оригинал для ясности.

Ссылочные переменные

Во время выполнения текущие состояния сохраняются в стеке.

Каждый раз при ссылке на переменную выполняется обход стека вниз в поисках наивысшего переопределения или, в случае отсутствия переопределений, значения по умолчанию.

Переключение состояний

Каждый раз, когда переключается на кадр с одним состоянием, это состояние помещается в стек.

Каждый раз, когда происходит переключение в состояние, я отслеживаю спуск по дереву, который ведет меня от текущего состояния к корневому состоянию. Затем я выполняю спуск по дереву от целевого состояния к корневому состоянию, пока не увижу, что текущая трасса соответствует предыдущей трассе. Я объявляю пересечение там, где встречаются эти две трассы. Затем, чтобы переключиться в целевое состояние, я спускаюсь из источника, извлекая кадры состояния из стека, пока не достигну точки пересечения. Затем я поднимаюсь к целевому узлу и помещаю кадры состояния в стек.

Итак, для примера кода выше

Трассировка выполнения для переключения состояния

  • Исходное состояние = запись

  • Целевое состояние = alsoStreamToRemoteIp

  • происхождение от источника = запись-> корень (трассировка = [корень])

  • происхождение от target = alsoStreamToRemoteIp->playback->root (trace = [playback, root])

  • Пересекается в корне.

Чтобы переключиться с записи на alsoStreamToRemoteIp,

  1. Извлеките «запись» из стека (и вызовите ее функцию выхода... здесь не определено).
  2. Поместите «воспроизведение» в стек (и вызовите функцию ввода).
  3. Поместите "alsoStreamToRemoteIp" в стек (и вызовите функцию ввода).

c++ stack state-machine tree
person jameszhao00    schedule 11.09.2009    source источник
comment
связанные: stackoverflow.com/questions/1647631/c-state-machine- дизайн   -  person jldupont    schedule 14.11.2009

Ответы (2)


arrow_upward
1
arrow_downward

Две вещи:

1: В большинстве случаев просто представляйте состояние вашей программы в виде модели и взаимодействуйте с ней напрямую или через шаблон MVC.

2: Если вам действительно нужен FSM, т.е. вы хотите случайным образом сделать кучу действий с вашей моделью, только некоторые из которых разрешены в определенное время. Потом....

По-прежнему сохраняйте состояние вашей программы в модели (или нескольких моделях в зависимости от декомпозиции и сложности) и представляйте состояния и переходы, например.

class State:
   def __init__(self):
      self.neighbors = {}

Где соседи содержат словарь {Action: State}, так что вы можете сделать что-то вроде

someAction.execute() # Actions manipulate the model (use classes or lambdas)
currentState = currentState.neighbors[someAction]

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

person DevDevDev    schedule 11.09.2009
comment
Как соседи подошли бы к вложенным состояниям? то есть для перехода из состояния A: B: C в A: E: F: G: H, как он узнает, какое дерево нужно пройти? - person jameszhao00; 12.09.2009
comment
Вы можете просто запустить BFS. Если вам нужны все пути, вам нужно немного настроить BFS. - person DevDevDev; 12.09.2009
comment
Посмотрите BFS, если вы этого не знаете, но в основном это даст вам путь от A -> D, примените действия для каждого состояния на пути, и вы окажетесь в D. - person DevDevDev; 12.09.2009
comment
Да, я знаю, как это реализовать. Просто BFS имеет худшие характеристики производительности по сравнению с моим пересечением нисходящего дерева, описанным выше. - person jameszhao00; 12.09.2009

arrow_upward
1
arrow_downward

Я не уверен, что следую всем деталям здесь. Однако кажется, что вы описываете реализацию FSM (конечный автомат), в которой у вас есть несколько конечных автоматов. Иногда, когда определенное событие (E1) происходит в определенном состоянии (S1) FSM F1, вам нужно ввести новый FSM (назовем его F2), чтобы упростить обработку в целом).

Если это так, то когда E1 происходит в S1, вам нужно вызвать подпрограмму действия, которая берет на себя чтение события и реализует F2 FSM. При вызове он начинает обработку в начальном состоянии F2 и обрабатывает соответствующие подсобытия. Когда он достигает своего конечного состояния, интерпретатор для F2 завершает работу. Он может вернуть некоторую информацию подпрограмме действия F1, которая была приостановлена ​​во время выполнения F2, и это может повлиять на следующее состояние в F1.

Остальная часть вашего описания — например, «блоки переопределения» — не будет иметь особого смысла для людей, не имеющих доступа к вашей реализации.

person Jonathan Leffler    schedule 11.09.2009
comment
В корневом состоянии конечный автомат имеет набор переменных (функций, свойств...), инициализированных некоторыми значениями по умолчанию. Каждый раз, когда мы входим в дочернее состояние, список переопределений определяет переменную и значения, которые должны заменить переменные и значения с тем же именем в родительском состоянии. Обновленный оригинал для ясности. - person jameszhao00; 11.09.2009