學習 Erlang

為了美好的事物！

• 首頁
• 常見問題
• RSS
• 程式碼

對抗有限狀態機

它們是什麼？

有限狀態機 (FSM) 並不是真正的機器，但它確實具有有限數量的狀態。我一直覺得使用圖表和圖形更容易理解有限狀態機。例如，以下是一個簡化的圖表，表示一隻（非常笨的）狗的狀態機

這裡的狗有 3 種狀態：坐著、吠叫或搖尾巴。不同的事件或輸入可能會迫使它改變狀態。如果一隻狗平靜地坐著並看到一隻松鼠，它會開始吠叫，直到你再次撫摸它才會停止。但是，如果狗坐著而你撫摸它，我們不知道會發生什麼。在 Erlang 世界中，這隻狗可能會崩潰（並最終由其監管者重新啟動）。在現實世界中，這將是一個令人毛骨悚然的事件，但你的狗會在被汽車撞到後回來，所以這並不是完全糟糕。

這是為了比較而繪製的貓的狀態圖

這隻貓只有一種狀態，並且沒有任何事件可以改變它。

在 Erlang 中實作貓的狀態機是一項有趣且簡單的任務

-module(cat_fsm).
-export([start/0, event/2]).

start() ->
	spawn(fun() -> dont_give_crap() end).

event(Pid, Event) ->
	Ref = make_ref(), % won't care for monitors here
	Pid ! {self(), Ref, Event},
	receive
		{Ref, Msg} -> {ok, Msg}
	after 5000 ->
		{error, timeout}
	end.

dont_give_crap() ->
	receive
		{Pid, Ref, _Msg} -> Pid ! {Ref, meh};
		_ -> ok
	end,
	io:format("Switching to 'dont_give_crap' state~n"),
	dont_give_crap().

我們可以嘗試這個模組，看看這隻貓真的從不在乎

1> c(cat_fsm).
{ok,cat_fsm}
2> Cat = cat_fsm:start().
<0.67.0>
3> cat_fsm:event(Cat, pet).
Switching to 'dont_give_crap' state
{ok,meh}
4> cat_fsm:event(Cat, love).
Switching to 'dont_give_crap' state
{ok,meh}
5> cat_fsm:event(Cat, cherish).
Switching to 'dont_give_crap' state
{ok,meh}

對於狗的 FSM也可以做同樣的事情，只是有更多狀態可用

-module(dog_fsm).
-export([start/0, squirrel/1, pet/1]).

start() ->
	spawn(fun() -> bark() end).

squirrel(Pid) -> Pid ! squirrel.

pet(Pid) -> Pid ! pet.

bark() ->
    io:format("Dog says: BARK! BARK!~n"),
    receive
        pet ->
            wag_tail();
        _ ->
            io:format("Dog is confused~n"),
            bark()
    after 2000 ->
        bark()
    end.

wag_tail() ->
    io:format("Dog wags its tail~n"),
    receive
        pet ->
            sit();
        _ ->
            io:format("Dog is confused~n"),
            wag_tail()
    after 30000 ->
        bark()
    end.

sit() ->
    io:format("Dog is sitting. Gooooood boy!~n"),
    receive
        squirrel ->
            bark();
        _ ->
            io:format("Dog is confused~n"),
            sit()
    end.

將每個狀態和轉換對應到上面的圖表應該相對簡單。以下是使用中的 FSM

6> c(dog_fsm).
{ok,dog_fsm}
7> Pid = dog_fsm:start().
Dog says: BARK! BARK!
<0.46.0>
Dog says: BARK! BARK!
Dog says: BARK! BARK!
Dog says: BARK! BARK!
8> dog_fsm:pet(Pid).
pet
Dog wags its tail
9> dog_fsm:pet(Pid).
Dog is sitting. Gooooood boy!
pet
10> dog_fsm:pet(Pid).
Dog is confused
pet
Dog is sitting. Gooooood boy!
11> dog_fsm:squirrel(Pid).
Dog says: BARK! BARK!
squirrel
Dog says: BARK! BARK!    
12> dog_fsm:pet(Pid).
Dog wags its tail
pet
13> %% wait 30 seconds
Dog says: BARK! BARK!
Dog says: BARK! BARK!
Dog says: BARK! BARK!     
13> dog_fsm:pet(Pid).     
Dog wags its tail
pet
14> dog_fsm:pet(Pid).
Dog is sitting. Gooooood boy!
pet

如果需要，您可以按照這個架構進行（我通常會這樣做，這有助於確保沒有任何問題）。

這實際上是作為 Erlang 程序實作的 FSM 的核心。有些事情可以做得不同：我們可以以類似於伺服器主迴圈的方式，在狀態函數的參數中傳遞狀態。我們也可以加入 init 和 terminate 函數，處理程式碼更新等等。

狗和貓的 FSM 之間的另一個區別是，貓的事件是同步的，而狗的事件是非同步的。在真正的 FSM 中，兩者可以混合使用，但我為了最簡單的表示而選擇了最純粹的惰性。還有其他形式的事件範例中沒有顯示：可以在任何狀態下發生的全域事件。

這樣一個事件的例子可能是當狗聞到食物的味道時。一旦觸發 smell food 事件，無論狗處於什麼狀態，它都會去尋找食物的來源。

現在我們不會花太多時間在我們「寫在餐巾紙上」的 FSM 中實作所有這些。相反，我們將直接轉到 gen_fsm 行為。

通用有限狀態機

gen_fsm 行為在某種程度上類似於 gen_server，因為它是它的專門版本。最大的區別在於，我們處理的是同步和非同步的事件，而不是處理呼叫和轉換。與我們的狗和貓的例子非常相似，每個狀態都由一個函數表示。同樣，我們將瀏覽模組為了運作而需要實作的回呼。

init

這與通用伺服器使用的 init/1 相同，只是接受的傳回值是 {ok, StateName, Data}、{ok, StateName, Data, Timeout}、{ok, StateName, Data, hibernate} 和 {stop, Reason}。 stop 元組的工作方式與 gen_server 的相同，而 hibernate 和 Timeout 保留相同的語義。

這裡的新內容是 StateName 變數。StateName 是一個原子，表示要呼叫的下一個回呼函數。

StateName

函數 StateName/2 和 StateName/3 是佔位符名稱，您需要決定它們是什麼。假設 init/1 函數傳回元組 {ok, sitting, dog}。這表示有限狀態機將處於 sitting 狀態。這與我們在 gen_server 中看到的狀態類型不同；它更像是先前狗 FSM 的 sit、bark 和 wag_tail 狀態。這些狀態決定了您處理給定事件的上下文。

舉例來說，有人打電話給你。如果你的狀態是「週六早上睡覺」，你的反應可能是對電話大吼大叫。如果你的狀態是「等待工作面試」，你很可能會接起電話並禮貌地回答。另一方面，如果你的狀態是「已死」，那麼我很驚訝你竟然還能讀到這段文字。

回到我們的 FSM。 init/1 函數表示我們應該處於 sitting 狀態。每當 gen_fsm 程序收到一個事件時，就會呼叫函數 sitting/2 或 sitting/3。 sitting/2 函數會針對非同步事件呼叫，而 sitting/3 函數會針對同步事件呼叫。

sitting/2（或通常是 StateName/2）的參數是 Event，即作為事件傳送的實際訊息，以及 StateData，即在呼叫中攜帶的資料。然後 sitting/2 可以傳回元組 {next_state, NextStateName, NewStateData}、{next_state, NextStateName, NewStateData, Timeout}、{next_state, NextStateName, NewStateData, hibernate} 和 {stop, Reason, NewStateData}。

sitting/3 的參數類似，只是在 Event 和 StateData 之間有一個 From 變數。From 變數的使用方式與 gen_server 的完全相同，包括 gen_fsm:reply/2。 StateName/3 函數可以傳回以下元組

{reply, Reply, NextStateName, NewStateData}
{reply, Reply, NextStateName, NewStateData, Timeout}
{reply, Reply, NextStateName, NewStateData, hibernate}

{next_state, NextStateName, NewStateData}
{next_state, NextStateName, NewStateData, Timeout}
{next_state, NextStateName, NewStateData, hibernate}

{stop, Reason, Reply, NewStateData}
{stop, Reason, NewStateData}

請注意，您可以擁有的這些函數數量沒有限制，只要它們是導出的即可。在元組中以 NextStateName 形式傳回的原子將決定是否呼叫該函數。

handle_event

在上一節中，我提到了全域事件，無論我們處於什麼狀態，它們都會觸發特定的反應（狗聞到食物的味道會放下正在做的事情，轉而去尋找食物）。對於這些應該在每個狀態中以相同方式處理的事件，您需要的是 handle_event/3 回呼。該函數接受與 StateName/2 類似的參數，但它們之間接受一個 StateName 變數，告訴您收到事件時的狀態。它傳回與 StateName/2 相同的值。

handle_sync_event

handle_sync_event/4 回呼對於 StateName/3 而言，就像 handle_event/2 對於 StateName/2 一樣。它會處理同步全域事件，採用相同的參數並傳回與 StateName/3 相同的元組類型。

現在可能是解釋我們如何知道事件是全域的，還是應該傳送到特定狀態的好時機。要確定這一點，我們可以查看用於將事件傳送到 FSM 的函數。針對任何 StateName/2 函數的非同步事件都是使用 send_event/2 傳送的，而要由 StateName/3 接收的同步事件則使用 sync_send_event/2-3 傳送。

全域事件的兩個對等函數是 send_all_state_event/2 和 sync_send_all_state_event/2-3（名稱相當長）。

code_change

它的工作方式與 gen_server 的完全相同，只是當呼叫時會採用額外的狀態參數，例如 code_change(OldVersion, StateName, Data, Extra)，並傳回 {ok, NextStateName, NewStateData} 形式的元組。

terminate

這應該再次像我們為通用伺服器所擁有的那樣運作。terminate/3 應該執行與 init/1 相反的操作。

交易系統規格

現在是將所有這些付諸實踐的時候了。許多關於有限狀態機的 Erlang 教學範例都使用包含電話交換機和類似內容的範例。我猜想，大多數程式設計師很少需要處理用於狀態機的電話交換機。因此，我們將來看一個更適合許多開發人員的範例：我們將為某個虛構且不存在的電玩遊戲設計和實作一個物品交易系統。

我選擇的設計有些挑戰性。我們將實作一個伺服器，讓兩個玩家直接交談（這將具有可分配的優點），而不是使用玩家在其中路由物品和確認的代理（坦率地說，這會更容易）。

由於實作很棘手，我會花很多時間來描述它、要面對的問題以及解決問題的方法。

首先，我們應該定義玩家在交易時可以執行的動作。第一個是要求設定交易。另一個使用者也應該能夠接受該交易。不過，我們不會給他們拒絕交易的權利，因為我們希望讓事情保持簡單。一旦完成整個過程，就很可以輕鬆新增此功能。

設定交易後，我們的使用者應該能夠彼此協商。這表示他們應該能夠提出報價，然後在他們願意時撤回。當雙方都對報價感到滿意時，他們可以各自宣告自己準備好完成交易。然後，資料應該儲存在雙方的某個位置。在任何時間點，任何一方的玩家取消整個交易也應該有意義。一些平民可能只提供被對方（可能很忙）認為不值得的物品，因此應該可以使用理所當然的取消來反擊他們。

簡而言之，應該可以執行以下動作

• 要求交易
• 接受交易
• 提供物品
• 撤回報價
• 宣告自己準備好
• 粗暴地取消交易

現在，當執行這些動作中的每一個時，另一個玩家的 FSM 應該要知道。這是有道理的，因為當 Jim 告訴他的 FSM 將一個物品傳送給 Carl 時，Carl 的 FSM 必須知道這件事。這表示兩個玩家都可以與他們自己的 FSM 交談，而 FSM 會與對方的 FSM 交談。這讓我們得到類似這樣的東西

當我們有兩個相同的程序彼此通訊時，首先要注意的是，我們必須盡可能避免同步呼叫。原因在於，如果 Jim 的 FSM 向 Carl 的 FSM 傳送訊息，然後等待其回覆，同時 Carl 的 FSM 向 Jim 的 FSM 傳送訊息，並等待其特定的回覆，則兩者最終都會等待對方，而永遠不會回覆。這實際上會凍結兩個 FSM。我們遇到了死鎖。

一種解決方案是等待逾時，然後繼續，但是這樣兩個程序的信箱中都會有剩餘的訊息，並且協議會搞砸。這肯定是一個麻煩的難題，因此我們要避免它。

最簡單的方法是避免所有同步訊息並完全使用非同步訊息。請注意，Jim 仍然可以對自己的 FSM 進行同步呼叫；這裡沒有風險，因為 FSM 不需要呼叫 Jim，因此它們之間不會發生死鎖。

當這兩個 FSM 一起通訊時，整個交換過程可能看起來有點像這樣

兩個有限狀態機 (FSM) 都處於閒置狀態。當您要求 Jim 交易時，Jim 必須先接受，事情才能繼續進行。然後，你們雙方都可以提供物品或撤回它們。當你們都聲明自己準備好時，交易就可以進行。這是一個簡化版本，說明可能發生的所有情況，我們將在接下來的段落中更詳細地了解所有可能的案例。

現在是困難的部分：定義狀態圖以及狀態轉換如何發生。通常需要花費大量心思在這上面，因為您必須考慮所有可能出錯的小細節。有些事情即使在多次審查後也可能會出錯。因此，我將直接將我決定實作的版本放在這裡，然後再加以解釋。

首先，兩個有限狀態機都從 idle (閒置) 狀態開始。在這一點上，我們可以做的一件事是要求其他玩家與我們協商。

為了等待我們的 FSM 轉發請求後的回覆，我們會進入 idle_wait (閒置等待) 模式。一旦另一個 FSM 發送回覆，我們的 FSM 就可以切換到 negotiate (協商) 狀態。

另一個玩家也應該在此之後處於 negotiate (協商) 狀態。顯然，如果我們可以邀請對方，對方也可以邀請我們。如果一切順利，結果應該看起來像這樣：

所以這幾乎與先前兩個狀態圖的組合相反。請注意，在這種情況下，我們預期玩家會接受提議。如果純粹是運氣好，我們在要求對方與我們交易的同時，對方也要求我們交易，會發生什麼事？

這裡發生的情況是，兩個客戶端都會要求自己的 FSM 與另一個 FSM 進行協商。一旦發送了 *ask negotiate* (要求協商) 訊息，兩個 FSM 都會切換到 idle_wait (閒置等待) 狀態。然後，它們將能夠處理協商請求。如果我們回顧先前的狀態圖，我們會發現這種事件組合是我們在 idle_wait (閒置等待) 狀態下接收 *ask negotiate* (要求協商) 訊息的唯一情況。因此，我們知道在 idle_wait (閒置等待) 中收到這些訊息意味著我們遇到了競爭條件，並且可以假設兩個使用者都想互相交談。我們可以將它們都移到 negotiate (協商) 狀態。萬歲！

現在我們正在協商。根據我先前列出的動作清單，我們必須支援使用者提供物品，然後撤回提議。

這一切所做的只是將我們客戶端的訊息轉發到另一個 FSM。兩個有限狀態機都需要保存任一玩家提供的物品清單，以便在收到此類訊息時更新該清單。此後我們仍保持在 negotiate (協商) 狀態；也許另一個玩家也想提供物品。

在這裡，我們的 FSM 基本上的作用方式類似。這是正常的。一旦我們厭倦了提供東西，並且認為自己夠慷慨了，我們就必須說我們準備正式進行交易。因為我們必須同步兩個玩家，我們必須使用一個中間狀態，就像我們對 idle (閒置) 和 idle_wait (閒置等待) 所做的那樣。

我們在這裡所做的是，一旦我們的玩家準備好，我們的 FSM 就會詢問 Jim 的 FSM 他是否準備好。在等待其回覆期間，我們自己的 FSM 會進入其 wait (等待) 狀態。我們將收到的回覆將取決於 Jim 的 FSM 狀態：如果它處於 wait (等待) 狀態，它會告訴我們它已準備好。否則，它會告訴我們它尚未準備好。這正是如果 Jim 在 negotiate (協商) 狀態下詢問我們是否準備好，我們的 FSM 會自動回覆 Jim 的內容。

在我們的玩家說他準備好之前，我們的有限狀態機將保持在 negotiate (協商) 模式。讓我們假設他已經這樣做了，而我們現在處於 wait (等待) 狀態。但是，Jim 還沒有準備好。這表示當我們聲明自己準備好時，我們將會詢問 Jim 他是否也準備好，而他的 FSM 將會回覆「尚未準備好」。

他還沒準備好，但我們準備好了。我們無能為力，只能繼續等待。在等待 Jim 的同時 (順便說一下，他仍在協商中)，他可能會嘗試向我們發送更多物品，或取消他先前的提議。

當然，我們想避免 Jim 移除他所有的物品，然後點擊「我準備好了！」，從而在此過程中欺騙我們。一旦他更改了提供的物品，我們就會回到 negotiate (協商) 狀態，以便我們可以修改自己的提議，或檢查目前的提議，並決定我們是否準備好了。重複操作。

在某個時間點，Jim 也會準備好完成交易。當這種情況發生時，他的有限狀態機將會詢問我們的 FSM 我們是否準備好。

我們的 FSM 所做的是回覆我們確實準備好了。我們仍保持在等待狀態，並拒絕移動到 ready (準備好) 狀態。這是為什麼？因為存在潛在的競爭條件！想像一下，在沒有執行這個必要的步驟的情況下，以下事件序列發生了：

這有點複雜，因此我將解釋一下。由於訊息接收的方式，我們可能只會在我們聲明自己準備好之後，以及 Jim 也聲明自己準備好之後，才處理物品提議。這表示一旦我們讀取提議訊息，我們就會切換回 negotiate (協商) 狀態。在那段時間，Jim 會告訴我們他準備好了。如果他要在那裡改變狀態並移動到 ready (準備好) 狀態 (如上所示)，他會陷入無限期等待，而我們將不知道該怎麼辦。這種情況也可能反過來發生！哎呀。

解決這個問題的一種方法是增加一層間接性 (感謝 David Wheeler)。這就是為什麼我們保持在 wait (等待) 模式並發送「ready!」(如我們先前的狀態圖所示)。以下是我們如何處理該「ready!」訊息，假設我們已經處於 ready (準備好) 狀態，因為我們事先告訴我們的 FSM 我們準備好了：

當我們收到來自另一個 FSM 的「ready!」時，我們會再次發送「ready!」。這是為了確保我們不會出現上述的「雙重競爭條件」。這將在兩個 FSM 中的其中一個中產生多餘的「ready!」訊息，但我們只需在這種情況下忽略它即可。然後，我們會發送一個「ack」訊息 (而 Jim 的 FSM 也會做同樣的事情)，然後才移動到 ready (準備好) 狀態。「ack」訊息存在的原因是一些關於同步客戶端的實作細節。為了確保正確性，我將它放在圖表中，但我不會在稍後解釋它。現在先忘記它。我們終於成功同步了兩位玩家。呼！

所以現在有了 ready (準備好) 狀態。這個狀態有點特殊。兩個玩家都準備好了，並且基本上已經將他們需要的所有控制權交給了有限狀態機。這讓我們可以實作一個修改過的 兩階段提交 版本，以確保在正式進行交易時一切順利。

我們的版本 (如上所述) 將相當簡單。編寫一個真正正確的兩階段提交，將需要比我們理解有限狀態機所需的多得多的程式碼。

最後，我們只需允許隨時取消交易。這表示無論我們處於何種狀態，我們都會從雙方收聽「cancel」(取消) 訊息並退出交易。在離開之前通知對方我們離開也應該是出於禮貌。

好吧！一次要吸收這麼多資訊實在有點多。如果需要一點時間才能完全理解它，請不要擔心。我花了一大群人仔細檢查我的協定，看看是否正確，即使這樣，我們都錯過了一些競爭條件，然後我在撰寫本文時審查程式碼時，在幾天後才發現它們。需要閱讀不只一次是很正常的，尤其如果您不習慣非同步協定。如果是這種情況，我強烈建議您嘗試設計自己的協定。然後問自己「如果兩個人非常快地執行相同的動作會發生什麼？如果他們快速鏈接另外兩個事件會發生什麼？當狀態變更時，我該如何處理我沒有處理的訊息？」您會發現複雜性增長得非常快。您可能會找到類似我提供的解決方案，甚至更好的解決方案 (如果有這種情況，請告訴我！) 無論結果如何，這都是一件非常有趣的工作，而且我們的 FSM 仍然相對簡單。

一旦您消化了這一切 (或者如果您是個叛逆的讀者，在消化之前)，您就可以進入下一節，在那裡我們將實作遊戲系統。如果您想這麼做，您現在可以去享用一杯美味的咖啡。

兩位玩家之間的遊戲交易

要使用 OTP 的 gen_fsm 實作我們的協定，首先需要做的是建立介面。我們的模組將有 3 個呼叫者：玩家、gen_fsm 行為和其他玩家的 FSM。但是，我們只需要匯出玩家函數和 gen_fsm 函數。這是因為其他 FSM 也將在 trade_fsm 模組中執行，並且可以從內部存取它們。

-module(trade_fsm).
-behaviour(gen_fsm).

%% public API
-export([start/1, start_link/1, trade/2, accept_trade/1, 
         make_offer/2, retract_offer/2, ready/1, cancel/1]).
%% gen_fsm callbacks
-export([init/1, handle_event/3, handle_sync_event/4, handle_info/3,
         terminate/3, code_change/4,
         % custom state names
         idle/2, idle/3, idle_wait/2, idle_wait/3, negotiate/2,
         negotiate/3, wait/2, ready/2, ready/3]).

這就是我們的 API。您可以看到我計劃讓某些函數同時具有同步和非同步功能。這主要是因為我們希望我們的客戶端在某些情況下同步呼叫我們，但另一個 FSM 可以非同步呼叫。讓客戶端同步可以透過限制可以一個接一個發送的矛盾訊息的數量，來大大簡化我們的邏輯。我們會到達那裡的。讓我們首先根據上述定義的協定來實作實際的公開 API。

%%% PUBLIC API
start(Name) ->
    gen_fsm:start(?MODULE, [Name], []).

start_link(Name) ->
    gen_fsm:start_link(?MODULE, [Name], []).

%% ask for a begin session. Returns when/if the other accepts
trade(OwnPid, OtherPid) ->
    gen_fsm:sync_send_event(OwnPid, {negotiate, OtherPid}, 30000).

%% Accept someone's trade offer.
accept_trade(OwnPid) ->
    gen_fsm:sync_send_event(OwnPid, accept_negotiate).

%% Send an item on the table to be traded
make_offer(OwnPid, Item) ->
    gen_fsm:send_event(OwnPid, {make_offer, Item}).

%% Cancel trade offer
retract_offer(OwnPid, Item) ->
    gen_fsm:send_event(OwnPid, {retract_offer, Item}).

%% Mention that you're ready for a trade. When the other
%% player also declares being ready, the trade is done
ready(OwnPid) ->
    gen_fsm:sync_send_event(OwnPid, ready, infinity).

%% Cancel the transaction.
cancel(OwnPid) ->
    gen_fsm:sync_send_all_state_event(OwnPid, cancel).

這相當標準；所有這些「gen_fsm」函數之前都已在本章中介紹過 (除了 start/3-4 和 start_link/3-4，我相信您可以理解它們)，。

接下來，我們將實作 FSM 到 FSM 的函數。第一個與交易設定有關，也就是當我們第一次想要求其他使用者加入我們進行交易時。

%% Ask the other FSM's Pid for a trade session
ask_negotiate(OtherPid, OwnPid) ->
    gen_fsm:send_event(OtherPid, {ask_negotiate, OwnPid}).

%% Forward the client message accepting the transaction
accept_negotiate(OtherPid, OwnPid) ->
    gen_fsm:send_event(OtherPid, {accept_negotiate, OwnPid}).

第一個函數會詢問另一個 pid 是否要交易，而第二個函數則是用來回覆該詢問（當然，是非同步的）。

接著我們可以撰寫提供和取消報價的函數。根據我們上面的協定，它們應該是這樣的：

%% forward a client's offer
do_offer(OtherPid, Item) ->
    gen_fsm:send_event(OtherPid, {do_offer, Item}).

%% forward a client's offer cancellation
undo_offer(OtherPid, Item) ->
    gen_fsm:send_event(OtherPid, {undo_offer, Item}).

現在，我們已經完成了這些呼叫，需要專注於剩下的部分。剩下的呼叫與是否準備好以及處理最終的提交有關。同樣，根據我們上面的協定，我們有三個呼叫：are_you_ready，其回覆可以是 not_yet 或 ready!。

%% Ask the other side if he's ready to trade.
are_you_ready(OtherPid) ->
    gen_fsm:send_event(OtherPid, are_you_ready).

%% Reply that the side is not ready to trade
%% i.e. is not in 'wait' state.
not_yet(OtherPid) ->
    gen_fsm:send_event(OtherPid, not_yet).

%% Tells the other fsm that the user is currently waiting
%% for the ready state. State should transition to 'ready'
am_ready(OtherPid) ->
    gen_fsm:send_event(OtherPid, 'ready!').

剩下的唯一函數是那些在 ready 狀態下進行提交時，由兩個 FSM 使用的函數。它們的精確用法稍後將更詳細地描述，但目前來說，名稱和先前的序列/狀態圖應該就足夠了。儘管如此，您仍然可以將它們轉錄到您自己版本的 trade_fsm 中。

%% Acknowledge that the fsm is in a ready state.
ack_trans(OtherPid) ->
    gen_fsm:send_event(OtherPid, ack).

%% ask if ready to commit
ask_commit(OtherPid) ->
    gen_fsm:sync_send_event(OtherPid, ask_commit).

%% begin the synchronous commit
do_commit(OtherPid) ->
    gen_fsm:sync_send_event(OtherPid, do_commit).

喔，還有一個禮貌性函數，允許我們警告另一個 FSM 我們取消了交易。

notify_cancel(OtherPid) ->
    gen_fsm:send_all_state_event(OtherPid, cancel).

現在我們可以進入真正有趣的部分：gen_fsm 回呼函數。第一個回呼函數是 init/1。在我們的例子中，我們希望每個 FSM 為它所代表的使用者保留一個名稱（這樣我們的輸出會更美觀），並將其保存在它持續傳遞給自己的資料中。我們還想在記憶體中保留什麼？在我們的例子中，我們想要對方的 pid、我們提供的物品以及對方提供的物品。我們還將加入一個監視器的參考（以便我們知道如果對方死亡則中止）以及一個 from 欄位，用於進行延遲回覆。

-record(state, {name="",
                other,
                ownitems=[],
                otheritems=[],
                monitor,
                from}).

在 init/1 的情況下，我們目前只關心我們的名稱。請注意，我們將從 idle 狀態開始。

init(Name) ->
    {ok, idle, #state{name=Name}}. 

接下來要考慮的回呼函數將是狀態本身。到目前為止，我已經描述了狀態轉換和可以進行的呼叫，但我們需要一種方法來確保一切順利。我們先撰寫一些實用函數。

%% Send players a notice. This could be messages to their clients
%% but for our purposes, outputting to the shell is enough.
notice(#state{name=N}, Str, Args) ->
    io:format("~s: "++Str++"~n", [N|Args]).

%% Unexpected allows to log unexpected messages
unexpected(Msg, State) ->
    io:format("~p received unknown event ~p while in state ~p~n",
              [self(), Msg, State]).

我們可以從閒置狀態開始。為了方便起見，我將先介紹非同步版本。根據我們的 API 函數，這個版本除了另一個玩家要求交易之外，不需要關心任何事情，如果你查看 API 函數，你會發現它會使用同步呼叫。

idle({ask_negotiate, OtherPid}, S=#state{}) ->
    Ref = monitor(process, OtherPid),
    notice(S, "~p asked for a trade negotiation", [OtherPid]),
    {next_state, idle_wait, S#state{other=OtherPid, monitor=Ref}};
idle(Event, Data) ->
    unexpected(Event, idle),
    {next_state, idle, Data}.

設定一個監視器，以便我們處理另一方死亡的情況，並且它的 ref 會與對方的 pid 一起儲存在 FSM 的資料中，然後移動到 idle_wait 狀態。請注意，我們將報告所有非預期的事件，並通過保持在我們已經處於的狀態來忽略它們。這裡可能會有一些帶外訊息，它們可能是競爭條件的結果。忽略它們通常是安全的，但我們無法輕易地擺脫它們。最好不要因為這些未知但有點預期的訊息而導致整個 FSM 崩潰。

當我們自己的客戶要求 FSM 聯絡另一位玩家進行交易時，它將發送一個同步事件。需要 idle/3 回呼函數。

idle({negotiate, OtherPid}, From, S=#state{}) ->
    ask_negotiate(OtherPid, self()),
    notice(S, "asking user ~p for a trade", [OtherPid]),
    Ref = monitor(process, OtherPid),
    {next_state, idle_wait, S#state{other=OtherPid, monitor=Ref, from=From}};
idle(Event, _From, Data) ->
    unexpected(Event, idle),
    {next_state, idle, Data}.

我們以類似於非同步版本的方式進行，但我們需要實際詢問對方是否願意與我們協商。您會注意到我們 *沒有* 回覆客戶。這是因為我們沒有什麼有趣的事情要說，並且我們希望客戶被鎖定並等待交易被接受後再進行任何操作。只有當對方接受，並且我們處於 idle_wait 狀態時，才會發送回覆。

當我們處於該狀態時，我們必須處理對方接受協商，以及對方要求協商（如協定中所述，這是競爭條件的結果）。

idle_wait({ask_negotiate, OtherPid}, S=#state{other=OtherPid}) ->
    gen_fsm:reply(S#state.from, ok),
    notice(S, "starting negotiation", []),
    {next_state, negotiate, S};
%% The other side has accepted our offer. Move to negotiate state
idle_wait({accept_negotiate, OtherPid}, S=#state{other=OtherPid}) ->
    gen_fsm:reply(S#state.from, ok),
    notice(S, "starting negotiation", []),
    {next_state, negotiate, S};
idle_wait(Event, Data) ->
    unexpected(Event, idle_wait),
    {next_state, idle_wait, Data}.

這給了我們兩個轉換到 negotiate 狀態的機會，但請記住，我們必須使用 gen_fsm:reply/2 回覆我們的客戶，告訴它可以開始提供物品。還有我們的 FSM 客戶接受另一方提出的交易的情況。

idle_wait(accept_negotiate, _From, S=#state{other=OtherPid}) ->
    accept_negotiate(OtherPid, self()),
    notice(S, "accepting negotiation", []),
    {reply, ok, negotiate, S};
idle_wait(Event, _From, Data) ->
    unexpected(Event, idle_wait),
    {next_state, idle_wait, Data}.

同樣，這會轉換到 negotiate 狀態。在這裡，我們必須處理來自客戶和另一個 FSM 的非同步查詢，以新增和移除物品。但是，我們尚未決定如何儲存物品。因為我有點懶，而且我假設使用者不會交易那麼多物品，所以簡單的列表目前就足夠了。但是，我們可能會在稍後改變主意，因此最好將物品操作包裝在它們自己的函數中。將以下函數與 notice/3 和 unexpected/2 一起新增到檔案底部。

%% adds an item to an item list
add(Item, Items) ->
    [Item | Items].

%% remove an item from an item list
remove(Item, Items) ->
    Items -- [Item].

很簡單，但它們的作用是將動作（新增和移除物品）與它們的實作（使用列表）隔離。我們可以輕鬆地移動到屬性列表、陣列或任何其他資料結構，而不會破壞程式碼的其餘部分。

使用這兩個函數，我們可以實作提供和移除物品。

negotiate({make_offer, Item}, S=#state{ownitems=OwnItems}) ->
    do_offer(S#state.other, Item),
    notice(S, "offering ~p", [Item]),
    {next_state, negotiate, S#state{ownitems=add(Item, OwnItems)}};
%% Own side retracting an item offer
negotiate({retract_offer, Item}, S=#state{ownitems=OwnItems}) ->
    undo_offer(S#state.other, Item),
    notice(S, "cancelling offer on ~p", [Item]),
    {next_state, negotiate, S#state{ownitems=remove(Item, OwnItems)}};
%% other side offering an item
negotiate({do_offer, Item}, S=#state{otheritems=OtherItems}) ->
    notice(S, "other player offering ~p", [Item]),
    {next_state, negotiate, S#state{otheritems=add(Item, OtherItems)}};
%% other side retracting an item offer
negotiate({undo_offer, Item}, S=#state{otheritems=OtherItems}) ->
    notice(S, "Other player cancelling offer on ~p", [Item]),
    {next_state, negotiate, S#state{otheritems=remove(Item, OtherItems)}};

這是兩端都使用非同步訊息的一個醜陋之處。一組訊息的形式為 'make' 和 'retract'，而另一組訊息的形式為 'do' 和 'undo'。這完全是任意的，僅用於區分玩家到 FSM 的通訊和 FSM 到 FSM 的通訊。請注意，對於來自我們自己玩家的訊息，我們必須告訴對方我們正在進行的變更。

另一個責任是處理我們在協定中提到的 are_you_ready 訊息。這是要在 negotiate 狀態中處理的最後一個非同步事件。

negotiate(are_you_ready, S=#state{other=OtherPid}) ->
    io:format("Other user ready to trade.~n"),
    notice(S,
           "Other user ready to transfer goods:~n"
           "You get ~p, The other side gets ~p",
           [S#state.otheritems, S#state.ownitems]),
    not_yet(OtherPid),
    {next_state, negotiate, S};
negotiate(Event, Data) ->
    unexpected(Event, negotiate),
    {next_state, negotiate, Data}.

正如協定中所述，只要我們不在 wait 狀態且收到此訊息，我們就必須回覆 not_yet。我們也會將交易詳細資訊輸出給使用者，以便可以做出決定。

當做出這樣的決定並且使用者準備好時，將會發送 ready 事件。這應該是同步的，因為我們不希望使用者在聲稱自己準備好的同時，通過新增物品來持續修改他的報價。

negotiate(ready, From, S = #state{other=OtherPid}) ->
    are_you_ready(OtherPid),
    notice(S, "asking if ready, waiting", []),
    {next_state, wait, S#state{from=From}};
negotiate(Event, _From, S) ->
    unexpected(Event, negotiate),
    {next_state, negotiate, S}.

此時，應該轉換到 wait 狀態。請注意，僅僅等待對方是沒有意義的。我們儲存 From 變數，以便我們可以在有訊息要告訴客戶時，將其與 gen_fsm:reply/2 一起使用。

wait 狀態是一個有趣的野獸。可能會提供和撤回新物品，因為對方可能尚未準備好。因此，自動回滾到協商狀態是有道理的。如果有人向我們提供了很棒的物品，結果對方卻移除了它們並聲稱自己準備好，這就太糟糕了。回到協商是一個很好的決定。

wait({do_offer, Item}, S=#state{otheritems=OtherItems}) ->
    gen_fsm:reply(S#state.from, offer_changed),
    notice(S, "other side offering ~p", [Item]),
    {next_state, negotiate, S#state{otheritems=add(Item, OtherItems)}};
wait({undo_offer, Item}, S=#state{otheritems=OtherItems}) ->
    gen_fsm:reply(S#state.from, offer_changed),
    notice(S, "Other side cancelling offer of ~p", [Item]),
    {next_state, negotiate, S#state{otheritems=remove(Item, OtherItems)}};

這是有意義的，我們使用儲存在 S#state.from 中的座標回覆玩家。 我們需要擔心的下一組訊息與同步兩個 FSM 有關，以便它們可以移動到 ready 狀態並確認交易。對於此訊息，我們應該真正專注於先前定義的協定。

我們可能有的三個訊息是 are_you_ready（因為對方剛剛聲稱自己準備好）、not_yet（因為我們問對方是否準備好，而他沒有）和 ready!（因為我們問對方是否準備好，而他準備好了）。

我們將從 are_you_ready 開始。請記住，在協定中我們說過那裡可能隱藏著競爭條件。我們唯一能做的就是使用 am_ready/1 發送 ready! 訊息，並稍後處理其餘部分。

wait(are_you_ready, S=#state{}) ->
    am_ready(S#state.other),
    notice(S, "asked if ready, and I am. Waiting for same reply", []),
    {next_state, wait, S};

我們將再次陷入等待，因此暫時不需要回覆我們的客戶。同樣地，當另一方將 not_yet 發送到我們的邀請時，我們也不會回覆客戶。

wait(not_yet, S = #state{}) ->
    notice(S, "Other not ready yet", []),
    {next_state, wait, S};

另一方面，如果對方準備好，我們會向另一個 FSM 發送額外的 ready! 訊息，回覆我們自己的使用者，然後移動到 ready 狀態。

wait('ready!', S=#state{}) ->
    am_ready(S#state.other),
    ack_trans(S#state.other),
    gen_fsm:reply(S#state.from, ok),
    notice(S, "other side is ready. Moving to ready state", []),
    {next_state, ready, S};
%% DOn't care about these!
wait(Event, Data) ->
    unexpected(Event, wait),
    {next_state, wait, Data}.

您可能已經注意到我使用了 ack_trans/1。實際上，兩個 FSM 都應該使用它。這是為什麼呢？要理解這一點，我們必須開始了解 ready! 狀態下發生的事情。

在準備好狀態下，兩個玩家的動作都變得無用（取消除外）。我們不會關心新的物品報價。這給了我們一些自由。基本上，兩個 FSM 可以自由地相互交談，而不用擔心其他世界。這讓我們可以實作我們對兩階段提交的改造。為了在沒有任何玩家採取行動的情況下開始提交，我們需要一個事件來觸發 FSM 的動作。ack_trans/1 中的 ack 事件用於此目的。只要我們處於準備就緒狀態，訊息就會被處理並採取行動；交易就可以開始了。

但是，兩階段提交需要同步通訊。這意味著我們不能讓兩個 FSM 同時開始交易，因為它們最終會死鎖。訣竅是找到一種方法來決定一個有限狀態機應該啟動提交，而另一個則會坐等第一個的命令。

事實證明，設計 Erlang 的工程師和電腦科學家非常聰明（好吧，我們早就知道了）。任何程序 的 pid 都可以相互比較並排序。無論程序 何時產生、是否仍然存活或是否來自另一個 VM，都可以執行此操作（當我們進入分散式 Erlang 時，我們將看到更多相關資訊）。

知道兩個 pid 可以比較並且一個會大於另一個，我們可以編寫一個函數 priority/2，它將取得兩個 pid 並告訴程序 是否已被選中。

priority(OwnPid, OtherPid) when OwnPid > OtherPid -> true;
priority(OwnPid, OtherPid) when OwnPid < OtherPid -> false.

通過呼叫該函數，我們可以讓一個程序啟動提交，而另一個則遵循命令。

這是包含在 ready 狀態（在收到 ack 訊息之後）中的結果。

ready(ack, S=#state{}) ->
    case priority(self(), S#state.other) of
        true ->
            try 
                notice(S, "asking for commit", []),
                ready_commit = ask_commit(S#state.other),
                notice(S, "ordering commit", []),
                ok = do_commit(S#state.other),
                notice(S, "committing...", []),
                commit(S),
                {stop, normal, S}
            catch Class:Reason -> 
                %% abort! Either ready_commit or do_commit failed
                notice(S, "commit failed", []),
                {stop, {Class, Reason}, S}
            end;
        false ->
            {next_state, ready, S}
    end;
ready(Event, Data) ->
    unexpected(Event, ready),
    {next_state, ready, Data}.

這個大的 try ... catch 表達式是主導 FSM 決定提交如何運作的方式。ask_commit/1 和 do_commit/1 都是同步的。這讓主導 FSM 可以自由地呼叫它們。您可以看到另一個 FSM 只是在那裡等待。然後，它將收到來自主導程序的命令。第一個訊息應該是 ask_commit。這只是為了確保兩個 FSM 仍然存在；沒有發生任何錯誤，它們都致力於完成任務。

ready(ask_commit, _From, S) ->
    notice(S, "replying to ask_commit", []),
    {reply, ready_commit, ready, S};

收到此訊息後，主導程序將要求使用 do_commit 確認交易。這就是我們必須提交資料的時候。

ready(do_commit, _From, S) ->
    notice(S, "committing...", []),
    commit(S),
    {stop, normal, ok, S};
ready(Event, _From, Data) ->
    unexpected(Event, ready),
    {next_state, ready, Data}.

完成後，我們就會離開。主導 FSM 將收到 ok 作為回覆，並且知道之後要自行結束提交。這解釋了為什麼我們需要大的 try ... catch：如果回覆 FSM 死亡或其玩家取消交易，則同步呼叫將在逾時後崩潰。在這種情況下，應中止提交。

只是讓您知道，我將提交函數定義如下：

commit(S = #state{}) ->
    io:format("Transaction completed for ~s. "
              "Items sent are:~n~p,~n received are:~n~p.~n"
              "This operation should have some atomic save "
              "in a database.~n",
              [S#state.name, S#state.ownitems, S#state.otheritems]).

非常普通，是吧？通常不可能僅用兩個參與者進行真正的安全提交，通常需要第三方來判斷兩個玩家是否都做對了所有事情。如果要編寫一個真正的提交函數，它應該代表兩個玩家聯絡該第三方，然後對它們執行安全寫入資料庫或回滾整個交換。我們將不深入探討這些細節，目前的 commit/1 函數對於本書的需求就足夠了。

我們還沒完成。我們尚未涵蓋兩種事件：玩家取消交易以及另一個玩家的有限狀態機崩潰。前者可以使用回呼函數 handle_event/3 和 handle_sync_event/4 來處理。每當另一個使用者取消時，我們都會收到非同步通知。

%% The other player has sent this cancel event
%% stop whatever we're doing and shut down!
handle_event(cancel, _StateName, S=#state{}) ->
    notice(S, "received cancel event", []),
    {stop, other_cancelled, S};
handle_event(Event, StateName, Data) ->
    unexpected(Event, StateName),
    {next_state, StateName, Data}.

當我們執行此操作時，我們絕不能忘記在自己退出之前告訴對方。

%% This cancel event comes from the client. We must warn the other
%% player that we have a quitter!
handle_sync_event(cancel, _From, _StateName, S = #state{}) ->
    notify_cancel(S#state.other),
    notice(S, "cancelling trade, sending cancel event", []),
    {stop, cancelled, ok, S};
%% Note: DO NOT reply to unexpected calls. Let the call-maker crash!
handle_sync_event(Event, _From, StateName, Data) ->
    unexpected(Event, StateName),
    {next_state, StateName, Data}.

瞧！最後要處理的事件是另一個 FSM 關閉時。幸運的是，我們在 idle 狀態中設定了一個監視器。我們可以匹配這個並做出相應的反應。

handle_info({'DOWN', Ref, process, Pid, Reason}, _, S=#state{other=Pid, monitor=Ref}) ->
    notice(S, "Other side dead", []),
    {stop, {other_down, Reason}, S};
handle_info(Info, StateName, Data) ->
    unexpected(Info, StateName),
    {next_state, StateName, Data}.

請注意，即使在我們提交時發生 cancel 或 DOWN 事件，一切都應該是安全的，並且不應該有任何人的物品被盜。

只剩下兩個回呼函式要說明！它們是 code_change/4 和 terminate/3。目前，我們不需要對 code_change/4 做任何事，只是把它匯出，以便 FSM 的下一個版本在重新載入時可以呼叫它。我們的 terminate 函式也很短，因為在這個例子中我們沒有處理真實的資源。

code_change(_OldVsn, StateName, Data, _Extra) ->
 {ok, StateName, Data}.

%% Transaction completed.
terminate(normal, ready, S=#state{}) ->
    notice(S, "FSM leaving.", []);
terminate(_Reason, _StateName, _StateData) ->
    ok.

呼。

現在我們可以試試看。嗯，試用它有點麻煩，因為我們需要兩個程序互相溝通。為了解決這個問題，我把測試寫在 trade_calls.erl 這個檔案中，它可以執行 3 種不同的情境。第一個是 main_ab/0。它會執行一個標準的交易並輸出所有內容。第二個是 main_cd/0，會在交易進行到一半時取消交易。最後一個是 main_ef/0，它和 main_ab/0 非常相似，只是它包含不同的競爭條件。第一個和第三個測試應該成功，而第二個測試應該失敗（會有一大堆錯誤訊息，但就是這樣）。如果你想試試看，可以試試。

這真是太驚人了

如果你覺得這一章比其他章節難一點，我必須提醒你這是完全正常的。我只是瘋了，決定從通用的有限狀態機行為中製造一些難題。如果你感到困惑，問自己這些問題：你是否了解不同的事件如何根據你的程序所處的狀態來處理？你是否了解如何從一個狀態轉換到另一個狀態？你是否知道何時使用 send_event/2 和 sync_send_event/2-3，而不是 send_all_state_event/2 和 sync_send_all_state_event/3？如果你對這些問題的答案都是肯定的，那麼你了解 gen_fsm 是關於什麼的。

其餘的非同步協定、延遲回覆和攜帶 From 變數、為同步呼叫設定程序的優先順序、被閹割的兩階段提交等等，並不是理解的必要條件。它們主要目的是展示可以做什麼，並突顯編寫真正並行軟體的困難，即使是在像 Erlang 這樣的語言中也是如此。Erlang 並不能免除你的規劃或思考，Erlang 也不能為你解決問題。它只會給你工具。

話雖如此，如果你完全理解了這些重點，你可以為自己感到驕傲（尤其是如果你以前從未編寫過並行軟體）。你現在開始真正地並行思考了。

適合真實世界嗎？

在真實的遊戲中，還有更多的事情會讓交易變得更複雜。角色可能會穿戴物品，而物品可能會在交易過程中被敵人損壞。也許物品可以在交換時移入和移出背包。玩家是否在同一個伺服器上？如果不是，你如何同步對不同資料庫的提交？

我們的交易系統在脫離任何遊戲的現實情況下是合理的。在嘗試將其放入遊戲之前（如果你敢的話），請確保一切順利。測試它，測試它，再測試它。你可能會發現，測試並行程式碼是一個完全令人痛苦的事情。你會掉頭髮、失去朋友，以及失去一部分理智。即使這樣之後，你還是必須知道你的系統總是和它最薄弱的環節一樣強，因此仍然可能非常脆弱。

幸運的是，我們可以把所有這些瘋狂拋在腦後。接下來，我們將看到 OTP 如何藉助 gen_event 行為來處理各種事件，例如警報和日誌。

• < 上一頁
• 目錄
• 下一頁 >

除非另有說明，本網站內容以創用 CC 姓名標示-非商業性-禁止改作授權條款釋出