18.1. 有限ステートマシンとはなにか¶

有限ステートマシン（FSM）は実際には機械ではなく、有限個の状態を持ったものです。 私は有限ステートマシンを理解するときは、グラフやダイアグラムで理解したほうが簡単だと気づきました。 例えば、次の図は（とても馬鹿な）犬を状態マシンとして簡潔にダイアグラムにしたものです。

ここで、犬には3つの状態があります。座る（sitting）、吠える（barking）、しっぽをふる（wagging）の3つです。 異なるイベントや入力が状態を変更させるでしょう。 もし犬がおとなしく座っているときに、リスを見かけたら、犬は吠え始め、あなたが撫でてあげるまで吠えるのを辞めないでしょう。 一方で、犬が座っているときにあなたが撫でてあげたら、何が起きるかはわかりません。 Erlangの世界では、犬はクラッシュします。（そしていずれスーパバイザによって再起動されます。） 実世界では、そんなおかしな事は起きませんが、犬が車に轢かれた（クラッシュした）あとに戻ってくるので、すべてが悪いというわけではありません。

比較のために、猫の状態ダイアグラムをみてみましょう：

この猫は1つの状態を持っていて、どんなイベントも状態を変更することはできません。

猫の状態マシンを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でのもう1つの違いは、猫のイベントは同期で、犬のイベントは非同期だった点です。 実際のFSMでは、同期と非同期の両方が混ざって使われますが、まずは一番楽な形で表現してみました。 上の例では、表現できていない形式もあります。たとえば、どのような状態でも起こりうる、グローバルイベントという形式です。

そのようなイベントの一例としては、犬が食べ物の匂いをかぐことです。 一度「匂いがする食べ物」というイベントが起きたら、犬はどんな状態にあっても、食べ物がある場所を探しに行ってしまうでしょう。

こんな「ナプキンの上に描いた」FSMの実装にはもう時間を割くつもりはありません。 かわりに、もう直接 gen_fsm ビヘイビアの話題に移ってしまいましょう。

18.2. 汎用的な有限ステートマシン¶

gen_fsm ビヘイビアは、専用のビヘイビアであるという点で、いくらか gen_server と似ています。 最も大きな違いは、呼び出しやメッセージ投入を扱うのではなく、同期や非同期のイベントを扱っているという点です。 犬や猫の例のように、それぞれの状態は関数によって表現されます。 再び、私たちのモジュールがきちんと動作するために実装する必要があるコールバックについて見ていきましょう。

18.2.1. init¶

これは、受け取れる戻り値が {ok, StateName, Data}, {ok, StateName, Data, Timeout}, {ok, StateName, Data, hibernate}, {stop, Reason} のいずれかであるという点以外は、汎用サーバで使った init/1 と同じものです。 stop のタプルは gen_server と同様の動作をし、 hibernate と Timeout は同じ意味で使われます。

ここで新しいのは StateName 変数です。 StateName はアトムで、次に呼ばれるコールバック関数を表します。

{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}

18.3. 取引システムの仕様¶

いよいよ実践で使ってみる頃合いです。 多くのErlangの有限ステートマシンに関するチュートリアルでは、電話交換器やそれに似たものを含む例を使います。 私の推測では、おそらくほとんどプログラマは状態マシンのために電話交換器を扱うことはほとんどないと思います。 なので、もうちょっと多くの開発者の状況にあった例を見てみましょう。 フィクションで存在しないテレビゲーム向けのアイテム取引システムを設計し、実装してみましょう。

私が選んだ設計はいくらか困難ですがやりがいは感じられると思います。 プレーヤーがその人を通じてアイテムのやり取りをするようなブローカーは使わずに（ざっくり言うと、使うほうが、楽なのですが）、プレーヤー同士が直接やり取りできるようなサーバーを実装します。（この実装の方が、分散する際に有利です）

実装は手が込んでいますので、説明には長い時間を書けます。例えば直面しうる問題や、その修正方法についても触れていきます。

まず初めに、プレーヤーが取引をする際にとりうるアクションを定義しましょう。 1つ目は取引の申し入れです。他方のユーザもその取引を受け入れられるべきです。 しかしながら、単純化のために、ユーザに取引を拒否する機能は与えません。 実装がひと通り終わったら、拒否の機能を追加するのは簡単でしょう。

取引が始まったら、ユーザはお互いに交渉できるべきです。 これはつまり、ユーザは提案をし、望めば撤回できるということです。 両方のプレーヤーが提案に満足したら、プレーヤーはそれぞれ取引を完了させる準備が出来たと宣言出来ます。 その後両者のデータが保存されます。 どのタイミングにおいても、いずれのプレーヤーも取引をキャンセルすることも出きるべきです。 平民の中には他のパーティー（とても忙しいかもしれない人々）には価値がないと思われるアイテムだけしか提示できない人もいるので、それに値するキャンセル処理によって提案を引っ込めさせることが出来るべきでしょう。

簡単にまとめると、次のようなアクションが考えられます：

• 取引を申し入れる
• 取引を受け入れる
• アイテムを提示する
• 提案を撤回する
• 取引の準備が出来たと宣言する
• 取引を強制的にキャンセルする

いま、これらのアクションが取られたとして、他のプレーヤーのFSMもそれに気づくべきです。 これは当然のことです。なぜなら、JimがFSMに対して、Carlにアイテムを送るように伝えた時、CarlのFSMはそれに気づかなければいけません。 つまり、プレーヤーは両方共自身のFSMと相手のFSMに対して話すことが出来ます。 このことは次のような図で考えられます：

2つの独立したプロセスがお互いにやり取りしているときに最初に気づくべきことは、できる限り同期呼び出しを避けることです。 その理由は、JimのFSMがCarlのFSMにメッセージを送ってから返信を待つ一方で、同時にCarlのFSMがJimのFSMにメッセージを送ってその返信を待ってしまった場合、両方共他方の返信待ったままになってしまいます。 これにより両方のFSMは固まってしまいます。 つまりデッドロックです。

この問題の解決方法の1つは、タイムアウトを設定して、それ以上経ったら次へ移ることです。 しかし、その時両方のプロセスのメールボックスにメッセージが残っていて、このやりとりはめちゃくちゃになってしまいます。 これは確実に複雑で解決困難な問題なので、出来れば避けたいところです。

最も単純な方法は、同期メッセージを使うことをやめ、すべて非同期にすることです。 それでもなおJimは自分のFSMに対して同期呼び出しをすることに注意して下さい。FSMがJimを呼び出すことは無いですし、したがってJimとFSMの間でデッドロックは起こり得ないので、この場合は安全だからです。

2つのFSMがお互いにやりとりしている場合、取引の全体は次ような流れになるでしょう：

2つのFSMは両方共アイドル状態にあります。 あなたがJimに取引を持ちかけた時、Jimは取引を進める前に取引を受け入れなければいけません。 それから、両者ともにアイテムを提示したり、取り下げたりします。 両者が取引の準備が出来た時に、取引が行われます。 これが起こりうる状態の簡素版で、以降の段落で考えられるすべての状況を見ていきます。

大変な部分がやって来ました。状態ダイアグラムと状態遷移を定義します。 通常、ここでかなりのことを考える必要が出てきます。なぜなら、どんな些細な事でも、おかしくなりそうな事はすべて考えなければいけないからです。 何度見なおした後でも、いくつかの状況は自体をおかしくしてしまいます。 このような理由から、私は1つ実装することを定め、それからその説明をします。

まずはじめに、2つの有限ステートマシンは両方共アイドル状態にあります。 この時、私達ができることは、相手のプレーヤーに取引を持ちかけることだけです：

私たちのFSMが要求を伝えたあと、最終的な返事を待つために idle_wait モードになります。 一度相手のFSMが返信を送ったら、私たちのFSMは negotiate に切り替わります：

他のプレーヤーもその後 negotiate 状態になるでしょう。 明らかに、私たちが相手を招待したら、相手も私たちを招待できます。 すべてが上手くいったら、次の様になるでしょう：

これは、前の2つの状態ダイアグラムが1つになったものとは真逆です。 このとき私たちはプレーヤーが提案を受け入れてくれると期待していることに注意して下さい。 もし本当に偶然に、相手もちょうど取引したいと申し込んできた時に他のプレーヤーに取引を申し込んだら、何が起きるでしょうか。

このとき、両方のクライアントが自分のFSMに相手のFSMに交渉するように言います。 交渉依頼のメッセージが送られるとすぐに、両方のFSMは idle_wait 状態に切り替わります。 その後、交渉のやりとりを開始することが出来ます。 前の状態ダイアグラムをもう一度見てみると、このイベントの組み合わせは、 idle_wait 状態のときに交渉依頼のメッセージを受け取る唯一の場合です。 結果的に、これらのメッセージを idle_wait で受け取ることは競合状態になったとわかり、両ユーザともにお互いに話したいのだと推測することが出来ます。 両ユーザを negotiate 状態に移すことが出来ます。 やったね！

さて、交渉の段階となりました。先に挙げたアクションのリストによると、ユーザがアイテムを提示して、提案を撤回する機能をサポートしなければなりません：

ここで行なっていることは、クライアントのメッセージを相手のFSMに転送しているだけです。 両者の有限ステートマシンは、そのようなメッセージを受け取ったときに更新できるように、相手のプレーヤーから提示されたアイテムのリストを保持しておく必要があるでしょう。 メッセージを送信したあとは negotiate 状態にとどまります。おそらく相手プレーヤーもアイテムを提示したいと思っているはずですから。

ここで、私たちのFSMも基本的には同様に動作します。 これが通常の流れです。 アイテムの提示に飽きて、もう十分良い提示ができたと思ったら、取引を公表する準備ができたと言う必要があります。 両プレーヤーの同期を取らなければいけないため、 idle と idle_wait でそうしたように、中間の状態を使う必要があるでしょう。

ここでは、私たちのプレーヤーが準備完了したらすぐに、私たちのFSMはJimのFSMに彼も準備ができているかを尋ねます。 その返事を待ってから、私たちのFSMは wait 状態に代わります。 受け取るであろう返答はJimのFSMの状態に依ります。もし相手も wait 状態であれば、準備ができたと伝えてくるでしょう。そうでなければ、まだ準備ができていないと返答するでしょう。 これは、彼が私たちが negotiate 状態のときに準備ができたか聞いてきたときに、私たちのFSMがJimに自動的に返信するものでもあります：

私たちの有限ステートマシンは、私たちのプレーヤーが準備ができたと言うまで negotiate モードであり続けます。 私たちのプレーヤーの準備が完了したとして、いまは wait 状態にあるとします。 しかし、Jimはまだ準備ができていません。 つまり、私たちは自分は準備ができたと宣言したときに、Jimにも準備ができたかを聞いたけれど、彼のFSMは「まだだ」と返信した、ということです：

彼はまだだけど、私たちは準備ができました。 私たちにできるのは待つことだけです。 ところで、Jimを待つ間、誰がまだ交渉しているのでしょう。 Jimがもっとアイテムを提示しようとしたり、前の提案をキャンセルする可能性もあります：

もちろん、Jimがすべてのアイテムを削除してから’ready!（準備完了！）’をクリックして、私たちを騙そうとするようなことは避けたいところです。 彼が提示するアイテムを変更したらすぐに、私たちの提案を修正したり、いまの提示を見て準備ができているか確認できるように、 negotiate 状態に戻ります。 仕切り直しで、繰り返しです。

ある時点で、Jimも取引を完了させる準備ができるでしょう。 そうなったときに、彼の最終的な状態マシンが私たちに準備ができたか訊いてきます：

私たちのFSMがすることは、私たちは実際準備完了していると返信することです。 しかし、 wait 状態に留まって、 ready 状態に移行することはしません。 なぜでしょうか。 なぜなら、潜在的な競合状態に陥る可能性があるからです！ 次のようなイベントのシーケンス図を見て、今言ったような必要な段階を経なかった場合にどうなるか想像してみてください：

これは少し複雑なので、説明しましょう。 メッセージの受け取られ方を見ると、私たちが準備完了したと宣言した後で、Jimも準備完了したあとには、おそらくアイテム提示の処理だけは出来ました。 これはつまり、提案のメッセージを読んだ後すぐに negotiate 状態に戻る、ということです。 その間に、Jimが私たちに準備完了したと言いました。 もし彼がそこですぐに状態を変更して、 ready になってしまったら（上図に示したとおり）、彼は一体全体何をしていいかわからないまま、いつまでも待たされることになるでしょう。 これは私たちが待たされるという逆のパターンで起きるだけではなく、私たちとJimに同時にも起こりうるのです。つまり二重の競合状態です！ あちゃー。

これを解決する方法の1つとして、間接参照の層を設けることがあります。（David Wheeler氏に感謝します） これが、（先の状態ダイアグラムで示したように）私たちが wait モードに留まって ‘ready!’ のメッセージを送った理由です。 次に、どのように ‘ready!’ メッセージを扱うか見ていきましょう：

‘ready!’ を受け取った時、私たちも再度 ‘ready!’ を送り返します これは上で言ったような競合状態にならないようにするためです。 それあと、 ready 状態に移る前に ‘ack’ メッセージを送ります。（JimのFSMも同様にします。） ‘ack’ メッセージが存在する理由は、クライアントを同期するための実装に関わっているからです。 正確さを期すために、 ‘ack’ についてダイアグラムに描きましたが、これについてしばらくは説明しません。 これについてはいまは忘れましょう。 ついに、両プレーヤーをなんとか同期することができました。 やれやれ。

さあ、 ready 状態になりました。 この状態はちょっと特別です。 両プレーヤーは準備ができていて、基本的には有限ステートマシンに必要な制御をすべて委ねています。 取引を公表する際に、物事が正しく処理されるように、低品質版の2フェーズコミットを実装してみましょう。

（上で説明したとおり）私たちのバージョンはかなり単純化されています。 本当に正確な2フェーズコミットを書くには、私たちが有限ステートマシンを理解するのに必要なコード量よりも、もっとずっと多くのコードが必要です。

最後に、取引をいつでもキャンセルできるようにするだけになりました。 これは、どうにかして、どのような状態にいても、両者から ‘cancel（キャンセル）’ メッセージを聴いて、トランザクションを終了する、ということを意味します。 取引の場から去る前に相手にその旨をお知らせするのも礼儀でしょう。

さあ、準備ができました！ 一度に理解するには大きすぎる情報量になってしまいました。 全体を理解するのに時間がかかってしまうとしても心配しないでください。 多くの方々に、私のプロトコルが正しいかどうかレビューしてもらった後でさえ、この文章を書いているときにコードをレビューしていて、先に挙げたようないくつかの競合状態に気づき、全員がそれを見逃していたのでした。 二度以上読む必要が出てくることは普通なのです。あなたが非同期プロトコルに慣れていないのであればなおさらです。 もしあなたが非同期プロトコルに慣れていないのであれば、自分でプロトコルを設計してみることを心からお勧めします。 そのときに、「もし両者が同じ動作をとても早く行ったらどうなるだろうか？彼らが2つのイベントを素早く連続で行ったら何がおこるだろうか？状態を変えるときに扱っていないメッセージが来たらどうすればいいだろうか？」といった質問を自問してみてください。 きっと複雑さがあっという間に膨らむのがわかるでしょう。 きっと私がこれまで説明してきたものと似た解決方法を見つけるでしょう。あるいは私のものよりも良い物かもしれません。（そのときは私に教えてください！） 結果がどうあれ、こうしたプロトコルを考え、実装するのはとても面白いものです。そして私たちのFSMは今もなお比較的簡潔です。

これまでの説明をすべて理解したら（あるいは、あなたが反抗的に、理解する前に読み進めているのなら）、いよいよ次の節へ進んで、ゲームシステムを実装できます。 ひとまず、コーヒーブレイクをしたい方は、このへんでどうぞ。

18.4. 2プレーヤーのゲーム内取引¶

私たちのプロトコルを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}).

さて、残りにとりかかりましょう。 残っているのは、準備完了しているかどうか、と最後のコミットに関わる部分です。 再度確認ですが、上記のプロトコルによれば、私たちは3つの呼び出しがありました。 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が自分自身に返すデータ内に、それが表すユーザのために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]).

まず idle 状態から始めることができます。 規則に従って、まず非同期版から実装します。 こちらの場合は、私たちのプレーヤーが同期呼び出しを使うという前提で、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}.

モニターが死にそうな相手側のプロセスを処理するために設定されていて、 idle_wait 状態に移行する前に、その参照はFSMのデータ内に相手のpidと一緒に保存されています。 予期しないメッセージが来たときは、すべてレポートだけして無視して、そのときにいる状態に留まる、ということに注意してください。 いくつかアウトオブバンドメッセージを用意することはできますが、それを取り除くことは容易ではありません。 これらの、想定外だけれども予測が可能がメッセージで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 状態になるまでに2トランザクションがかかりますが、 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.

単純ですが、実装から(アイテムを追加したり削除する)アクションを(リストを使って)孤立させる働きをしています。 他の部分のコードを壊すことなく簡単にproplistや配列、あるいはどんなデータ構造に移行できます。

これらの関数を両方つかって、アイテムの提示と撤回を実装できます:

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同士のやりとりを区別するためだけに使われています。 私たちのプレーヤーから来るメッセージでは、相手側に私たちが行おうとしている変更を伝えなければいけないことに留意してください。

他にも、プロトコル内で言及した 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 状態への遷移が行われるべきです。 ただ相手の返事を待つのは面白いくないですよね。 クライアントに何かを伝えることがあるときには、 gen_fsm:ready/2 で使えるように From 変数を残しておいたのでした。

wait 状態はやんちゃな獣です。 相手が準備が出来ていないために、新しいアイテムが提示されたり撤回されたりするでしょう。 そのときに negotiate 状態に自動的にロールバックするのは納得がいきます。 私たちに素晴らしいアイテムが提示されたのに、結局相手がアイテムを撤回して準備ができたと宣言して、私たちから略奪するのは、最悪です。 交渉に戻るのは良い決断です：

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 に保存した座標を使ってプレーヤーに返信します。 ready 状態に遷移して取引を確認できるように、私たちが次に気にしなければいけないメッセージは、両方のFSMを同期するようなメッセージです。 このメッセージに関して、先に定義したプロトコルによく注目するべきです。

私たちが受け取れる3つのメッセージは are_you_ready （相手のユーザが準備ができたと宣言したため）と not_yet （相手に準備が出来たか尋ねて、まだだったため）と ready! （相手に準備ができたか尋ねて、そうだったため）でした。

まず are_you_ready の場合について見てみましょう。 プロトコルでは、このとき競合状態になりうると言ったことを思い出してください。 ここでできることは、 ready! メッセージを am_ready/1 で送って、あとで残りを処理するだけでした：

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};

再び待っている状態で留まるので、まだ私たちのクライアントに返信する意味はありません。 同様に、相手が私たちの are_you_ready の確認に対して not_yet を送ってきたときは、クライアントに返信しません：

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

一方で、相手が準備できてる場合、余分に ready! メッセージを相手のFSMに送って、ユーザに返信をしてから、 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は両方とも周りがどうなっていようが気にせずに、お互いに自由に話しかけることができます。 これによって、私たちの低品質版の2フェーズコミットを実装することができます。 このコミットを他プレーヤーのアクションなしにはじめるために、FSMからきっかけとなるイベントを送ってもらう必要があります。 ack_trans/1 から送られる ack イベントがそれにあたります。 準備完了状態になったらすぐに、そのメッセージが処理され、それをきっかけにアクションが行われます。つまりトランザクションが始められます。

けれども2フェーズコミットには同期コミュニケーションが必要です。 これは、デッドロックになってしまうので、両方のFSMが同時にトランザクションを始めることはできないということです。 鍵となるのは、どちらのFSMがコミットを開始し、どちらが留まって最初のFSMからの命令を待つかを決める方法を見つけることです。

Erlangを設計したエンジニアと計算機科学者がかなり賢い人々だったということがわかりました。（すでに知っていたことではありますが） どんなプロセスでもpidは比較可能でソート可能です。 これは、いつプロセスが生成されたとしても、それがまだ生きているとしても死んでいても、あるいは、プロセスが他のVMから来たものだとしても（これについては分散Erlangで触れます）、可能です。

2つのpidは比較可能で、あるpidは他方のpidよりも大きい、という前提で、2つのpidを引数として、あるプロセスが選ばれたかどうかを知る priority/2 関数を書くことができます：

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

そして、この関数を呼ぶことで、1つのプロセスがコミットを始め、他方がそれを追うことが出来ます。

この関数によって、 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/ はともに同期的です。 したがって最初に処理するFSMは自由にそれらを呼び出すことができます。 他方のFSMはただ待つだけだとわかります。 その後、最初のFSMプロセスから命令を受け取ります。 最初のメッセジーは ask_commit になるでしょう。 これは両FSMがまだそこにあることを確認するためだけのものです。つまり、正しく動作していて、両方共タスクを完了させようとしています：

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

ask_commit が受信されたら、先に処理をしたプロセスが 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が死んだり、そのFSMに対応するプレーヤーがトランザクションをキャンセルしたら、同期呼び出しがタイムアウト後にクラッシュします。 コミットはこの場合中止させられるべきです。

おわかりのとおり、次のように commit 関数を定義しました：

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]).

かなりつまらないですよね？ 一般的に、真に安全なコミットを2者の関係性だけで行うことは出来ません。―両プレーヤーがすべて正しく処理したかを判断するために、通常第3者が必要となります。 もしあなたが本当の commit 関数を書こうと思ったら、その関数が両プレーヤーの代わりにその第3者に連絡を取って、彼らの代わりにデータベースに安全な書き込みをするか、あるいは全変更をロールバックします。 この詳細に関しては触れませんし、本書で求めてる程度であれば現状の current/1 関数で十分です。

まだ終わりではありません。まだ2種類のイベントについて触れていません。それはプレーヤーが取引をキャンセルすることと、相手のFSMがクラッシュした場合です。 前者は 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 イベントが起きたとしても、すべて安全で、、だれもアイテムを盗まれない、ということに留意してください。

あと2つのコールバックだけ扱う必要があります！ code_change/4 と terminate/3 です。 いまのところ、 code_change/4 ですることは何もなく、次のバージョンのFSMがリロードされたときにその関数を呼べるように、エクスポートだけしておきます。 この例では実際のリソースを扱ってないので terminate/3 関数も本当に短いものです：

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.

やっと終わりました。

これで試して見ることが出来ます。 さて、このモジュールを試してみるのはいささか面倒です。なぜなら、2つのプロセスをお互いにやりとりさせる必要があるからです。 これを解決するために、 trade_calls.erl というファイルにテストを書きました。ここでは3つの異なるシナリオを実行します。 1つ目は main_ab/0 です。 これは標準の取引を実行し、すべてを出力します。 2つ目は main_cd/0 で、途中でトランザクションをキャンセルします。 最後は main_ef/0 で、 main_ab/0 によく似ていますが、異なる競合状態を含んでいる点が違います。 1つ目と3つ目は成功し、2つ目は失敗します。（大量のエラーメッセージが出ますが、何が起きたかが書いてあります） 気に入ったらぜひ使ってテストしてみてください。

18.5. たいしたもんです¶

もしあなたがこの章が他の章よりもちょっときついと感じたとしても、それはまったくもって普通だとお伝えしておきます。 私がちょっといかれて、汎用的な有限ステートマシンビヘイビアからなにか大変な物を作ると決めてしまったのです。 もし混乱してしまったとしたら、こう自問してみてください。「あなたは、プロセスがどの状態にあるかでイベントの扱われ方がどう異なるか理解できましたか？」「あなたはどうやってある状態から別の状態への遷移できるか理解しましたか？」「いつ send_event/2 と sync_send_event/2-3 を使って、逆にいつ send_all_state_event/2 と sync_send_all_state_event/3 を使うかわかりますか？」 もしこれらの質問に「はい」と答えられるなら、 gen_fsm が何か理解したと言えましょう。

非同期プロトコルの残りの部分、遅延リプライや From 変数の引き回し、同期呼び出しの際のプロセスの優先順位付け、劣化版2フェーズコミット、などなどは理解する本質ではありません。 これらは、何ができるかを見せるため、そして、Erlangのような言語でさえ、真に並列なソフトウェアを書くことの難しさを強調するために、見せたようなものです。 これらは道具に過ぎないのです。

とはいえ、これらをすべて理解できたら、それは誇りに思っていいでしょう。（特に過去に並列プログラミングをしたことが一度もなければ） あなたは、いま並列について本当に考え始めたところなのです。

18.6. 実世界に適用できるの？¶

実際のゲームでは、取引をもっとずっと複雑にすることが、ずっと多く行われています。 アイテムは取引される一方で、キャラクターによって使い古され、敵によってダメージを与えられます。 おそらく、アイテムは交換されている間にアイテムリストに出入りするでしょう。 プレーヤーは同じサーバにいますか。 そうでないとしたら、異なるデータベースへのコミットをどのように同期しますか。

私たちの取引システムは、どんなゲームの実際から切り離された場合には正常です。 （無謀にも）ゲームに適用させようとする前に、すべてがきちんと動いていることを確認してください。 テストして、テストして、再度テストしてください。 おそらく、並列で並行なコードをテストするのは完全に苦痛だと分かるでしょう。 頭もハゲて、友達も失って、正気も失うでしょう。 こんな状態になった後でさえも、あなたのシステムは常に最弱リンクほどにしか強くなく、潜在的にとても脆いものだと知る必要があります。

幸いにも、これらの狂気をうしろに置いておくことができます。 次の章では、OTPでは gen_event ビヘイビアの助けを借りて、アラームやログといった様々なイベントをどのように扱えるを見ていきます。