あまり強調されないようですが、Erlangでは、その構文と実行メカニズムとがあいまって、状態遷移のプログラミングがとても容易です。
例題として、正規表現 /aa?b*c/ とマッチする文字列を認識するオートマトンを作ってみましょう。まず、状態遷移図を描き*1、それから遷移表を書きます。図と表のなかで、EOSは End Of String のマーカー、◎は終状態です
遷移表： 0から3までの各状態について、入力ごとの遷移先は次の通り。×はエラーです。
| 状態 | 文字a | 文字b | 文字c | EOS | その他 |
|---|---|---|---|---|---|
| 0 | 1 | × | × | × | × |
| 1 | 2 | 2 | 3 | × | × |
| 2 | × | 2 | 3 | × | × |
| 3 | × | × | × | ◎ | × |
この表を見ながら、Erlangコードを書きます。以下のような感じ。
accept(N) -> % 引数Nが状態
case N of
0 ->
receive
$a ->
accept(1);
_ ->
exit(error)
end;
1 ->
receive
$a ->
accept(2);
$b ->
accept(2);
$c ->
accept(3);
_ ->
exit(error)
end;
2 ->
receive
$b ->
accept(2);
$c ->
accept(3);
_ ->
exit(error)
end;
3 ->
receive
0 -> % End Of String
exit(normal);
_ ->
exit(error)
end
end.
Erlangでは、文字'a'を $a と書きます（文字番号の整数値に過ぎないけど）。End Of Stringマーカーには数値0を使いました。_（アンダスコア）は「その他の入力」の意味です。オートマトンによる受理が成功すればnormalでプロセスを終了し、失敗ならerrorでプロセスを終了します。あまりにも表のまんまなんで笑っちゃうでしょ。
オートマトンの本体はとても簡単ですが、フロントエンドのプロセスのほうが少しめんどうです。次のようにしてみました（一例）。関数acceptを走らせるプロセスをアクセプターと呼ぶことにして、フロントのプロセスは、文字列を受け取ったらアクセプターを起動して文字を順にアクセプターに送りつけます。
% -*- coding: utf-8 -*-
-module(accept).
-compile(export_all).start() ->
spawn(fun () -> process_flag(trap_exit, true), main_loop() end).main_loop() ->
receive
stop ->
io:fwrite("byebye.~n"),
exit(normal);
Str when is_list(Str) -> % 文字列はアクセプターで処理する
Pid = spawn_link(?MODULE, accept, [0]), % アクセプターを起動
send_loop(Pid, Str, send); % アクセプターとの通信に入る
% 終われば main に戻ってくる（ご安心を）
_Other -> % ノイズは捨てる
main_loop()
end.send_loop(Pid, [], send) ->
Pid ! 0, % アクセプターに End-Of-String を送る
send_loop(Pid, [], wait); % 待ちに入る
send_loop(Pid, [], wait) ->
receive
{'EXIT', Pid, error} -> % 失敗
io:fwrite("ERROR.~n"),
main_loop(); % 戻る
{'EXIT', Pid, normal} -> % 成功
io:fwrite("ACCEPTED.~n"),
main_loop(); % 戻る
_Other -> % ノイズは捨てる
send_loop(Pid, [], wait)
after 1000 -> % いくら何でも遅すぎるだろうよ
erlang:error(something_wrong)
end;
send_loop(Pid, [Ch|Rest], send) ->
receive
{'EXIT', Pid, error} -> % 失敗
io:fwrite("ERROR.~n"),
main_loop(); % 戻る
_Other -> % ノイズは捨てる
send_loop(Pid, [Ch|Rest], send)
after 0 ->
Pid ! Ch, % アクセプターに1文字送る
send_loop(Pid, Rest, send) % 残りの仕事
end.accept(N) ->
% ...
% ...
end.
アクセプターの終了をフロントのプロセスで監視することによって、文字列が受理されたか否かを判定します。
1> c(accept).
{ok,accept}
2> P = accept:start().<0.37.0>
3> P!"abc".
ACCEPTED.
"abc"
4> P!"aabc".
ACCEPTED.
"aabc"
5> P!"aaabc".
ERROR.
"aaabc"
6> P!"axbc".
ERROR.
"axbc"
7> P!"abbc".
ACCEPTED.
"abbc"
8> P!stop.
byebye.
stop
9>
文字列の受理は、プロセスを使わずに関数だけでも当然できますが、状態遷移機械をプログラムすることは多いので、プロセスとメッセージによる状態遷移の実装方法を知っておいて損はありません。
