層次狀态機

出處：http://xlambda.com/blog/2014/11/04/hierarchical-state-machine/

計算機程式是寫給人看的，隻是順便能運作。

—— 《計算機程式的構造和解釋》 [1]

FSM

在計算機領域，FSM(有限狀态機)是一個在自動機理論和程式設計實踐中很常見的術語，簡單來說，有限狀态機表示的是系統根不同輸入/不同條件在各個狀态之間進行跳轉的模型。可以通過圖或表來描述有限狀态機，這種圖或表一般被稱為狀态圖/狀态轉移圖(State Chart)或狀态轉移表。因為圖更加直覺，本文統一使用狀态圖來描述有限狀态機。

在狀态圖裡面，一般用圓圈或方框來表示狀态，用箭頭來表示狀态之間的跳轉，箭頭可以帶上跳轉需要的輸入或條件，也可以帶附帶其它描述。一個從空白處引出，沒有源狀态的箭頭則表示整個系統的啟動，啟動後進入的第一個狀态可以稱為開始狀态，可以用雙重圓圈特别标出。整個狀态圖就是一個有圓圈，箭頭及描述的有向圖形。下面是一個簡單例子。

層次狀态機

上圖表示一個接受二進制輸入(輸入為0或者1)，計算輸入包含奇數還是偶數個0的狀态機。其中S1狀态表示”偶數個0”，S2表示”奇數個0”。系統啟動後，沿着圖中最左邊的箭頭進入S1狀态，此時沒有讀入任何輸入（0個0）。S1圓圈上方帶1的箭頭表示如果輸入是1，則跳轉到S1，即保持原狀态不變。如果輸入是0，則跳轉到S2。其它箭頭也可以類似了解。當全部輸入都處理完之後，隻需看目前狀态是S1還是S2即可得出結論：輸入具有奇數個0還是偶數個0。

由于狀态機可以将問題整體的分解成各個部分狀态及跳轉，直覺地對系統進行模組化，是以它不僅被用于理論研究過程當中，而且被廣泛用于程式設計實踐，在作業系統，網絡協定棧，各種分布式應用中都可以見到它的身影。

程式設計中的FSM

由上面的表述我們得知，FSM是對系統的模組化，是将問題/解決方案以一種條理化系統化的方式表達出來，映射到人的認知層面，而要在程式中表達FSM，也需要一定的模組化工具，即用某種代碼編寫的方式(或稱之為FSM模式)，将FSM以一種條理化系統化的方式映射到代碼層面。在程式設計領域，到底有哪些常用的FSM實作方式呢？下面我們來做一個簡單的回顧。

從簡單到複雜，下面我們浏覽一下常見的幾種FSM實作模式[2]。

a. 嵌套if-else/switch模式

自從1960年第一個Lisp實作引入條件表達式以來， if-else/switch語句 [3]已經成為每個程式員手頭必備的工具，每當需要”根據不同條件進入不同分支”，就搬出它來組織代碼，這與FSM裡面”狀态之間根據不同輸入進行跳轉”的概念有簡單的對應關系，這就使得if-else/switch語句成為人們要表達FSM時最先選擇的方式。

仍然以圖1例子進行說明，我們用if-else/switch語句編寫它的實作代碼，用一個變量state表示目前狀态，state可以取兩個值S1, S2，輸入input表示下一個輸入的數字是0還是1，那麼就有下列代碼[4]:

type State int
type Input int

var (
	StateS1 State =  + iota
	StateS2 State
)

var (
	Zero Input = 
	One  Input = 
)

var state = StateS1

func NumberOfZero(i Input) {
	switch state {
	case StateS1:
		switch i {
		case Zero:
			state = StateS2
		case One:
		}
	case StateS2:
		switch i {
		case Zero:
			state = StateS1
		case One:
		}
	}
}

上面的代碼有一個明顯的嵌套形式的結構，最外層的

switch

語句是根據目前狀态state變量進入不同的分支，内層

switch

針對的則是輸入，所有代碼像挂在衣櫃中的衣服一樣從上到下一一陳列，結構比較清晰。這種嵌套形式if-else/switch語句的FSM代碼組織方式，我們将其稱之為嵌套if-else/switch 模式。由于這種模式實作起來比較直覺簡明，是以它最為常見。

嵌套if-else/switch具有形式嵌套，代碼集中化的特點，它隻适合用來表達狀态個數少，或者狀态間跳轉邏輯比較簡單的FSM。嵌套意味着縮進層次的疊加，一個像圖1那麼簡單的實作就需要縮進4層，如果狀态間的邏輯變得複雜，所需要的縮進不斷疊加，代碼在水準方向上會發生膨脹；集中化意味着如果狀态個數增多，輸入變複雜，代碼從垂直方向上會發生指數級别的膨脹。即使通過簡化空分支，抽取邏輯到命名函數[5]等方法來”壓縮”水準/垂直方向上的代碼行數，依然無法從根本上解決膨脹問題，代碼膨脹後造成可讀性和可寫性的急劇下降，例如某個狀态裡面負責正确設定20個相關變量，而下翻了幾屏代碼之後，下面的某個狀态又用到上面20個變量裡面其中的5個，整個代碼像一鍋粥一樣粘糊在一起，變得難于了解和維護。

a. 狀态表

另一個比較流行的模式是狀态表模式。狀态表模式是指将所有的狀态和跳轉邏輯規劃成一個表格來表達FSM。仍然以圖1為例子，系統中有兩個狀态S1和S2，不算自跳轉，S1和S2之間隻有兩個跳轉，我們用不同行來表示不同的狀态，用不同的列來表示不同的輸入，那麼整個狀态圖可以組織成一張表格：

State\Input	Zero	One
S1	DoSomething, S2	null
S2	DoSomething, S1	null

對應S1行, Zero列的”DoSomething, S2”表示當處于狀态S1時，如果遇到輸入為Zero，那麼就執行動作DoSomething，然後跳轉到狀态S2。由于圖1的例子狀态圖非常簡單，DoSomething動作為空，這裡将它特别的列出來隻是為了說明在更一般化的情況下如果有其它邏輯可以放到這裡來。根據這個狀态表，我們可以寫出下列代碼：

type State int
type Input into

const (
	StateUndefined State =  + iota
	StateS1
	StateS2
)

var (
	Zero Input = 
	One  Input = 
)

type Action func(i Input)

func DoSomething1(_ Input) {
	// Do nothing here
}

func DoSomething2(_ Input) {
	// Do nothing here
}

type Item struct {
	Action    Action
	NextState State
}

var StateTable = [][]*Item{
	[]*Item{
		&Item{
			Action:    DoSomething1,
			NextState: StateS2,
		},
		nil,
	},
	[]*Item{
		&Item{
			Action:    DoSomething2,
			NextState: StateS1,
		},
		nil,
	},
}

var state = StateS1

func NumberOfZero(i Input) {
	item := StateTable[int(state)][int(i)]
	if item != nil {
		item.Action(i)
		if item.NextState != StateUndefined {
			state = item.NextState
		}
	}
}

從上述例子我們可以看到，用這種方式實作出來的代碼跟畫出來的狀态表有一個直覺的映射關系，它要求程式員将狀态的劃分和跳轉邏輯細分到一定的合适大小的粒度，事件驅動的過程查找是對狀态表的直接下标索引，性能也很高。狀态表的大小是不同狀态數量S和不同輸入數量I的一個乘積 S * I，在常見的場景中，這張狀态表可能十分大，占用大量的記憶體空間，然而中間包含的有效狀态跳轉項卻相對少，也就是說狀态表是一個稀疏的表。

c. 狀态模式

在OOP的設計模式 [6]中，有一個狀态模式可以用于表達狀态機。狀态模式基于OOP中的代理和多态。父類定義一系列通用的接口來處理輸入事件，做為狀态機的對外接口形态。每個包含具體邏輯的子類各表示狀态機裡面的一個狀态，實作父類定義好的事件處理接口。然後定義一個指向具體子類對象的變量标記目前的狀态，在一個上下文相關的環境中執行此變量對應的事件處理方法，來表達狀态機。依然使用上述例子，用狀态模式編寫出的代碼如下：

type Input int

const (
	Zero Input =  + iota
	One
)

type State interface {
	OnEventZero(i Input)
	OnEventOne(i Input)
}

var (
	S1 = "S1"
	S2 = "S2"
)

type StateS1 struct {
	c *Context
}

func (self *StateS1) OnEventZero(i Input) {
	self.doSomething1(i)
	self.c.Tran(S2)
}

func (self *StateS1) OnEventOne( Input) {
	// do nothing here
}

func (self *StateS1) doSomething1( Input) {
	// do nothing here
}

type StateS2 struct {
	c *Context
}

func (self *StateS2) OnEventZero(i Input) {
	self.doSomething2(i)
	self.c.Tran(S1)
}

func (self *StateS2) OnEventOne( Input) {
	// do nothing here
}

func (self *StateS2) doSomething2( Input) {
	// do nothing here
}

type Context struct {
	allStates    map[string]State
	currentState State
}

func NewContext() *Context {
	object := &Context{}
	states := make(map[string]State)
	states[S1] = &StateS1{c: object}
	states[S2] = &StateS2{c: object}
	object.allStates = states
	object.currentState = states[S1]
	return object
}

func (self *Context) Tran(nextState string) {
	if s, ok := self.allStates[nextState]; ok {
		self.currentState = s
	}
}

func (self *Context) Handle(i Input) {
	switch i {
	case Zero:
		self.currentState.OnEventZero(i)
	case One:
		self.currentState.OnEventOne(i)
	}
}

var context = NewContext()

func NumberOfZero(i Input) {
	context.Handle(i)
}

狀态模式将各個狀态的邏輯局部化到每個狀态類，事件分發和狀态跳轉的性能也很高，記憶體使用上也相當高效，沒有稀疏表浪費記憶體的問題。它将狀态和事件通過接口繼承分隔開，實作的時候不需要列舉所有事件，添加狀态也隻是添加子類實作，但要求有一個context類來管理上下文及所有相關的變量，狀态類與context類之間的通路多了一個間接層，在某些語言裡面可能會遇到封裝問題(比如在C++裡面通路private字段要使用friend關鍵字)。

5. 優化的FSM實作

結合上述幾種FSM實作模式，我們可以得到一個優化的FSM實作模式，它用對象方法表示狀态，将狀态表嵌套到每個狀态方法中，是以它包含了上述幾種模式的優點：事件和狀态的分離，高效的狀态跳轉和記憶體使用，直接的變量通路，直覺而且擴充友善。用它重寫上述例子，得到下述的代碼：

type Input int

const (
	Zero Input =  + iota
	One
)

type EventType uint32

const (
	EventInitialize EventType =  + iota
	EventFinalize
	EventStateEntry
	EventStateExit
	EventUser
)

type Event interface {
	Type() EventType
}

type FSMEvent struct {
	T EventType
}

func (self *FSMEvent) Type() EventType {
	return self.T
}

var (
	FSMEvents = []*FSMEvent{
		&FSMEvent{
			T: EventInitialize,
		},
		&FSMEvent{
			T: EventFinalize,
		},
		&FSMEvent{
			T: EventStateEntry,
		},
		&FSMEvent{
			T: EventStateExit,
		},
	}
)

type FSM interface {
	Init()
	Dispatch(i Input)
	Tran(target string)
}

type State func(e Event)

const (
	EventInput EventType = EventUser +  + iota
)

type InputEvent struct {
	T EventType
	I Input
}

func NewInputEvent(i Input) *InputEvent {
	return &InputEvent{
		T: EventInput,
		I: i,
	}
}

func (self *InputEvent) Type() EventType {
	return self.T
}

type BaseFSM struct {
	AllStates map[string]State
	S         State
}

func NewBaseFSM() *BaseFSM {
	return &BaseFSM{}
}

func (self *BaseFSM) Register(name string, state State) {
	self.AllStates[name] = state
}

func (self *BaseFSM) InitState(s State) {
	self.S = s
	self.S(FSMEvents[EventInitialize])
}

func (self *BaseFSM) Dispatch(i Input) {
	self.S(NewInputEvent(i))
}

func (self *BaseFSM) Tran(target string) {
	s, ok := self.AllStates[target]
	if !ok {
		panic("invalid target state")
	}
	self.S(FSMEvents[EventStateExit])
	self.S = s
	self.S(FSMEvents[EventStateEntry])
}

type ZeroCounter struct {
	*BaseFSM
	count int
}

func NewZeroCounter() *ZeroCounter {
	return &ZeroCounter{
		BaseFSM: NewBaseFSM(),
		count:   ,
	}
}

func (self *ZeroCounter) Init() {
	self.Register("S1", self.S1)
	self.Register("S2", self.S2)
	self.InitState(self.S1)
}

func (self *ZeroCounter) S1(e Event) {
	switch e.Type() {
	case EventInitialize:
	case EventStateEntry:
	case EventStateExit:
	case EventInput:
		event,  := e.(*InputEvent)
		if event.I == Zero {
			self.count++
			self.Tran("S2")
		}
	}
}

func (self *ZeroCounter) S2(e Event) {
	switch e.Type() {
	case EventStateEntry:
	case EventStateExit:
	case EventInput:
		event,  := e.(*InputEvent)
		if event.I == Zero {
			self.count++
			self.Tran("S1")
		}
	}
}

var (
	counter *ZeroCounter
)

func init() {
	counter := NewZeroCounter()
	counter.Init()
}

func NumberOfZero(i Input) {
	counter.Dispatch(i)
}

在這種模式中可以添加整個狀态機的初始化動作，每個狀态的進入/退出動作。上述代碼中

ZeroCounter.S1()

方法的

case EventInitialize

分支可以放入狀态機的初始化邏輯，每個狀态方法的

case EventStateEntry

和

case EventStateExit

分支可以放入對應狀态的進入/退出動作。這是一個重要的特性，在實際狀态機程式設計中每個狀态可以定制進入/退出動作是很有用的。

6. HSM

上述幾種模式中，狀态之間都是互相獨立的，狀态圖沒有重合的部分，整個狀态機都是平坦的。然而實際上對很多問題的狀态機模型都不會是那麼簡單，有可能問題域本身就有狀态嵌套的概念，有時為了重用大段的處理邏輯或代碼，我們也需要支援嵌套的狀态。這方面一個經典的例子就是圖形應用程式的編寫，通過圖形應用程式的架構(如MFC, GTK, Qt)編寫應用程式，程式員隻需要注冊少數感興趣的事件響應，如點選某個按鈕，大部分其它的事件響應都由預設架構處理，如程式的關閉。用狀态機來模組化，架構就是父狀态，而應用程式就是子狀态，子狀态隻需要處理它感興趣的少數事件，大部分事件都由向上傳遞到架構這個父狀态來處理，這兩種系統之間有一個直覺的類比關系，如下圖所示：

層次狀态機

這種事件向父層傳遞，子層繼承了父類行為的結構，我們将其稱為行為繼承，以差別開OOP裡面的類繼承。并把這種包含嵌套狀态的狀态機稱為 HSM(hierarchical state machine) ，層次狀态機。

加上了對嵌套狀态的支援之後，狀态機的模型就可以變得任意複雜了，大大的擴大了狀态機的适用場景和範圍，如此一來用狀态機對問題模組化就好比用OOP對系統進行程式設計：識别出系統的狀态及子狀态，并将邏輯固化到狀态及它們的跳轉邏輯當中。

那麼在狀态機實作模式裡如何支援嵌套狀态呢？從整個狀态圖來看，狀态/子狀态所形成的這張大圖本質上是一個單根的樹結構，每個狀态圖有一個根結點top，每個狀态是一個樹結點，可以帶任意多的子狀态/子結點，每個子狀态隻有一個父結點，要表達嵌套狀态，就是要構造出這樣一棵樹。

go-hsm

我用Golang編寫了一個HSM架構 go-hsm ，設計要點如下：

用類來表示狀态，局部化狀态内部變量及邏輯，整棵狀态樹由具體應用構造
支援嵌套狀态及行為繼承，支援進入退出動作，
支援自定義事件，支援靜态和動态兩種跳轉

它的代碼在這裡，go-hsm的使用例子則放在另一個項目 go-hsm-examples 。由于Golang本身的語言特點，有一些地方的實作較其它語言多了一些缺點，比如Golang裡面的binding是靜态的，為了将子類對象的指針傳播到父類方法，要顯式傳遞self指針，子類的接口函數也需要由應用重寫。但由于HSM本身的靈活強大，

go-hsm

具有良好的可調整性及擴充性，是一個很好的狀态機模組化工具，一門靈活有效表達複雜狀态機的 DSL(Domain Specific Language) 。

注：

[1] 《Structure and Interpretation of Computer Programs》一書的中文譯本。

[2] 本文内容主要出自Miro Samek博士的經典著作《Practical Statecharts in C/C++: Quantum Programmming for Embedded Systems》，其中文譯本書名為《嵌入式系統的微子產品化程式設計：實用狀态圖C/C++實作》，翻譯甚差，不推薦閱讀。

[3] 各種程式設計語言裡面的條件判斷關鍵字和語句都不盡相同，有的if語句帶

then

關鍵字，有的不帶

then

，有的支援

switch

，這裡将它們簡單統稱為if-else/switch語句。

[4] 本文中所有代碼都為Go語言代碼。

[5] 之是以強調函數是命名的，是因為很多語言支援匿名函數(即lambda函數)，在嵌套if-else/switch模式内部寫匿名函數定義對降低代碼膨脹起不了作用。

[6] OOP領域設計模式的流行，源于這本書《Design Patterns: Elements of Reusable Object-Oriented Software》的出版，其中文譯本見這裡。

層次狀态機

FSM

程式設計中的FSM

a. 嵌套if-else/switch模式

a. 狀态表

c. 狀态模式

5. 優化的FSM實作

6. HSM

go-hsm

繼續閱讀

DC-DC降壓電路

嵌入式硬體設計：電容電容三、電容的型号四、電容的分類

python機器人開發——基于Micropython的智能機器人底層控制開發

2021-08-20前言一、超音波子產品的工作原理二、超音波的時序圖三、利用STM32F407進行驅動編寫總結

藍橋杯單片機經曆

藍橋杯單片機标準模闆

藍橋杯單片機組學習總結（一）

藍橋杯單片機(二)獨立按鍵

藍橋杯單片機比賽蜂鳴器與繼電器子產品（原理、代碼詳解）

AD17學習筆記

Ardunio實作RGB調光原理PWM調光具體代碼

基于51單片機的智能調光台燈

PIC-直流電機無級調速系統

STM32-UART序列槽通信STM32-UART序列槽通信

詳解STM32單片機的堆棧

STM32F4内部Flash讀寫