函數式編程如何模擬有限狀態機？

01-31

比如用haskell

根據自動機的理論模型來就行, 用wikipedia里那個例子為例:

符號表:


&> symbols = [a..z]
狀態集:
&> data State = Start | NFound | IFound | CFound | Error | Success deriving Show
初始狀態集:

Start
終結狀態集:

[Error, Success]
映射函數:
&> match :: State -&> Char -&> State

&> match Start  n = NFound

&> match Start   _  = Error

&> match NFound i = IFound

&> match NFound  _  = Error

&> match IFound c = CFound

&> match IFound  _  = Error

&> match CFound e = Success

&> match CFound  _  = Error

&> matchNice :: String -&> State &> matchNice str = matchNice str Start &> where &> matchNice _ Error = Error &> matchNice [] Success = Success &> matchNice (x:xs) state = matchNice xs (match state x) &> matchNice _ Success = Error

效率什麼的忽略, 大概是這個意思~

補上一個用Elixir的宏的例子

defmodule Fsm do fsm = [ running: {:pause, :paused}, running: {:stop, :stopped}, paused: {:resume, :running} ]


  for {state, {action, next_state}} &<- fsm do
    def unquote(action)(unquote(state)), do: unquote(next_state)
  end
  def initial, do: :running
end

Fsm.initial
# :running

Fsm.initial |&> Fsm.pause

# :paused

Fsm.initial |&> Fsm.pause |&> Fsm.pause # ** (FunctionClauseError) no function clause matching in Fsm.pause/1

via theerlangelist.com

你可以去看下CLaSH。用Haskell寫的代碼在FPGA上跑。

狀態機用mealy 和moore 這兩個組合子實現，或者用state monad實現。

比如說，你要用mealy模型實現一個狀態機，你需要提供一個s -&> i -&> (s,o)的函數。

當然是面向異常編程，多種範式結合的最佳實踐（

exception State_transfer of (char -&> string) exception Terminating_state of string


let success = "Success"

let error = "Error"
let c_found = function

|e -&> raise (Terminating_state success)

|_ -&> raise (Terminating_state error)
let i_found = function

|c -&> raise (State_transfer c_found)

|_ -&> raise (Terminating_state error)
let n_found = function

|i -&> raise (State_transfer i_found)

|_ -&> raise (Terminating_state error)
let start = function

|n -&> raise (State_transfer n_found)

|_ -&> raise (Terminating_state error)
let rec state_machine f lst = match lst with

|[] -&> error

|x::xs -&> try f x with

   State_transfer st -&> state_machine st xs

  |Terminating_state str -&> str

let match_nice = state_machine start

簡潔一點可以寫成這樣：

exception State_transfer of (char -&> exn) exception Terminating_state of string


let success = "Success"

let error = "Error"
let c_found = function

|e -&> Terminating_state success

|_ -&> Terminating_state error
let i_found = function

|c -&> State_transfer c_found

|_ -&> Terminating_state error
let n_found = function

|i -&> State_transfer i_found

|_ -&> Terminating_state error
let start = function

|n -&> State_transfer n_found

|_ -&> Terminating_state error
let rec state_machine f lst = match lst with

|[] -&> error

|x::xs -&> match f x with

  |State_transfer st -&> state_machine st xs

  |Terminating_state str -&> str

  |_ -&> error

let match_nice = state_machine start

再把異常換成正常的 type 就和正常的寫法沒什麼區別了（逃

Table-driven

簡單的說說我的思路。

考慮自動機需要什麼功能，添加新的轉移路徑，查找路徑，表明起點終點。實現這些功能即可。

傳統上有兩種辦法，一張大的轉移表，保存全部狀態和轉移路徑；或者面向對象，每個狀態是一個對象。函數式編程，都可以借鑒這兩種方法實現。

轉移表[（int, char, int, start_or_end）]，各項分別標記狀態號，路徑的字元，路徑的下個狀態，起點或終點。剩下的就是寫函數來添加、刪除、查找了。最簡單的函數寫法就是haskell的++ !!或scheme的cons car cdr了。

類似面向對象的方法也很簡單。data State= State{sn: int, way: [(char,int)], soe: start_or_end} 要寫這麼幾個函數move, insert, delete, isStart, isEnd。

若是用scheme, define-datatype和cases配合也可以實現。

另外，也可以把state實現為函數。insert, delete, move返回的是不同的函數state，(state char)返回移動狀態後的state函數，(state start_end?)返回string表明起點或終點。其實也還是面向對象，不過是另一種實現而已，正是所謂的procedural representation。

非常粗糙的想法，歡迎指正。