使用单个协程实现有限状态机

Question

我正在寻找实现有限状态机（FSM）的方法，这让我第一次接触到协程。

我看到了几个示例（这里、这里和这里），它们表明一个状态机可以通过单个协程来实现。然而，我注意到所有这些状态机都有一个共同点，即除了循环之外，它们都是树形结构 - 也就是说，从起始节点到每个其他节点都只有一条路径（不包括循环），并且这与由嵌套的if提供的分层控制流相吻合。我试图建模的状态机至少有一个状态从起始节点到达该状态的路径不止一条（如果消除循环，则为有向无环图）。我无法想象什么样的控制流（除了goto）能够实现这一点，或者是否可能实现。

另外，我可以使用单独的协程来处理每个状态并向某种调度协程进行yield。但是，在这种设置中，我没有看到使用协程相对于常规函数的特别好处。

下面是我尝试建模的一个简单状态机：

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

以下是我目前的进展。最终实现将采用Boost C++，但我正在使用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)

这个协程能否被修复以正确地模拟状态机？或者我需要另外想办法来处理它？

- mcmlxxxvi

Answer 1

我会明确地建立状态机模型：

我会明确地建立状态机模型：

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

使用嵌套的switch语句或状态转移表，这个内容可以很好地翻译成C++。

如果您更喜欢隐式模型，则需要一种处理状态机中循环的方法。在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;
}

- laindir

---

我认为你将会遇到的问题是，你试图将一个循环图表示为一棵树。这只有在允许重新进入树的情况下才可能实现；这将需要像 goto 进入树的中间或者一个变量来保存状态，以便可以从顶部重新进入树。 - laindir

我个人也这样认为，但我找不到关于“仅使用协程无法实现循环有限状态机”的参考资料。 - mcmlxxxvi

这并不是仅限于协程。您想要将每个状态转换实现为自己的if分支，但需要跨越树的分支进行跳转。Python没有goto，但C和C++有，我将编辑我的答案以包括在C中使用goto的示例。我认为这不是最好的方法，但它确实演示了可能的方法。 - laindir

编码后，它看起来比我预期的要更清晰（我一开始使用了 Python 中类似的 if 分支逻辑混合，但后来切换到了 goto，这使得代码大幅度简化）。它可能应该处理除了 'a' 和 'b' 之外的其他输入（也许只需返回 0）。顶部的 #define 有点棘手，但允许您在标准C中实现生成器，带一些语法糖。Python在幕后基本上也是用其 yield 关键字做着同样的事情。 - laindir

我想避免提及的一个额外的侧面是：协程或生成器本身通常作为状态机在后台实现（其中状态是下一个恢复执行的行或指令）。我感觉我至少要指出这一点，因为在C中确实没有任何“幕后”。这就是那些#define宏真正意义所在。 - laindir

Answer 2

理论上，每个有限状态机都可以用单个协程实现，只需要以下结构之一：

• 辅助变量的测试
• 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)

- Abc