1. 问题的提出，抽象
建一，不止是他，不少人跟我讨论过这样的问题：如何才能保证在需求变更、扩充
的情况下，程序的主体部分不动呢？
这是一个非常深刻和艰难的问题。在进入实质讨论之前，我们还得先明确什么是"
主体"，就是我们不希望动的那一部分是什么。事实上，没有什么" 主体"，这是被
我们主观划分的，代码中有一部分是不动的，另一部分是动的。而追求永恒(一劳
永逸？) ，是我们的天性吧。
我们希望实现一段程序，换一些东西，游戏就由 双截龙 变成了 超级玛丽，再换
一点东西，就变成了 魂斗罗。只要招些美工，再招些脚本作者，所有的程序员就
可以--解雇了。
这看起来不太现实，那么我们来看一段类似的，但是更现实一点的。我们希望实现
一段程序，在每轮迭代/循环中，这段代码都能完成我们需要做的任 务，虽然这些
任务可能在每轮迭代中有所不同。在数学归纳法，在 sigma 符号的的周围，甚至
在积分符号的周围，都在发生这样的事情。
这些梦想或者已经实现的技术，都基于"抽象"。我们试图找到在不同的情境 (动
作、需求) 下那些相同的部分。我们对具体事件做抽象，并且期待抽象的结果适用
于所有的具体的事例。这样，原来的很多工作就成为 应用抽象的理论 的过程，不
再需要创造力，因此也不再能吸引我们。那么，我们再对抽象的结果继续抽象，直
到形而上。
2. 状态机的引擎
引擎，就是上文中提到的开发出一个游戏，然后能衍生出很多游戏的技术。代码的
核心部分、流程部分不会改变，只有数据 (甚至可以在外部文件中) 才随需求的变
化而变化。
状态机，也可以用引擎实现。实现这一目标的技术也存在已久，就是查表。查表的
经典案例是 求三角函数 (在一定精度下)，常量时间复杂度的解决方案 就是查
表。事先把三角函数在不同度数下的值都求出来，放在hash表 (?) 里。你要查哪
个度数，我就去查哪个度数对应的函数值。
在这个案例里，查表的那段代码，不随三角函数由sin变成cos或tan而发生任何变
化。这就是引擎，被查的表就是数据。
3. 接口
我们期待的接口跟前一篇普通青年中的完全一样。在主函数中调用 void
state_change(enum message m) 向状态机传递消息，用 test.in 作为测试用例。
主函数还知道，一共就这样几种消息：
enum message { play, stop, forward, backward, record, pause };
4. 状态迁移表
在讲如何查表前，我们先设计 表 本身。我们期待表格能够描述 状态迁移 中的要
素。记得么，一共4个。 (1) 当前状态， (2)当前消息， (3)将迁移到的状态，
(4)在状态迁移中的动作。我们期待能用表格，而不是如普通青年一文中用代码
(switch-case)的方式描述。因为我们相 信，改表格比改代码容易。
状态迁移表与状态迁移图完全等价。
表格看起来像下面这样，如果想像划上竖线效果更佳。。
1 struct transition fsm[transition_num] = {
2 /* current_state, message/event, next_state*/
3 {s_play, stop, s_stop},
4 {s_play, pause, s_pause},
5 {s_pause, pause, s_play},
6 {s_pause, stop, s_stop},
7 {s_stop, forward, s_forward},
8 {s_stop, play, s_play},
9 {s_stop, backward, s_backward},
10 {s_stop, record, s_record},
11 {s_forward, stop, s_stop},
12 {s_backward, stop, s_stop},
13 {s_record, stop, s_stop} };
每一行，都是一组状态迁移的匹配。第一列是当前状态，第二列是接收到的消息，
第三列是在此种情况下将迁移到的状态。每增加一个迁移的匹配，我 们就按这样
的规则增加一行。这规定了状态机迁移中4要素里的3条，剩下的那条是在迁移中的
动作，后面再介绍。
当然，为了遵循C语言的语法，我们需要在此前就定义 (1) 状态枚举、 (2) 消息
枚举，还有 (3) 迁移的结构体。如下。
1 enum state { s_stop='s', s_play='p', s_forward='f', s_backward='b',
s_pause='_', s_record='r' };
2 enum message { play, stop, forward, backward, record, pause };
3
4 struct transition {
5 enum state current;
6 enum message m;
7 enum state next;
8 };
我们还需要定义一共多少条迁移规则，是为了我们还没有写出来的代码准备的，不
过此处已经用到，所以定义如下。
1 #define transition_num 11
5. 迁移时的动作
我们希望把迁移时的动作放在每个状态到达之处。即，每个状态都可以有一些"副
作用"。这与迁移时的动作是等价的，证明略去。如果仅想在迁移时 写代码，也可
以利用这种方法实现。
状态机的动作 表格如下：
1 struct state_action state_action_map[state_num] = {
2 {s_stop, do_stop},
3 {s_play, do_play},
4 {s_forward, do_forward},
5 {s_backward, do_backward},
6 {s_pause, do_pause},
7 {s_record, do_record}};
每一行，是一个状态对应的动作。第一列是状态，第二列是对应的动作。这样，每
增加一个状态 (如果它有对应动作)，就在这里加入一行；动作对应的函数需要实
现，后面会介绍。
类似于状态迁移图，为了遵循C语言语法，我们需要在此前声明如下。
1 #define state_num 6
2 typedef void (*action_foo)() ;
3
4 enum state { s_stop='s', s_play='p', s_forward='f', s_backward='b',
s_pause='_', s_record='r' };
5
6 /* action starts */
7 void do_stop() {printf ("I am in state stop and should doing something
here.\n");}
8 void do_play() {printf ("I am in state play and should doing something
here.\n");}
9 void do_forward() {printf ("I am in state forward and should doing
something here.\n");}
10 void do_backward() {printf ("I am in state backward and should doing
something here.\n");}
11 void do_pause() {printf ("I am in state pause and should doing
something here.\n");}
12 void do_record() {printf ("I am in state record and should doing
something here.\n");}
13
14 struct state_action {
15 enum state m_state;
16 action_foo foo;
17 };
第1行，是状态的数量。第2行和第7行到第12行，以及第16行，使用了函数指针(指
向函数的指针，一个指针，它的基类型是一个函数)，用于 表示要执行的动作。第
4行，是状态枚举。第14行到第17行，是 状态-动作 对应关系的结构体。
第7行至第12行，是动作的执行部分。当增加的状态需要动作时，程序员要在此处
加入一个函数，它遵守第2行的签名约定。
6. 引擎
如果表格的数据结构已定，代码就好写了。我们的引擎代码的核心部分是查表，遍
历表格，找到与当前状态、当前消息匹配的将迁移到的状态。
我们还是自顶向下，假设 查表部分已经完成，为主函数提供与 普通青年一文相同
的接口--而内部实现是不同的。
1 void state_change(enum message m)
2 {
3 static state = s_stop;
4 enum state next;
5 int index = 0;
6
7 index = lookup_transition(state, m, fsm);
8 if(index!=ERR)
9 {
10 state = fsm[index].next;
11 lookup_action(state, state_action_map)();
12 }
13 return;
14 }
如第3行如示，初始状态是 停止。在第7行，我们引用了一个尚未写好的函
数，lookup_transition。虽然函数还不存在，不过我们能猜出来它的作用，查
表，找到 当前状态是 state，当前消息是 m 时所对应的表项的下标 index。fsm
参数是为了可能有多个状态迁移表设计的，此处可以略过。
当查找到 index 以后，且 index 不是 ERR (没找到)，就可以令 下一个状态为
state = fsm[index].next，见第10行。
以上，完成了状态迁移4要素中的3个：当前状态、当前消息、将迁移到的状态。
第11行，完成的功能是执行与状态对应的动作。这里又用到函数指针。在代码
lookup_action(state, state_action_map)() 中，lookup_action(state,
state_action_map) 用于找到状态 state 对应的动作，后面的 "()"，是因为这个
动作是一个函数指针，可以使用这样的方式执行这个指针指向的函数。与上文中的
fsm 参数类似，state_action_map是为了应对有多个状态-动作表的情况，这里可
以略过。
无论数据 (状态迁移、状态-动作)如何变化，引擎代码都不会变化。所以，甚至可
以把引擎放在静态或动态链接库里，或者把数据放在外部文件里，运行时再载入，
从而提 高部署时的灵活性。
7. 查表
刚刚用到的两个未定义的函数 lookup_transition(state, m, fsm) 和
lookup_action(state, state_action_map) 都使用了查表的方法。
代码如下。可以看出，二者的结构非常类似，遍历数组 (for循环) ，找到符合条
件的元素 (if判断)，然后把该元素的索引或者该元素结构体的某个成员返回。
ERR 和 ACTION_NOT_FOUND 是用来容错的，万一表格有误，没有查到匹配的项。
1 int const ERR = -1;
2 int lookup_transition (enum state s, enum message m, struct transition
* t)
3 {
4 int ret=ERR;
5 int i;
6 for(i=0;i<transition_num;++i)
7 {
8 if(t[i].current == s && t[i].m == m)
9 {
10 ret = i;
11 }
12 }
13 return ret;
14 }
15
16 action_foo ACTION_NOT_FOUND = NULL;
17 action_foo lookup_action(enum state s, struct state_action* a)
18 {
19 action_foo ret = ACTION_NOT_FOUND;
20 int i=0;
21 for (i=0;i<state_num;++i)
22 {
23 if(s == a[i].m_state)
24 {
25 ret = a[i].foo;
26 }
27 }
28 return ret;
29 }
8. 总结
geek青年，从接口上看，与普通青年并无不同。甚至在情况相对简单 (状态少、状
态迁移种类少) 的时候，代码量比普通青年还有不如。那么，geek青年的长处在哪
里呢？
古人云：沧海横流方显英雄本色。古人又云：大丈夫山崩于前不变色，海啸于后不
动容。
geek青年的长处在于，他始终如一，无论遇到的情形是多么糟糕多么恶劣，他始终
没有变化。这个世界上，总需要一些因素，一些承诺，不随任何 易变的感情、任
何旁人不能承受的痛苦或诱惑而变化，稳定地坚持。这才能让我们对这个世界保留
一丝希望，未来才能够和值得期待。
这一篇和上一篇的代码在这里 [http://download.csdn.net/detail/younggift
/7569627]。
--------------------
博客会手工同步到以下地址：
[http://giftdotyoung.blogspot.com]
[http://blog.csdn.net/younggift]
=======================
No comments:
Post a Comment