基于状态的编程

写在前面

---

在写算法的时候，我们应该会特别注意算法执行过程中每一步的“状态”如何，以及下一步“状态”将会发生什么样的改变——在DP、traceback的过程中我们尤其强调这一点。事实上，“状态”这个词可以推而广之，不仅局限在算法的范围内——一个被离散化的连续过程的每一个“切片”都有一个“状态”。这篇文章就从状态着手，来说明一些编程上的问题。

正文

---

状态驱动

Code Talks :)

// 声明
struct Cond;
struct State;
struct Character;

// 条件
struct Cond
{
	std::string m_condDesc;
	bool operator<(const Cond& right) const
	{
		return strcmp(this->m_condDesc.c_str(), right.m_condDesc.c_str()) < 0;
	}
	bool operator==(const Cond& right) const
	{
		return strcmp(this->m_condDesc.c_str(), right.m_condDesc.c_str()) == 0;
	}
	void thisCond() { printf("%s!\n",m_condDesc.c_str()); }
	Cond(const char* desc) { m_condDesc = desc; }
	virtual ~Cond() {}
};
// 状态
struct State
{
	std::map<Cond, State* > m_nextStates;
	std::string  m_stateDesc;
	virtual void handleState(Character* c) = 0;
};
// 状态接受者
struct Character
{
	std::string m_name;
	State* m_preState;
	State* m_curState;
	void ReceiveCond(Cond* c)	{
	
		auto it = m_curState->m_nextStates.find(* c);
		auto end = m_curState->m_nextStates.end();
		if (it != end)
		{
			m_preState = m_curState;
			m_curState = it->second;
			c->thisCond();
		}
	}
	void HandleCurState()	{
	
		m_curState->handleState(this);
	}
	void SetStart(State* s)	{
	
		m_preState = NULL;
		m_curState = s;
	}
	Character(const char* name) :m_name(name) {}
};
//Character的一些具体状态
struct fullOfPowerState : public State
{
	void handleState(Character* c) { printf("Mr.%s is full of power!\n", c->m_name.c_str()); }
};

struct hungryState : public State
{
	void handleState(Character* c) { printf("Mr.%s is hungry now, bread him.\n", c->m_name.c_str()); }
};

struct thirstyState : public State
{
	void handleState(Character* c) { printf("Mr.%s is thirsty now, water him.\n", c->m_name.c_str()); }
};

struct tiredState : public State
{
	void handleState(Character* c) { printf("Mr.%s is tired now, let him have a rest.\n", c->m_name.c_str()); }
};

int main(int argc, char const * argv[]) {
	//定义一些状态
	fullOfPowerState power;
	hungryState hungry;
	thirstyState thirsty;
	tiredState tired;
	//定义状态转移条件
	Cond hungryCond("hungry");
	Cond thirstyCond("thirsty");
	Cond tiredCond("tired");
	Cond breadCond("bread");
	Cond waterCond("water");
	Cond restCond("rest");
	//构建状态转移图
	power.m_nextStates.insert(std::pair<Cond,State* >(hungryCond,&hungry));
	power.m_nextStates.insert(std::pair<Cond, State* >(thirstyCond, &thirsty));
	power.m_nextStates.insert(std::pair<Cond, State* >(tiredCond, &tired));

	hungry.m_nextStates.insert(std::pair<Cond, State* >(breadCond, &power));

	thirsty.m_nextStates.insert(std::pair<Cond, State* >(waterCond, &power));

	tired.m_nextStates.insert(std::pair<Cond, State* >(restCond, &power));
	printf("\nNow Mr.K's turn\n");
	//角色Mr.K
	Character Mr_K("K");
	Mr_K.SetStart(&power);
	//Let Mr.K go
	Mr_K.HandleCurState();
	//饥饿
	Mr_K.ReceiveCond(&hungryCond);
	Mr_K.HandleCurState();
	Mr_K.ReceiveCond(&breadCond);
	Mr_K.HandleCurState();
	//干渴
	Mr_K.ReceiveCond(&thirstyCond);
	Mr_K.HandleCurState();
	Mr_K.ReceiveCond(&waterCond);
	Mr_K.HandleCurState();
	//疲累
	Mr_K.ReceiveCond(&tiredCond);
	Mr_K.HandleCurState();
	Mr_K.ReceiveCond(&restCond);
	Mr_K.HandleCurState();
	printf("\nNow Mr.A's turn\n");
	//角色Mr.A
	Character Mr_A("A");
	Mr_A.SetStart(&hungry);
	//Let Mr.A go
	Mr_A.HandleCurState();
	//补充面包
	Mr_A.ReceiveCond(&breadCond);
	Mr_A.HandleCurState();

	system("pause");
	return 0;

从代码中可以看到，基于状态要求把“主体”的一部分行为提取出来放到与它相关的状态之中，根据当前“外界”传递给“主体”的条件来控制其对应的行为。
上面程序的状态转移图如下，还是比较简单的：

            rest cond          +-----------+
   +-------------------------  |           |
   | +---------------------->  |   tired   |
   | |      tired cond         |           |
   | |                         +-----------+
   | |
   ↓ |
+----------+      hungry cond    +-----------+
|          |   ----------------> |           |
|full power|                     |   hungry  |
|          |   <---------------- |           |
+----------+      bread cond     +-----------+
   ↑ |
   | |
   | |                         +-----------+
   | |       tirsty cond       |           |
   | +-----------------------> |  thirsty  |
   +-------------------------- |           |
             water cond        +-----------+

接下来，我们来看一下另外一张图：

将上图中的if判断语句单独提取出来，放置到代码块的转移边上，再次体会一下：

             +-----------+
             |   i = 1   | <----+
             +-----------+      |
               |      |     (v > 20)
       (u < v) |  (u >= v)      |
+---------+    |      |         |
|  i = 2  | <--+      +-> +--------+
|  u += 1 | ------------> | v -= 1 |
+---------+               +--------+
                              |
                          (v <= 20)
             +-----------+    |
             |   j = 1   | <--+
             +-----------+

对比之下我们可以看出即便是一个普通的过程式代码，一样可以被认为是由状态组成的。而对于函数调用，我们可以这样理解：将函数视作一个节点，而caller执行call和callee执行ret都是转移的一条边。这个模型还可以进一步套用到OS的工作过程中：cpu的每次trap都有一个条件（外部中断或者异常）来触发，进而使得操作系统在各个状态之间来回切换来完成工作。

回忆一下前面表驱动与面向对象编程一文中提到的“OO中的类以及其继承关系可以认为是一个转发表”，我们可以看出实际上“State”与“Policy”在本质上其实并无二致，实质上都是对不同过程的组织而已，只不过它们在设计方法上不同，以满足不同场景的需求而已。

其实谈到这里我们其实应当具有了一些函数式编程的基础：在函数式编程中，函数作为第一等实体，跟我们前面经常谈到的“过程”是一脉同出，最大的区别在于两点：

• 类型、term（或者说symbol），两者在函数式编程中是分离的；而在C/C++ like的语言中，绝大部分时候两者之间是视为一体的。
• C++中，任何时候的操作都是在一个值上面，这使得很多时候人们会将值与过程分开看待；而在函数式编程中函数本身也被视为是一个值（其实可以换一个角度去理解：对值的操作其实是对一段内存的操作；代码本身就需要被放置在代码段，自然可以被视为是一个值。当然由于代码段是只读的，那么我们可以对它的一个副本进新操作，操作这个副本在计算机看来跟操作一个值并没有什么区别）。

状态机

---

提到状态就不能不提状态机，我们最常听到的就是图形库以及词法/语法分析时候的状态机。实际上，前面的C++代码就是一个微型的状态机的例子。这里再举例简单的例子说明一个我个人入门时用的基于tire树的状态机，该结构可以用来解决多模板的字符串匹配问题（该问题可以在刘汝佳《算法竞赛入门经典——训练指南》中“实用数据结构——Aho-Corasick自动机”部分找到）。这里用它来说明词法分析的大致过程（嗯，我需要学习一下怎么制图了，用ASCII作画好低效劣质……）。

假设我们有6个关键字[if, ifel, int, for, foreach, float]，那么我们的Token状态可以有[TK_IF, TK_IFEL, TK_FOR, TK_FOREACH, TK_ID, TK_INT, TK_FLOAT, TK_START, TK_END]。

对于6个关键字我们可以首先将其组织为一个tire树：

然后把状态加到节点上，把tire中的字符作为转移条件放到边上：

OK，这样一个简单的有限状态机就构建好了，注意对于不存在的字符边，状态被导入到TK_START以便状态机重新运作。一段这样的字符串：if float for int forint将会得到下面的Tokens：

lexeme: if, state: TK_IF
lexeme: float, state: TK_FLOAT
lexeme: for, state: TK_FOR
lexeme: int, state: TK_INT
lexeme: forint, state: TK_ID

当然这只是简单的示例，实际代码的情况要处理一些边界情况才能得到满意的结果。

后记

---

回头看了一下最近写的三篇，结果发现高中毕业不写作文之后表达能力严重退化，连个重点都没有了…还是先考虑考虑怎么把话说清楚吧。之前写过的一些代码也该整理整理发上去了——这些代码基本都将会被重写一遍，其过程将在后面的博文中体现出来。