青梅梦呓

和世界交手的这许多年,你是否光彩依旧,兴致盎然

0%

Go实现有限状态机

有限状态机(FSM)是计算的基本概念,在现实生活中发现许多FSM行为,例如自动售货机,电梯,交通信号灯等。基于FSM的编程也是建模复杂状态转换的强大工具,它可以大大简化我们的程序。

什么是有限状态机

有限状态机(FSM)或简称为状态机,是计算的数学模型。它是一种抽象机器,在任何给定时间都可以恰好处于有限数量的状态之一。FSM可以响应某些输入而从一种状态更改为另一种状态。从一种状态到另一种状态的变化称为过渡。
— 维基百科

FSM由三个关键元素组成:初始状态,所有可能状态的列表,触发状态转换的输入。
让我们将旋转栅栏作为FSM建模的简单示例。

维基百科的旋转栅栏状态图

像其他FSM一样,旋转闸门的状态机包含三个元素:

  • 其初始状态为“锁定”
  • 它有两个可能的状态:“锁定”和“解锁”
  • 有两个输入将触发状态更改:“Push”和“Coin”

Go建立基于FSM的程序

将构建一个命令行程序来模拟旋转栅门的行为。程序启动时,提示用户键入一些命令,然后它将根据输入的命令更改其状态。

版本一 简单形式实现FSM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package main

import (
"bufio"
"fmt"
"log"
"os"
"strings"
)

// State the FSM state for turnstile
type State uint32

const (
// Locked locked state
Locked State = iota
// Unlocked unlocked state
Unlocked
)

const (
// CmdCoin command coin
CmdCoin = "coin"
// CmdPush command push
CmdPush = "push"
)

func main() {
state := Locked
reader := bufio.NewReader(os.Stdin)
prompt(state)

for {
cmd, err := reader.ReadString('\n')
if err != nil {
log.Fatalln(err)
}
cmd = strings.TrimSpace(cmd)

switch state {
case Locked:
if cmd == CmdCoin {
fmt.Println("unlocked, ready for pass through")
state = Unlocked
} else if cmd == CmdPush {
fmt.Println("not allowed, unlock first")
} else {
fmt.Println("unknown command, try again please")
}
case Unlocked:
if cmd == CmdCoin {
fmt.Println("well, don't waste your coin")
} else if cmd == CmdPush {
fmt.Println("pass through, shift back to locked")
state = Locked
} else {
fmt.Println("unknown command, try again please")
}
}
}
}

func prompt(s State) {
m := map[State]string{
Locked: "Locked",
Unlocked: "Unlocked",
}
fmt.Printf("current state is [%s], please input command [coin|push]\n", m[s])
}

首先,定义两个状态(Locked & Unlocked)和两个有效命令(CmdCoin & CmdPush)。在函数中main,我们将初始状态设置为Locked,向用户打印使用情况信息。然后开始主循环,从中读取命令字符串stdin,根据当前状态处理该命令。

您可能会注意到,我们必须为每个状态处理未知命令,这可以通过较小的重构得到改善。此外,如果将状态转换逻辑提取到函数中,则程序将更具表现力。

版本二 重构代码以使得更加清晰

在主循环中我们只关心,输入的有效命令和初始状态,完全可以将状态装换的逻辑代码抽成一个单独的函数,具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package main

import (
"bufio"
"fmt"
"log"
"os"
"strings"
)

// State the FSM state for turnstile
// 指出FSM的状态以便表示旋转门
type State uint32

const (
// Locked locked state
// 锁定状态
Locked State = iota
// Unlocked unlocked state
// 解锁状态
Unlocked
)

const (
// CmdCoin command coin
// 命令CmdCoin表示coin输入
CmdCoin = "coin"
// CmdPush command push
// 命令CmdPush表示push输入
CmdPush = "push"
)

func main() {
state := Locked
reader := bufio.NewReader(os.Stdin)
prompt(state)
for {
cmd, err := reader.ReadString('\n')
if err != nil {
log.Fatalln(err)
}
state = step(state, strings.TrimSpace(cmd))
}
}

func step(state State, cmd string) State {
if cmd != CmdCoin && cmd != CmdPush {
fmt.Println("unknown command, try again please")
return state
}

switch state {
case Locked:
if cmd == CmdCoin {
fmt.Println("unlocked, ready for pass through")
state = Unlocked
} else {
fmt.Println("not allowed, unlock first")
}
case Unlocked:
if cmd == CmdCoin {
fmt.Println("well, don't waste your coin")
} else {
fmt.Println("pass through, shift back to locked")
state = Locked
}
}
return state
}

func prompt(s State) {
m := map[State]string{
Locked: "Locked",
Unlocked: "Unlocked",
}
fmt.Printf("current state is [%s], please input command [coin|push]\n", m[s])
}

实际上,状态机通常由State-Transition Table表示,对于我们的旋转门示例,该表如下所示:
维基百科的状态转换表

我们可以使用转换表来实现FSM

版本三 状态转换表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package main

import (
"bufio"
"fmt"
"log"
"os"
"strings"
)

// State the FSM state for turnstile
// 指出FSM的状态以便表示旋转门
type State uint32

const (
// Locked locked state
// 锁定状态
Locked State = iota
// Unlocked unlocked state
// 解锁状态
Unlocked
)

const (
// CmdCoin command coin
// 命令CmdCoin表示coin输入
CmdCoin = "coin"
// CmdPush command push
// 命令CmdPush表示push输入
CmdPush = "push"
)

func main() {
state := Locked
reader := bufio.NewReader(os.Stdin)
prompt(state)
for {
// read command from stdin
cmd, err := reader.ReadString('\n')
if err != nil {
log.Fatalln(err)
}

// get function from transition table
//从状态转换表里面获取状态
tupple := CommandStateTupple{strings.TrimSpace(cmd), state}

if f := StateTransitionTable[tupple]; f == nil {
fmt.Println("unknown command, try again please")
} else {
f(&state)
}
}
}

// CommandStateTupple tupple for state-command combination
// 状态命令组合的元组
type CommandStateTupple struct {
Command string
State State
}

// TransitionFunc transition function
// 状态转换函数
type coin func(state *State)

// StateTransitionTable trsition table
//状态转换表
var StateTransitionTable = map[CommandStateTupple]TransitionFunc{
{CmdCoin, Locked}: func(state *State) {
fmt.Println("unlocked, ready for pass through")
*state = Unlocked
},
{CmdPush, Locked}: func(state *State) {
fmt.Println("not allowed, unlock first")
},
{CmdCoin, Unlocked}: func(state *State) {
fmt.Println("well, don't waste your coin")
},
{CmdPush, Unlocked}: func(state *State) {
fmt.Println("pass through, shift back to locked")
*state = Locked
},
}

func prompt(s State) {
m := map[State]string{
Locked: "Locked",
Unlocked: "Unlocked",
}
fmt.Printf("current state is [%s], please input command [coin|push]\n", m[s])
}

使用这种方法,所有可能的转换都在表中列出。易于维护和理解。如果需要新的转换,只需添加一个表条目。
由于FSM是抽象机器,因此我们可以更进一步,并以面向对象的方式实现它。

版本四 使用类对FSM进行建模

Turnstile引入了一个新类,它具有一个属性State,即名为的方法ExecuteCmd。
触发状态转换的唯一方法是调用方法ExecuteCmd。
该关系可以用下面的图表示:

oop类图

重新写一下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package main

import (
"bufio"
"fmt"
"log"
"os"
"strings"
)

// State the FSM state for turnstile
type State uint32

const (
// Locked locked state
Locked State = iota
// Unlocked unlocked state
Unlocked
)

const (
// CmdCoin command coin
CmdCoin = "coin"
// CmdPush command push
CmdPush = "push"
)

// Turnstile the finite state machine
type Turnstile struct {
State State
}

// ExecuteCmd execute command
func (p *Turnstile) ExecuteCmd(cmd string) {
// get function from transition table
tupple := CmdStateTupple{strings.TrimSpace(cmd), p.State}
if f := StateTransitionTable[tupple]; f == nil {
fmt.Println("unknown command, try again please")
} else {
f(&p.State)
}
}

func main() {
machine := &Turnstile{State: Locked}
prompt(machine.State)
reader := bufio.NewReader(os.Stdin)

for {
// read command from stdin
cmd, err := reader.ReadString('\n')
if err != nil {
log.Fatalln(err)
}

machine.ExecuteCmd(cmd)
}
}

// CmdStateTupple tupple for state-command combination
type CmdStateTupple struct {
Cmd string
State State
}

// TransitionFunc transition function
type TransitionFunc func(state *State)

// StateTransitionTable trsition table
var StateTransitionTable = map[CmdStateTupple]TransitionFunc{
{CmdCoin, Locked}: func(state *State) {
fmt.Println("unlocked, ready for pass through")
*state = Unlocked
},
{CmdPush, Locked}: func(state *State) {
fmt.Println("not allowed, unlock first")
},
{CmdCoin, Unlocked}: func(state *State) {
fmt.Println("well, don't waste your coin")
},
{CmdPush, Unlocked}: func(state *State) {
fmt.Println("pass through, shift back to locked")
*state = Locked
},
}

func prompt(s State) {
m := map[State]string{
Locked: "Locked",
Unlocked: "Unlocked",
}
fmt.Printf("current state is [%s], please input command [coin|push]\n", m[s])
}

总结

简单学习了FSM的概念并构建了一个基于FSM的Go程序,实现了这个程序的四个版本:

  • v1,以简单的形式实现FSM。
  • 进行一些重构,抽出函数以减少代码重复
  • 使用状态转换表
  • 采用OOP的方式进行重构

状态机的思想在编码中还是会遇到,例如解耦一些复杂的任务,实现接口幂等,分解程序逻辑,使得代码更急清晰等等。