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

Question

我正在寻找实现 FSM 的方法，这导致我第一次遇到协程。

我看到了几个示例(here、here 和 here)，它们暗示状态机可以由单个协程实现。然而，我注意到所有这些机器的共同点是，不包括循环，它们是树——也就是说，从起始节点到每个其他节点只有一条路径(不包括循环)——并且很好地映射到层次控制流由嵌套 if 提供s。我试图建模的状态机至少有一个状态，从起始节点到它的路径不止一条(如果消除了循环，它就是一个有向无环图)。而且我无法想象什么样的控制流(除了 goto s)可以实现这一点，或者是否有可能。

或者，我可以使用单独的协程来处理每个状态并让步给某种调度程序协程。但是，我没有看到在此设置中使用协程而不是常规函数有任何特别的好处。

这是一个我无法建模的简单状态机:

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

这是我到目前为止所拥有的。最终实现将在 C++ 中使用 Boost，但我使用 Python 进行原型(prototype)设计。

#!/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)

可以修复此协程以正确建模状态机吗？或者我必须采取其他方式吗？

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