Erlang入門

素晴らしいために！

• ホーム
• FAQ
• RSS
• コード

有限状態機械への反逆

それらとは何か？

有限状態機械（FSM）は実際には機械ではありませんが、有限個の状態を持ちます。私は常に、グラフや図表を使って有限状態機械を理解するのが簡単だと感じています。例えば、次の図は（非常に愚かな）犬を状態機械として単純化したものです。

ここでは、犬には座っている、吠えている、尻尾を振っているという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では、両方混合して使用できますが、純粋な怠惰さから最も単純な表現を選択しました。例では示されていない他の形式のイベントもあります。任意の状態に発生する可能性のあるグローバルイベントです。

そのようなイベントの1つの例として、犬が食べ物の匂いを嗅いだ場合が挙げられます。`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_fsm:reply/2を含め、`gen_server`とまったく同じ方法で使用されます。`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/3`と同じパラメータを取り、同じ種類のタプルを返します。

イベントがグローバルであるか、特定の状態に送信されるべきであるかをどのように判断するかを説明するのに良いタイミングかもしれません。これを判断するには、FSMにイベントを送信するために使用される関数を確認します。任意の`StateName/2`関数に向けられた非同期イベントはsend_event/2で送信され、`StateName/3`で受信される同期イベントはsync_send_event/2-3で送信されます。

グローバルイベントに対する2つの同等の関数は、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と通信することを意味します。これにより、次のような状況になります。

2つの同一のプロセスが互いに通信する場合、最初に注意すべき点は、同期呼び出しをできる限り回避する必要があることです。その理由は、JimのFSMがCarlのFSMにメッセージを送信し、応答を待機している間に、同時にCarlのFSMがJimのFSMにメッセージを送信し、独自の応答を待機すると、どちらも応答することなく、互いを待ち続けることになるからです。これにより、両方のFSMが事実上フリーズします。デッドロックが発生します。

これに対する1つの解決策は、タイムアウトを待ってから先に進むことですが、そうすると両方のプロセスのメールボックスにメッセージが残ってしまい、プロトコルが混乱します。これは間違いなく厄介な問題であり、回避したいと考えています。

最も簡単な方法は、すべての同期メッセージを回避し、完全に非同期にすることです。Jimは自分のFSMへの同期呼び出しを行う可能性がありますが、FSMはJimを呼び出す必要がないため、それらの間でデッドロックが発生するリスクはありません。

2つのFSMが通信する場合、全体の流れは次のようになります。

両方のFSMはアイドル状態です。Jimと取引を要求する場合、先に進む前にJimが受け入れる必要があります。その後、両方でアイテムを提供したり、取り消したりできます。両方が準備完了を宣言したら、取引を実行できます。これは起こりうるすべての出来事の簡略版であり、以降の段落でより詳細に可能性のあるすべてのケースを見ていきます。

ここからが難しい部分です。状態図と状態遷移の定義です。あらゆる小さな問題点を考えなければならないため、通常はかなりの量の検討が必要です。何度も見直した後でも、問題が発生する可能性があります。そのため、ここでは実装することにした状態図を示し、それを説明します。

まず、両方の有限状態機械は`idle`状態から開始します。この時点で、他のプレイヤーに交渉を依頼することができます。

FSMが要求を転送した後、最終的な応答を待機するために`idle_wait`モードになります。相手のFSMが応答を送信すると、自分のFSMは`negotiate`に切り替えることができます。

その後、相手プレイヤーも`negotiate`状態になるはずです。明らかに、私たちが相手を招待できるなら、相手も私たちを招待できます。すべてがうまくいけば、最終的には次のようになります。

これは、前の2つの状態図を1つにまとめたものとほぼ反対です。この場合、プレイヤーがオファーを受け入れることを期待していることに注意してください。運悪く、私たちが相手プレイヤーに取引を要求したと同時に、相手プレイヤーも私たちに取引を要求した場合、どうなるでしょうか？

ここで起こることは、両方のクライアントが自分の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`状態の場合は、準備ができていることを伝えます。そうでない場合は、まだ準備ができていないことを伝えます。`negotiate`状態の場合、Jimが準備ができているかどうかを尋ねたときに、私たちのFSMがJimに自動的に応答するのはまさにこれです。

プレイヤーが準備完了を言うまで、有限状態機械は`negotiate`モードのままです。プレイヤーが準備完了を言ったと仮定し、`wait`状態になったとします。しかし、Jimはまだそこにはいません。つまり、準備完了を宣言したときに、Jimに準備ができているかどうかを尋ね、彼のFSMが「まだ」と答えたことを意味します。

彼は準備ができていませんが、私たちは準備ができています。待っている以外に何もできません。まだ交渉中のJimを待っている間、彼はさらにアイテムを送信しようとしたり、以前のオファーをキャンセルしようとしたりする可能性があります。

もちろん、Jimがすべてのアイテムを削除してから「準備完了！」をクリックして、その過程で私たちを出し抜くことを避けたいと考えています。彼が提供されたアイテムを変更するとすぐに、`negotiate`状態に戻り、独自のオファーを変更したり、現在のオファーを調べたりして、準備完了であるかどうかを決定できます。繰り返します。

ある時点で、Jimも取引を確定する準備が整います。これが発生すると、彼の有限状態機械は、私たちが準備ができているかどうかを尋ねます。

私たちのFSMが行うのは、私たちが確かに準備ができていると答えることです。しかし、`wait`状態にとどまり、`ready`状態に移行することを拒否します。なぜでしょうか？潜在的な競合状態があるからです！この必要な手順を実行せずに、次のイベントシーケンスが発生すると想像してみてください。

これは少し複雑なので、説明します。メッセージの受信方法のため、準備完了を宣言した後、そしてJimが準備完了を宣言した後で、アイテムのオファーを処理できる可能性があります。これは、オファーメッセージを読み取るとすぐに、`negotiate`状態に戻ること意味します。その間、Jimは準備完了であることを伝えます。彼がそこで状態を切り替えて`ready`に移行した場合（上記のようにイラスト化されています）、彼は私たちが何をすべきかわからない間、無期限に待たされることになります。これは逆にも起こり得ます！うー。

これを解決する1つの方法は、間接化レイヤーを追加することです（David Wheelerのおかげです）。これが、`wait`モードにとどまり、「準備完了！」を送信する理由です（前の状態図に示されているとおり）。事前にFSMに準備完了であることを伝えたため、すでに`ready`状態にあったと仮定して、その「準備完了！」メッセージをどのように処理するかを以下に示します。

相手のFSMから「準備完了！」を受信すると、「準備完了！」を再度送信します。これは、上記の「二重競合状態」が発生しないようにするためです。これにより、2つのFSMのいずれかに余分な「準備完了！」メッセージが作成されますが、この場合は無視する必要があります。次に、「ack」メッセージを送信します（そしてJimのFSMも同じことを行います）。その後、`ready`状態に移動します。この「ack」メッセージが存在する理由は、クライアントを同期化するという実装の詳細によるものです。正しくするために図に追加しましたが、後で説明します。今は忘れてください。ついに両方のプレイヤーを同期させることができました。ふー。

これで`ready`状態になりました。これは少し特殊な状態です。両方のプレイヤーが準備完了であり、基本的に有限状態機械に必要なすべての制御権を与えています。これにより、取引を正式化する際に問題が発生しないように、2フェーズコミットの悪名高いバージョンを実装できます。

上記で説明したバージョンは非常に単純です。真に正しい2フェーズコミットを作成するには、有限状態機械を理解するために必要なものよりもはるかに多くのコードが必要です。

最後に、いつでも取引をキャンセルできるようにする必要があります。つまり、どのような状態であっても、両側から「キャンセル」メッセージを聞き取り、トランザクションを終了します。出発する前に相手に知らせることもマナーです。

よし！一度に吸収するにはたくさんの情報があります。完全に理解するのに時間がかかっても心配しないでください。プロトコルが正しいかどうかを確認するために多くの人が私のプロトコルを確認し、それでもいくつかの競合状態を見逃し、このテキストを書いている間にコードを見直した数日後に発見しました。特に非同期プロトコルに慣れていない場合は、複数回読む必要があるのは普通のことです。これが当てはまる場合は、独自のプロトコルを設計することを強くお勧めします。「2人が非常に速く同じアクションを実行した場合どうなるか？2つのイベントをすばやく連鎖させた場合どうなるか？状態を変更するときに処理しないメッセージをどうするか？」と考えてみてください。複雑さが急速に増加することがわかります。私のものと似た解決策、おそらくより良い解決策が見つかるかもしれません（これが当てはまる場合は教えてください！）結果に関係なく、これは非常に興味深い作業であり、私たちのFSMはまだ比較的単純です。

これらすべてを消化した後（または反逆的な読者であればその前でも）、ゲームシステムを実装する次のセクションに進むことができます。今は、コーヒーブレイクを取っても構いません。

2人のプレイヤー間のゲーム取引

OTPの`gen_fsm`でプロトコルを実装するために最初に必要なことは、インターフェースを作成することです。モジュールには、プレイヤー、`gen_fsm`ビヘイビア、相手のFSMの3つの呼び出し元があります。ただし、プレイヤー関数と`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間関数を実装します。最初の関数は取引の設定に関わり、最初に他のユーザーに取引への参加を依頼する場合に使用します。

%% 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に取引を希望するかを問い合わせ、2番目の関数は（もちろん非同期的に）それに返信するために使用されます。

次に、オファーの提示と取り消しを行う関数を記述できます。上記のプロトコルによると、これらがその関数です。

%% 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が表すユーザーの名前を（出力が見やすくなるように）保持するデータに保持したいと考えています。他にメモリに保持したいものがありますか？ここでは、相手側の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}.

相手が死んだ場合を処理するためにモニターが設定され、その参照は相手側の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」状態への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、配列、またはその他のデータ構造に移行できます。

これらの2つの関数を使用することで、アイテムの提示と削除を実装できます。

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への通信を区別するためにのみ使用されます。独自のプレイヤーからのメッセージでは、変更内容を相手側に伝える必要があります。

もう1つの責任は、プロトコルで説明した「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」状態に移行し、取引を確認することに関連するメッセージです。このためには、先に定義したプロトコルに集中する必要があります。

考えられる3つのメッセージは「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};

一方、相手が準備ができている場合は、追加の「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!」状態で何が起こっているかを見始める必要があります。

「ready」状態では、両方のプレイヤーのアクションは（キャンセルを除いて）無効になります。新しいアイテムのオファーは気にしません。これにより、ある程度の自由が得られます。基本的に、両方のFSMは、世界の他の部分を気にすることなく、自由に互いに通信できます。これにより、2フェーズコミットの悪用を実装できます。どちらのプレイヤーも行動することなくこのコミットを開始するには、FSMからアクションをトリガーするイベントが必要です。「ack_trans/1」からの「ack」イベントがそれのために使用されます。「ready」状態になったらすぐにメッセージが処理され、処理が行われます。トランザクションを開始できます。

ただし、2フェーズコミットには同期通信が必要です。つまり、両方のFSMが同時にトランザクションを開始することはできません。デッドロックになります。秘密は、1つの有限状態マシンがコミットを開始し、もう1つのマシンが最初のマシンからの指示を待つ方法を見つけることです。

Erlangを設計したエンジニアとコンピューター科学者は非常に賢かったようです（まあ、それはすでに知っていました）。任意のプロセスのpidは互いに比較してソートできます。これは、プロセスがいつ生成されたか、まだアクティブかどうか、別のVMから来たかどうかに関係なく実行できます（分散Erlangについて説明するときに、これについて詳しく説明します）。

2つのpidを比較して、一方の方が大きくなることがわかっているため、2つのpidを受け取り、プロセスが選出されたかどうかを伝える「priority/2」関数を記述できます。

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

そして、その関数を呼び出すことで、1つのプロセスがコミットを開始し、もう1つのプロセスが指示に従うことができます。

「ack」メッセージを受信した後、「ready」状態に含めると、これが得られます。

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

かなり underwhelmingでしょう？一般的に、参加者が2人だけの場合、真に安全なコミットを行うことはできません。両方のプレイヤーがすべて正しく行ったかどうかを判断するために、通常は第三者が必要です。真のコミット関数を作成する場合は、両方のプレイヤーに代わってその第三者に連絡し、その後、データベースへの安全な書き込みを行うか、交換全体をロールバックする必要があります。ここではそのような詳細には踏み込みません。この本のニーズには、現在のcommit/1関数が十分です。

まだ完了していません。プレイヤーによる取引のキャンセルと、他のプレイヤーの有限状態マシンのクラッシュという2種類のイベントはまだ網羅していません。前者は、コールバック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}.

そして、 voilà！最後に処理するイベントは、他の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が再ロードされたときに呼び出せるようにエクスポートするだけです。この例では実際の資源を処理していないため、終了関数も非常に短くなっています。

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つのプロセスが必要なため、試すのは少し面倒です。これを解決するために、3つの異なるシナリオを実行できるtrade_calls.erlファイルにテストを作成しました。最初のものはmain_ab/0です。標準的な取引を実行し、すべてを出力します。2番目はmain_cd/0で、取引の途中でキャンセルします。3番目はmain_ef/0で、main_ab/0と非常によく似ていますが、異なる競合状態を含んでいます。最初のテストと3番目のテストは成功するはずですが、2番目のテストは失敗するはずです（大量のエラーメッセージが表示されますが、そういうものです）。試してみたい場合は、試してみてください。

それはかなり大変でした

他の章よりもこの章が少し難しかったと感じた場合は、それは全く普通のことだと申し上げておきます。私はただ気が狂って、一般的な有限状態マシン動作から何か難しいものを作り出すことに決めました。混乱を感じた場合は、次の質問を自問自答してみてください。プロセスがどの状態にあるかに応じて、さまざまなイベントがどのように処理されるかを理解できますか？ある状態から別の状態へどのように遷移できるかを理解していますか？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動作の助けを借りて、アラームやログなどのさまざまなイベントをどのように処理できるかを見ていきます。

• < 前へ
• 目次
• 次へ >

特に明記されていない限り、このサイトのコンテンツはクリエイティブ・コモンズ表示-非営利-継承ライセンスの下でライセンスされています。