普通青年的状态机,纯C语言

state-733737

我们第一次接触到状态机,是在数字电路课程里。计数器、串行奇偶检校、 检验

三个1连续出现的报错电路 等,都需要状态机作为模型。实现这些功能的电路,与

状态机的状态转换图、状态转换表都是等价的。

后来,我们再接触状态机,是在编译原理课程里。状态机用于描述与正则表达式匹

配的字符串。

再后来,我们在GUI界面设计中,需要设置一些控件在某些条件下 禁用,某些条件

下使能,某些条件下打个对号。这也可以用状态机模型来控制。

1. 不要写成 消息响应/事件处理

状态机和消息响应都是 双层 switch-case 结构。不同的是,状态机的外层是状

态,内层是消息;消息响应外层是消息,内层是状态。

有的同学会说,那又有多大的区别呢?代码只是外在形式而非本质,它所反应的是

你对模型的理解,或者说,对于问题,你使用了哪种模型。

消息响应适合于这样的情形:有很多种消息,对于同一种消息,你的程序总是给出

同一种反应。打个比方,你女朋友喜欢吃冰淇淋,任何时候你给她 买,她都高

兴,或者转怒为喜,或者转悲为喜,总之,会置心情为"喜"。这种情形,适合用消

息响应解决。

而状态机适合于另一种情形,你的程序是"有状态的",它在不同的情况 (状态)

下,会对同一消息做出不同的反应。状态,是一种数据,但是它影响流程的行为。

按面向对象的观点,数据与流程间的这种高内聚关系,非常适合用 类 来实现。这

是题外话,我们回到女朋友和冰淇淋间的关系。你女朋友可能并非在任何情况下吃

了冰淇淋都高兴,比如刚刚吃完十个八个的时候…这与她当前的状 态有关。

状态机中,我们需要掌握的核心的数据是:当前状态,当前消息,将迁移到的状

态,在迁移中发生的动作。

在状态机代码之前,请先看一段消息响应机制,VC生成的win32api代码大抵如此。

我们随便找来一段片断看看:

1 LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam,

LPARAM lParam)

2 {

3 int wmId, wmEvent;

4 PAINTSTRUCT ps;

5 HDC hdc;

6 switch (message)

7 {

8 case WM_COMMAND:

9 wmId = LOWORD(wParam);

10 wmEvent = HIWORD(wParam);

11 case ID_MENU_GO: …. break;

12 case IDM_ABOUT: …. break;

13 case IDM_EXIT: …. break;

14 default:

15 return DefWindowProc(hWnd, message, wParam, lParam);

16 }

17 break;

18 case WM_PAINT: …. break;

19 case WM_DESTROY: … break;

20 case WM_KEYDOWN: … break;

21 default: return DefWindowProc(hWnd, message, wParam, lParam);

22 }

23 return 0;

24 }

第6行开始到第22行结束,对每个消息给出一个响应。没错,win32api也把这个传

进来的东西称为 message。这是很典型的适合消息响应机制的情形,程序对于相同

的消息,处理的方法总是相同的。

我们常常错误地把状态机写成了消息响应,消息这部分处理得不错,但是,由于没

有很好地记录和迁移状态,写起来容易把自己写糊涂了。无他,用错 了工具。拿

螺丝刀打孔,不是工具差,而是工程师选错了工具。

2. 状态机实例,录音机

实例得是相对简单的,不然我们很容易淹没在细节之中,没有足够精力去关注状态

机本身的机制了。假设我们仿真一台录音机…

我们先假设你见过录音机。录音机是一种曾经先进的设备,有一个或两个"卡",可

以放进磁带。"卡"前面有几个按键,这几个按键上的标识因为图 形简单且示意性

强,现在还在广泛使用。它们分别是 播放 > 、暂停 || 、快进 >> 、快退<< 、

录音 O 、停止 []。

这几个按键之间是有一定的"互斥关系"的。比如当播放键按下时,我们不应该能把

快进键按下。当然,淘气的同学可能这样干过,我们会听到"咔咔"的声音,然后是

家长骂败家玩艺的声音。可以就"互斥关系"开始写程序,但是我觉得这样有点 麻烦。

我们认为,这种"互斥关系"是因为录音机是"有状态的"。所以,我们打算用状态机

来实现。状态转换图是这样的。请读图的时候关注这四点:当前 状态,当前消

息,将迁移到的状态,在迁移中发生的动作 (本例中没有) 。

digraph state

{

graph [ nodesep=1.2];

rankdir = LR;

播放 -> 暂停 [label="按下 || "];

暂停 -> 播放 [label="按下 || "];

暂停 -> 停止 [label="按下 []"];

停止 -> 播放 [label="按下 >"];

播放 -> 停止 [label="按下 []"];

停止 -> 快退 [label="按下 <<"];

停止 -> 快进 [label="按下 >>"];

快进 -> 停止 [label="按下 []"];

快退 -> 停止 [label="按下 []"];

停止 -> 录音 [label="按下 O"];

录音 -> 停止 [label="按下 []"];

}

备注:我实在想不起来 暂停 和 停止 之间的关系了,似乎是这样的,又似乎不

是。反正大概是那么个意思,不影响对状态机的理解,就这么地吧。

接下来是C代码实现。

3. 接口 及 测试

看到以下代码,有的同学会说,你这不就是主程序么,为什么要把小标题叫做接

口。因为,它规定了我们的状态机函数将是什么样子的。

1 enum message { play, stop, forward, backward, record, pause };

2

3 int main(int argc, char *argv[])

4 {

5 char c=0x00;

6 while(1)

7 {

8 c = getchar();

9 switch(c)

10 {

11 case ' ': state_change(pause); break;

12 case 'p': state_change(play); break;

13 case 'r': state_change(record); break;

14 case 's': state_change(stop); break;

15 case 'f': state_change(forward); break;

16 case 'b': state_change(backward); break;

17 case 'q': return EXIT_SUCCESS;

18 }

19 }

20 return EXIT_SUCCESS;

21 }

上述代码规定了,状态机迁移函数的原型/签名是 void state_change(enum

message m)。

测试的时候,我们这样做:./state < test.intest.in的内容是"psfsbspq",测

试时期待看到输出的状态迁移过程。之所以这样做,而不是每次从控制台手动输

入,是因为每 次测试的内容都应该是相同的–相同的输入,程序有相同的反应–

可重现性。或者说,DRY原则。

一个非常值得我们注意的问题。在上述接口中,我们看不到"状态"。事实上,我们

将会定义:

enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record };

但是,接口以外的代码,是 *不应该* (是不应该,不是 不必要,是一定不要) 知

道状态的,既不应该知道当前状态,也不应该知道将要迁移到哪个状态,也不应该

知道在迁移过程中应该做什么动作。如果接口以外的代码知道了这些,就侵入了

状态机的隐私,子系统的边界就模糊了。而契约的首要任务就是规定边界,规定国

家与个人、个人与个人、个人与集体的边界。

这一原则,早在195X年,软件工程刚刚开始的时候就确立了,是最初确立的原则,

即 信息隐藏。后面的原则,都是它的儿子孙子。有个比喻讲过这个道理。当你在

超市出口付款的时候,你会自己把钱从钱夹里拿出来递给售货员,而不会转过身去

对她 说,"在我屁股兜里,你自己掏吧,别忘了把零钱放回来。"这既增加了假设

–你极端信任她,也增加了她的责任。

接口,最主要的任务就是为了明确责任,把责任分布在子系统边界两侧。其次才是

规定调用的方法,即边界长什么样。

4. 状态迁移

以下是状态机的代码片断。

1 enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record};

2 void state_change(enum message m)

3 {

4 static enum state s=s_stop;

5 switch (s)

6 {

7 case s_play:

8 if(m==stop)

9 {

10 s = s_stop;

11 printf("stop.n");

12 }

13 else if (m==pause)

14 {

15 s = s_pause;

16 printf("pause");

17 }

18 break;

我们还是要关注那四个关键点: (1) 当前状态, (2) 当前消息, (3) 将迁移到

哪个状态, (4) 迁移中会做哪些动作。

(1) 当前状态必然是第1行的枚举类型中的一个。我们初始化状态为 停止,见第4行。

在第5行到第7行,我们的双重 switch-case 的外层 按当前状态分类,如下。

5 switch (s)

6 {

7 case s_play:

下面还有很多 case,第1行的枚举类型中的每一个状态,都有一个 case。

(2) 当前消息。如果当前状态是第7行了,那么,当前消息由双层 switch-case的

内层,即第8行,第13行的 if…else if 来响应。

(3) 将迁移到哪个状态。在 s_play状态 (第7行) 接收到 stop 消息 (第8行)的

话,将迁移到 s_stop 状态,即第10行。

(4) 在迁移中会做哪些动作,如果还是这个状态这个消息,会做的动作是 第11

行,打印一段文字描述接下来的状态。

在函数 void state_change(enum message m) 中,维护了当前状态,规定了在某

种状态下-接收到某个消息,会迁移到哪个状态,在状态迁移中做哪些动作。

主函数在调用state_change时,是通过这一接口,向状态机发送一个消息;由状态

机对这个消息做出适合自己当前状态的响应–状态迁 移、动作。主函数所看到

的,是一个多彩或善变的女人,而她之所以对同一消息做出不同响应的原因,在她

的内心深入保留着,那是她不会对你说的状 态,以及状态迁移中的波澜壮阔。即

使表面上善变的状态机,也是可以理解和预测的,如果她对你倘开心扉,允许你一

行一行把附录A中的代码读完, 了解所有的 switch-case,了解所有的状态下她将

会如何响应每一种消息。

附录A 完整代码

1 #include <stdlib.h>

2 #include <stdio.h>

3

4

5 //recorder

6

7 enum state { s_stop, s_play, s_forward, s_backward, s_pause, s_record };

8 enum message { play, stop, forward, backward, record, pause };

9

10

11 void state_change(enum message m)

12 {

13 static enum state s=s_stop;

14 switch (s)

15 {

16 case s_play:

17 if(m==stop)

18 {

19 s = s_stop;

20 printf("stop.n");

21 }

22 else if (m==pause)

23 {

24 s = s_pause;

25 printf("pause");

26 }

27 break;

28 case s_pause:

29 if(m==pause)

30 {

31 s = s_play;

32 printf("play.n");

33 }

34 else if(m==stop)

35 {

36 s = s_stop;

37 printf("stop.n");

38 }

39 break;

40 case s_stop:

41 if(m==play)

42 {

43 s = s_play;

44 printf("play.n");

45 }

46 if(m==backward)

47 {

48 s = s_backward;

49 printf("backward.n");

50 }

51 if(m==forward)

52 {

53 s = s_forward;

54 printf("forward.n");

55 }

56 if(m==record)

57 {

58 s = s_record;

59 printf("record.n");

60 }

61 break;

62 case s_forward:

63 if(m==stop)

64 {

65 s = s_stop;

66 printf("stop.n");

67 }

68 break;

69 case s_backward:

70 if(m==stop)

71 {

72 s = s_stop;

73 printf("stop.n");

74 }

75 break;

76 case s_record:

77 if(m==stop)

78 {

79 s = s_stop;

80 printf("stop.n");

81 }

82 break;

83

84

85 }

86

87 }

88

89

90 int main(int argc, char *argv[])

91 {

92 char c=0x00;

93 while(1)

94 {

95 c = getchar();

96 switch(c)

97 {

98 case ' ': state_change(pause); break;

99 case 'p': state_change(play); break;

100 case 'r': state_change(record); break;

101 case 's': state_change(stop); break;

102 case 'f': state_change(forward); break;

103 case 'b': state_change(backward); break;

104 case 'q': return EXIT_SUCCESS;

105 }

106

107

108 }

109

110 return EXIT_SUCCESS;

111 }

附录B 状态图源代码 in graphviz

digraph state

{

graph [ nodesep=1.2];

rankdir = LR;

播放 -> 暂停 [label="按下 || "];

暂停 -> 播放 [label="按下 || "];

暂停 -> 停止 [label="按下 []"];

停止 -> 播放 [label="按下 >"];

播放 -> 停止 [label="按下 []"];

停止 -> 快退 [label="按下 <<"];

停止 -> 快进 [label="按下 >>"];

快进 -> 停止 [label="按下 []"];

快退 -> 停止 [label="按下 []"];

停止 -> 录音 [label="按下 O"];

录音 -> 停止 [label="按下 []"];

}

——————–

博客会手工同步到以下地址:

[http://giftdotyoung.blogspot.com]

[http://blog.csdn.net/younggift]

=======================

Leave a Reply