Реализация конечного автомата с одной сопрограммой

Я ищу способы реализовать FSM, что привело к моей первой встрече с сопрограммами.

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

В качестве альтернативы я могу использовать отдельную сопрограмму для обработки каждого состояния и передать какую-то сопрограмму диспетчера. Однако я не вижу особых преимуществ использования сопрограмм по сравнению с обычными функциями в этой настройке.

Вот простой конечный автомат, с моделированием которого у меня проблемы:

A --'a'--> B
A --'b'--> C
B --'a'--> C
B --'b'--> A
C --'a'--> A
C --'b'--> B

И вот что у меня пока есть. Окончательная реализация будет на C++ с использованием Boost, но я использую Python для прототипирования.

#!/usr/bin/python3

def StateMachine():
    while True:
        print("  Entered state A")
        input = (yield)
        if input == "a":
            print("  Entered state B")
            input = (yield)
            if input == "a":
                # How to enter state C from here?
                pass
            elif input == "b":
                continue
        elif input == "b":
            print("  Entered state C")
            input = (yield)
            if input == "b":
                continue
            elif input == "a":
                # How to enter state B from here?
                pass

if __name__ == "__main__":
    sm = StateMachine()
    sm.__next__()
    while True:
        for line in input():
        sm.send(line)

Можно ли исправить эту сопрограмму, чтобы правильно моделировать конечный автомат? Или я должен пойти другим путем об этом?


state-machine coroutine fsm
person mcmlxxxvi    schedule 20.12.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я бы явно смоделировал конечный автомат:

def StateMachine():
    state = 'A'
    while True:
        print(state)
        input = (yield)
        if state == 'A':
            if input == 'a':
                state = 'B'
            elif input == 'b':
                state = 'C'
            else:
                break
        elif state == 'B':
            if input == 'a':
                state = 'C'
            elif input == 'b':
                state = 'A'
            else:
                break
        elif state == 'C':
            if input == 'a':
                state = 'A'
            elif input == 'b':
                state = 'B'
            else:
                break
        else:
            break

Это должно быть очень аккуратно переведено на C++ с использованием вложенных операторов switch или таблицы перехода состояний.

Если вы предпочитаете неявную модель, вам нужен способ обработки циклов в конечном автомате. В C или C++ это, вероятно, будет goto. Я бы не рекомендовал этот подход, но если он вам более удобен, чем явное состояние, вот как это может выглядеть:

#include <stdio.h>

#define start(state) switch(state) { case 0:;
#define finish default:;}
#define yield(state, value) do { state = __LINE__; return (value); case __LINE__:; } while(0)

struct coroutine {
    int state;
};

int
run(struct coroutine *c, char input)
{
    start(c->state)
    {
A:
        printf("Entered state A\n");
        yield(c->state, 1);
        if(input == 'a') goto B;
        if(input == 'b') goto C;
B:
        printf("Entered state B\n");
        yield(c->state, 1);
        if(input == 'a') goto C;
        if(input == 'b') goto A;
C:
        printf("Entered state C\n");
        yield(c->state, 1);
        if(input == 'a') goto A;
        if(input == 'b') goto B;
    } finish;

    return 0;
}

int
main(void)
{
    int a;
    struct coroutine c = {0};

    while((a = getchar()) != EOF && run(&c, a));

    return 0;
}
person laindir    schedule 20.12.2013
comment
Наличие явных состояний всегда возможно, но я стараюсь избегать этого. - person mcmlxxxvi; 21.12.2013
comment
Я думаю, что проблема, с которой вы столкнетесь, заключается в том, что вы пытаетесь представить циклический граф в виде дерева. Это будет возможно только в том случае, если вы позволите повторно войти в дерево; это займет либо что-то вроде goto в середине дерева, либо переменную для сохранения состояния, чтобы дерево можно было повторно ввести вверху. - person laindir; 31.12.2013
comment
Я сам так считаю, но я не могу найти ссылку на то, что одни только сопрограммы не могут быть использованы для реализации циклического конечного автомата. - person mcmlxxxvi; 01.01.2014
comment
На самом деле это не относится к сопрограммам. Вы хотите реализовать каждый переход состояния как свою собственную ветвь if, но вам нужно прыгать по ветвям дерева. В Python нет goto, но есть в C и C++, я отредактирую свой ответ, чтобы включить пример на C с gotos. Я не думаю, что это лучший подход, но он демонстрирует, что возможно. - person laindir; 02.01.2014
comment
После кодирования он выглядит чище, чем я ожидал (я начал с гибридной логики ветвления if, как у вас в Python, но переключился только на goto, что существенно очистило ситуацию). Вероятно, он должен обрабатывать входные данные, отличные от «a» и «b» (возможно, просто возвращая 0). #define в верхней части немного неприглядны, но позволяют вам реализовать генераторы на стандартном C с небольшим синтаксическим сахаром. Python в основном делает то же самое за кулисами со своим ключевым словом yield. - person laindir; 02.01.2014
comment
Дополнительное примечание, которое я хотел избежать, чтобы не запутать воду, заключается в следующем: сами сопрограммы или генераторы часто реализуются за кулисами как конечные автоматы (где состояние — это строка или инструкция для выполнения при следующем возобновлении). Я чувствую, что должен, по крайней мере, указать на это, поскольку на самом деле в C нет ничего за кулисами. Вот для чего на самом деле нужны эти макросы #define. - person laindir; 02.01.2014
comment
Спасибо за уделенное время. В итоге мы использовали машину метасостояний Boost, поскольку у нас был старый код, который можно было изменить, но я получил свой ответ: одних сопрограмм как потока управления, как правило, не достаточно для реализации конечного автомата. . - person mcmlxxxvi; 14.01.2014

arrow_upward
0
arrow_downward

Теоретически каждый конечный автомат может быть реализован с помощью одной сопрограммы только с одной из следующих структур:

  • тесты на вспомогательных переменных
  • goto заявления
  • многоуровневые выходы из петель

Конечно, структуры if-then-else и while считаются доступными. С другой стороны, такая реализация не всегда осуществима только с одноуровневыми выходами.

Таким образом, конкретный пример записывается без переменных состояния и goto следующим образом:

#!/usr/bin/python3 
# Python doesn't support multilevel exits, so try/except can be used instead.
# However, for this FSM, single-level exits are sufficient.  
def StateMachine():
  while True:
    while True:
      print("  Entered state A")
      input = (yield)
      if input == "a":
          print("  Entered state B")
          input = (yield)
          if input == "a": 
            break
          elif input == "b": 
            pass
      elif input == "b": 
            break    
    while True:
      print("  Entered state C")
      input = (yield)
      if input == "a": 
          break
      elif input == "b": 
          print("  Entered state B")
          input = (yield)
          if input == "a": 
            pass
          elif input == "b": 
            break
if __name__=="__main__":
     sm = StateMachine()
     sm.__next__()
     while True:
       for line in input():
        sm.send(line)
person Abc    schedule 04.08.2017