近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對本書內(nèi)容進(jìn)行連載。

>>>>1.1狀態(tài)機(jī)

>>>1.1.1 有限狀態(tài)機(jī)

1. 起源

自動機(jī)是計(jì)算機(jī)的簡單理論模型，通常將自動機(jī)分為有限自動機(jī)和圖靈機(jī)。盡管有限自動機(jī)更簡單，但在定義圖靈機(jī)之后數(shù)年，這個(gè)概念才被提出來。

沃倫·麥卡洛克當(dāng)時(shí)正在研究腦部創(chuàng)傷治療精神病人，他想研究出一種解釋大腦如何工作的理論。沃爾特·皮茨最初被培養(yǎng)成為一位邏輯學(xué)學(xué)者，但是卻在全新的數(shù)學(xué)生物物理學(xué)領(lǐng)域發(fā)表論文。兩人于1942年相識，認(rèn)識到他們對相同類型的問題感興趣，于是開始聯(lián)手研究彼此取長補(bǔ)短。他們發(fā)表了第一篇論文“神經(jīng)活動中內(nèi)在的思想邏輯演算”（A Logical Calculus of Ideas Immanent in Nervous Activity），在這篇論文中，他們借助細(xì)胞對神經(jīng)元進(jìn)行了建模。雖然每個(gè)細(xì)胞都有多個(gè)輸入，但只有一個(gè)輸出。一個(gè)細(xì)胞的輸出必須成為另一個(gè)細(xì)胞的輸入，輸入的類型有兩種——抑制的和興奮的。如果興奮的輸入超過了一定閾值，且沒有抑制輸入，細(xì)胞將會被激活。雖然細(xì)胞的集合和它們之間的連接被兩人稱為神經(jīng)網(wǎng)絡(luò)，但他們沒有意識到，這是大腦實(shí)際運(yùn)作的簡化模型，通過研究神經(jīng)網(wǎng)絡(luò)可以得知神經(jīng)網(wǎng)絡(luò)如何處理邏輯活動。他們的網(wǎng)絡(luò)模型與神經(jīng)元和人類的大腦具備相同的特征，因此他們希望自己的研究能夠揭示人類邏輯推理的奧秘。

他們的論文引起了計(jì)算機(jī)專家約翰·馮·諾依曼和著名的數(shù)學(xué)家、哲學(xué)家諾伯特·維納的注意，兩位學(xué)者對這篇論文印象深刻。維納看到了其中蘊(yùn)含的力量，他意識到，這一觀點(diǎn)具有廣泛的適應(yīng)性，可以發(fā)展出控制論。控制論將催生可以學(xué)習(xí)的機(jī)器的理念，反過來也會孕育人工智能。馮·諾依曼認(rèn)識到，麥卡洛克和皮茨對細(xì)胞和細(xì)胞間連接的描述，同樣可以應(yīng)用到電子組件和計(jì)算中。他在《關(guān)于EDVAC的報(bào)告》（First draft of a report on the EDVAC）一文中對此進(jìn)行了詳細(xì)的描述，正是這篇論文奠定了現(xiàn)代計(jì)算機(jī)構(gòu)建的基石。

另一個(gè)受到麥卡洛克和皮茨影響的人是馬文·明斯基，1954年明斯基在他的博士論文中對神經(jīng)網(wǎng)絡(luò)進(jìn)行了研究，展示了如何使用這些網(wǎng)絡(luò)對自動機(jī)進(jìn)行全面的描述。明斯基的著作《計(jì)算：有限和無限機(jī)器》是這一領(lǐng)域的經(jīng)典之作，高屋建瓴地描述了自動機(jī)和計(jì)算理論。通過對比物理學(xué)，明斯基在這本書的前言中解釋了這種使用理論機(jī)器研究的理論為什么能夠發(fā)揮作用。

與物理學(xué)使用統(tǒng)計(jì)定義事件的方法不同，我們是用邏輯定義的計(jì)算或表達(dá)式。它們被聯(lián)系在一起，不是通過幾何或能量性質(zhì)，而是通過它們與類似機(jī)器或類似定義之間的關(guān)系。我們能夠使用機(jī)器組件進(jìn)行簡單的交互，應(yīng)用最顯而易見的邏輯命題。面對等價(jià)的現(xiàn)實(shí)物理機(jī)器時(shí)，我們必須解決極端復(fù)雜的分析等式。

自動機(jī)被劃分為兩類：一類具有有限內(nèi)存，另一類具有無限內(nèi)存下面只研究有限的一類。

2.有限狀態(tài)機(jī)

有限狀態(tài)機(jī)（Finite State Machine，F(xiàn)SM）是一種抽象的機(jī)制， 它包括有限數(shù)量的狀態(tài)。因此FSM是一個(gè)狀態(tài)集，值的一個(gè)有限集合。

閘機(jī)是一個(gè)常見的狀態(tài)機(jī)，這是《敏捷軟件開發(fā)——原則、模式與實(shí)戰(zhàn)》一書中展示的一個(gè)經(jīng)典示例。在這里，將以香港地鐵站的閘機(jī)為例介紹有限狀態(tài)機(jī)，其用例文本摘要如下：

通常閘機(jī)默認(rèn)是關(guān)閉的，當(dāng)閘機(jī)收到有效卡信息時(shí)，則打開閘機(jī)；當(dāng)乘客通過后，則關(guān)閉閘機(jī)。如果有人非法通過，則閘機(jī)會發(fā)出連續(xù)的“滴、滴、滴……”報(bào)警聲；如果閘機(jī)已經(jīng)打開，而乘客還在刷卡，則閘機(jī)會發(fā)出“滴”的聲音提示乘客，并顯示“票價(jià)和余額，閘機(jī)已經(jīng)打開，請通過，謝謝！”

FSM會響應(yīng)“事件”而改變狀態(tài)，即將每個(gè)“事件”實(shí)現(xiàn)為一個(gè)函數(shù)，當(dāng)“事件”發(fā)生時(shí)，就意味著調(diào)用了一個(gè)函數(shù)。FSM也執(zhí)行動作產(chǎn)生輸出，所執(zhí)行的動作是當(dāng)前狀態(tài)和輸入事件的一個(gè)函數(shù)，其目的是執(zhí)行系統(tǒng)的任務(wù)。

事件是指在某個(gè)時(shí)刻發(fā)生的事情，比如，閘機(jī)的“刷卡（card）”事件和“通過（pass）”事件，狀態(tài)是系統(tǒng)的狀態(tài)。事件表示時(shí)間點(diǎn)，狀態(tài)表示時(shí)間段，狀態(tài)對應(yīng)對象接收的兩次事件之間的時(shí)間間隔。比如，閘機(jī)可能處于的狀態(tài)：Locked狀態(tài)和Unlocked狀態(tài)。

轉(zhuǎn)換是從一個(gè)狀態(tài)轉(zhuǎn)移為另一個(gè)狀態(tài)的路徑，引發(fā)它的事件被稱為事件觸發(fā)器，簡稱觸發(fā)。而轉(zhuǎn)換可以觸發(fā)動作——表示對象的某個(gè)方法的調(diào)用，比如，當(dāng)事件card發(fā)生時(shí)，閘機(jī)從Locked狀態(tài)轉(zhuǎn)換為Unlocked狀態(tài)并執(zhí)行打開閘機(jī)動作。轉(zhuǎn)換還有一個(gè)監(jiān)護(hù)條件邏輯測試——或布爾測試，只有測試通過時(shí)轉(zhuǎn)換才發(fā)生。

而事件可以是外部事件和內(nèi)部事件，外部事件是在系統(tǒng)和它的執(zhí)行者之間傳遞的事件，比如，按下一個(gè)鍵和一個(gè)來自傳感器的中斷都是外部事件。內(nèi)部事件是在系統(tǒng)內(nèi)部的對象之間傳送的事件，比如，溢出異常是一個(gè)內(nèi)部事件。可以用UML對4種事件建模：信號、調(diào)用、時(shí)間推移或狀態(tài)的一次改變。信號或調(diào)用可以帶有參數(shù)，參數(shù)值對轉(zhuǎn)移（包括監(jiān)護(hù)條件和動作的表達(dá)式）是可見的。

信號是一個(gè)異步事件，在實(shí)例間異步傳遞消息的通信規(guī)約。消息是一個(gè)具名對象，信號是消息的類型，象類一樣，信號也有屬性和操作。而信號事件是指發(fā)送或接收信號的事件，其差別在于信號是對象之間的消息，而信號事件是指在某時(shí)某刻發(fā)生的事情。

如果事件沒有產(chǎn)生任何效果，則FSM保持狀態(tài)不變。通常下一個(gè)狀態(tài)依賴于當(dāng)前狀態(tài)和輸入事件，有時(shí)狀態(tài)轉(zhuǎn)移會導(dǎo)致輸出動作。在某些情況下，雖然一個(gè)事件不會立即導(dǎo)致狀態(tài)轉(zhuǎn)換，但它會影響隨后的狀態(tài)轉(zhuǎn)換。如果事件已經(jīng)產(chǎn)生，則可以將該情況保存為一個(gè)條件，在之后進(jìn)行檢驗(yàn)。

監(jiān)護(hù)條件是由一個(gè)方括號括起來的布爾表達(dá)式，放在觸發(fā)器事件的后面。其表示法為“事件[條件]”（Event[Condition]），條件是某一段時(shí)間內(nèi)值為True或False。通常“事件”引起了“狀態(tài)轉(zhuǎn)換”，當(dāng)事件發(fā)生時(shí)，為了發(fā)生轉(zhuǎn)換，可選的“條件”的值必須為True，可選的“動作”作為結(jié)果被執(zhí)行。

動作是與狀態(tài)轉(zhuǎn)換相關(guān)的可選的輸出，動作執(zhí)行了計(jì)算（調(diào)用相應(yīng)的函數(shù)），作為狀態(tài)轉(zhuǎn)換的結(jié)果。事件導(dǎo)致狀態(tài)轉(zhuǎn)移，而動作是狀態(tài)轉(zhuǎn)移所產(chǎn)生的效果。動作在狀態(tài)轉(zhuǎn)移時(shí)被觸發(fā)，執(zhí)行后自行終止。

● 轉(zhuǎn)換動作

轉(zhuǎn)換動作是指從某一狀態(tài)轉(zhuǎn)換為另一狀態(tài)時(shí)產(chǎn)生的動作，該動作也可能發(fā)生在狀態(tài)轉(zhuǎn)換至自身狀態(tài)時(shí)。為了描述狀態(tài)圖中的動作，將狀態(tài)轉(zhuǎn)換表示為：事件/動作（Event/Action）或事件[條件]/動作（Event[Condition]/Action），比如，card/unlock。

考慮閘機(jī)狀態(tài)圖中的動作：當(dāng)事件card發(fā)生時(shí)，閘機(jī)從Locked狀態(tài)轉(zhuǎn)換為Unlocked狀態(tài)，發(fā)生在該狀態(tài)轉(zhuǎn)移中的動作是獲取card信息。作為狀態(tài)機(jī)的輸出，該動作顯示票價(jià)和余額并開鎖。

通常多個(gè)動作可以和同一個(gè)狀態(tài)轉(zhuǎn)換關(guān)聯(lián)，因?yàn)閯幼鞫际遣l(fā)執(zhí)行的，所以這些動作之間不能有任何的相互依賴關(guān)系。比如，不能同時(shí)發(fā)生兩個(gè)并發(fā)的事件——計(jì)算余額和顯示余額，因?yàn)檫@兩個(gè)動作有先后順序的依賴關(guān)系，在余額計(jì)算之前不無法顯示出來。為了避開這個(gè)問題，可以引入“計(jì)算余額”的中間狀態(tài)。動作“計(jì)算余額”在進(jìn)入該狀態(tài)時(shí)執(zhí)行，動作“顯示余額”在退出該狀態(tài)時(shí)執(zhí)行。

● 進(jìn)入動作

進(jìn)入動作是指在開始進(jìn)入該狀態(tài)時(shí)觸發(fā)的即時(shí)動作，使用保留字“進(jìn)入（entry）”表示，在狀態(tài)框里表示為“進(jìn)入/動作（entry/Action），即entry/[action-list]。”

● 退出動作

退出動作是指在離開該狀態(tài)時(shí)觸發(fā)的即時(shí)動作，使用保留字“退出（exit）”表示，在狀態(tài)框里表示為“退出/動作（exit/Action），即exit/[action-list]。”

由于狀態(tài)圖源自于用例，因此要從用例開發(fā)狀態(tài)圖。首先需要用例中的一個(gè)特定的場景，即從用例中的一條特定路徑描述對象之間的交互，正常的業(yè)務(wù)序列詳見圖 4.8（a）。

圖 4.8 閘機(jī)業(yè)務(wù)序列圖

如果閘機(jī)在Locked狀態(tài)收到card事件，則轉(zhuǎn)移到Unlocked狀態(tài)并執(zhí)行unlock動作，此時(shí)閘機(jī)將它的狀態(tài)改為Unlocked并調(diào)用unlock函數(shù)；如果閘機(jī)在Unlocked狀態(tài)收到一個(gè)pass事件，則轉(zhuǎn)移到Locked狀態(tài)并執(zhí)行l(wèi)ock動作，此時(shí)閘機(jī)將它的狀態(tài)改為Locked并調(diào)用lock函數(shù)。

如圖 4.9 (a)所示為正常的業(yè)務(wù)序列圖對應(yīng)狀態(tài)圖，由于閘機(jī)處于打開狀態(tài)或關(guān)閉狀態(tài)時(shí)，“card()”或“pass()”操作對應(yīng)的處理是不同的，因此難以用一個(gè)序列圖清晰地描繪對象交互與狀態(tài)的關(guān)系。如果以業(yè)務(wù)實(shí)體（閘機(jī)）的狀態(tài)（打開狀態(tài)或關(guān)閉狀態(tài)）為核心，將執(zhí)行者與系統(tǒng)交互的具體操作稱之為“事件”，比如，card()、pass()等。

圖 4.9 閘機(jī)狀態(tài)圖

表4.1 閘機(jī)狀態(tài)轉(zhuǎn)移表

這些圖是由狀態(tài)、事件、轉(zhuǎn)換和動作組成的有向圖，圓角矩形表示閘機(jī)的狀態(tài)，閘機(jī)始終保持狀態(tài)直到轉(zhuǎn)換促使它改變狀態(tài)。轉(zhuǎn)換用導(dǎo)向箭頭表示，通常由收到觸發(fā)事件的元素發(fā)起。當(dāng)輸入的事件與有向邊上的事件匹配時(shí)，閘機(jī)將會從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)。

其中包含了起始狀態(tài)、觸發(fā)轉(zhuǎn)移事件、終止?fàn)顟B(tài)和要執(zhí)行的動作，將其轉(zhuǎn)換為狀態(tài)轉(zhuǎn)移表的表格，詳見表 4.1。由于狀態(tài)轉(zhuǎn)移表列出了所有狀態(tài)下，接收所有事件后的狀態(tài)是如何變化的，因此很容易幫助發(fā)現(xiàn)遺漏了哪些狀態(tài)轉(zhuǎn)移。雖然狀態(tài)轉(zhuǎn)移表的優(yōu)點(diǎn)是直觀，但其缺點(diǎn)也是非常明顯的，那就是難以確認(rèn)狀態(tài)轉(zhuǎn)移的完整性。

顯然，通用狀態(tài)圖與狀態(tài)表描述狀態(tài)機(jī)的行為，開發(fā)者可以很容易檢查那些未知的，甚至沒有處理的情況。比如，閘機(jī)在Unlocked狀態(tài)下沒有處理card事件的轉(zhuǎn)移，且在Locked狀態(tài)下也沒有處理pass事件的轉(zhuǎn)移。假設(shè)如果閘機(jī)在Locked狀態(tài)收到一個(gè)非法pass事件，則狀態(tài)不變并執(zhí)行alarm動作，其業(yè)務(wù)序列圖詳見圖 4.8（b）。如果乘客不熟悉流程，當(dāng)閘機(jī)已經(jīng)轉(zhuǎn)移到Unlocked狀態(tài)時(shí)，而乘客還在刷卡（card），則閘機(jī)會發(fā)出“滴”的聲音提示乘客，并顯示“票價(jià)和余額，閘機(jī)已經(jīng)打開，請通過，謝謝！” 其業(yè)務(wù)序列圖詳見圖 4.8（c），完整的閘機(jī)狀態(tài)轉(zhuǎn)移表詳見表 4.2。

表4.2 完整的閘機(jī)狀態(tài)轉(zhuǎn)移表

在關(guān)閉狀態(tài)下，當(dāng)需要增加報(bào)警功能時(shí)，只需要新增一條事件/動作線，詳見圖 4.9(b)。同理，增加一條事件/動作線表示閘門在已經(jīng)打開時(shí)繼續(xù)刷卡的情況，詳見圖 4.9(c)。由于這兩種情況不會改變閘機(jī)的狀態(tài)，因此導(dǎo)向箭頭起始和結(jié)束均為同一狀態(tài)。