今回はD言語で状態遷移表設計をやろうという誰得な話をします。
組み込み系ではごくごく一般的な設計手法ですが、エンタープライズ系ではお目にかかることはあまりないのではないかと思います。
状態遷移について
ときおり、オブジェクトが状態を持ち、状態に依存して振る舞いを変えたくなる時があります。
そんな場合、状態遷移図を使ってその様子を表し、ステートパターンなんかでプログラムコードに落としたりします。
しかし、状態遷移図には欠点があります。
私のような組み込みエンジニアは、この欠点が致命傷になる場合がよくあるのです。
さて、その欠点とは…。
状態遷移図の欠点
たとえば… CDプレーヤーを想定しましょう。
CDプレーヤーは、以下の状態と振る舞いを規定します。
- CDプレーヤーは、最初は「停止中」です。
- 「停止中」の場合、再生ボタンを受け付け、「再生中」になり音楽を再生し始めます。
- 「再生中」の場合、停止ボタンを受け付け、「停止中」になり音楽は停止します。
- 「再生中」の場合、再生ボタンを受け付け、「一時停止中」になり音楽は停止します。
- 「一時停止中」の場合、再生ボタンを受け付け、「再生中」になり音楽は一時停止したところから再度再生を開始します。
これがCDプレーヤーの仕様とします。
読みにくいですか？
それは図にすれば幾分か見やすくなるでしょう。
でも、この図も欠点を持っています。
なんだかわかりますか？
答えは…
- 一時停止中に、停止ボタンを押したらどうなる？
- 停止中に、停止ボタンを押したらどうなる？
これが記載されていない。
記載されていないのに、気づきにくい。
未定義動作なんていうのが許されるのはC/C++だけで十分です。
日本のCDプレーヤーのような民生機器なんかでは、市場的にハングすることが許されない場合が多く、考えてなかったものについてはとりあえず例外で警告出す…などの対処は万に一つも許されません。(万に1つあると、10万個製品が売れた時10件の不具合が出ることに。10人ヒットしたら1人くらいは「大切なお客様のお言葉」をメーカーに伝えるため電話を握り締めることでしょう。この場合、その大切なお客様のお言葉は大抵「なんかよくわからないけど動かなくなった！！」です。開発者は死にます。)
これに対する対処法はただひとつ。
全てのパターンを網羅的に仕様化・実装・テストすること。
そして、得てしてそういうのを状態遷移図に入れ込もうとすると、見やすいとはとても言いづらい図になってしまう。
ちなみにこれが上で言ったCDプレーヤーの仕様を網羅した図。
状態遷移表
はてさて。
たかだか3状態2イベントな状態遷移ですら、この始末。
これが10状態15イベントとかになったら…
考えなければならないのは、32=6から1015=実に150パターン…！
これらを改善するための手法、それが状態遷移表(STM: State Transition Matrix / Software Transactional Memoryじゃないよ！)です。
列ごとに状態、行ごとイベントが記載されています。ある状態の時、あるイベントが来たらが発生したら、どの状態に遷移するか、を表で表現したものです。
ついでに遷移時の振る舞いも記載できます。
各セルの上段が遷移先、下段がイベント発生時の振る舞いになります。
このようにして遷移先と遷移時の振る舞いを記載することによって、網羅的に状態遷移を表現する事ができるのです。
さて、ここまで細かく書いた状態遷移表の場合…。
単純な置換でソースコードに落とせるんじゃない？
って考えた人がいたわけです。
その手のソフトのことをCASEツールなどと呼び、たとえばCATS社のZIPCなどがまさに状態遷移表からC言語のソースコードを吐き出すツールとなっています。
最近ではソフトウェア規模の増大から、手でハードコーディングするようなことはなるべく避け、モデルベース開発を行うことで設計・コーディングの負担や重複を減らすことに注目が集まっています。
状態遷移表からのソースコード出力もそうした背景から出てきたツールといえるでしょう。
しかし私は考えました。
ソースコードを吐き出すのなんて前世代の産物だ…！
それ、D言語ならコンパイル時にできるよ！
と、いうわけで作ったのが
voileというのは私が作ってるスクラップライブラリで、とりあえず汎用化できそうなものを雑多に詰め込んだライブラリです。
私自身使ったことないようなしょうもないモジュールから、今回のSTMやUnique、Handlerみたいな有用なのまでいろいろ入れています。
インストールの仕方は置いておくとして…(ドキュメントとかおいてないので勘と気合でインストールすること)
その使い方や如何に。
ここでは例としてCSVファイルの解析(parse)を状態遷移表で行なってみます。
① CSVファイルで状態遷移表(csvparse.stm.csv)を作成します。
② CSVファイルで置換表(csvparse.map.csv)を作成します。
③ あとはこう！
mixin(parseCsvStm(import("csvparse.stm.csv"), import("csvparse.map.csv")));
auto stm = stmFactory();
プログラム全体としてはこんな感じ。
import voile.stm;
import std.stdio, std.array, std.exception;
pragma(lib, "voile");
void main()
{
auto cell = appender!string();
auto cols = appender!(string[])();
auto rows = appender!(string[][])();
char c;
enum csvdata = import("csvparse.stm.csv");
enum mapdata = import("csvparse.map.csv");
enum stmstr = parseCsvStm(csvdata, mapdata);
mixin(stmstr);
auto stm = stmFactory();
foreach (char x; csvdata)
{
c = x;
switch (c)
{
case '\r': stm.put(Event.eolCR); break;
case '\n': stm.put(Event.eolLF); break;
case '"': stm.put(Event.quote); break;
case ',': stm.put(Event.comma); break;
default: stm.put(Event.other); break;
}
}
writefln("%(%(%-s,%)\n%)", rows.data);
}
応用(状態遷移表 with ゲームプログラミング)
他の状態遷移表の実施例として、簡単に思いつきそうなのがゲームプログラミングですね。
ゲームの内部構造は状態だらけなので、簡単に適用できます。
例えば、
- ゲーム画面中"C"キー押下でメニューを表示する
- メニュー表示中上下キーで各メニュー項目にカーソルを移動する
- メニュー表示中「セーブ」のメニュー項目で"Z"キー押下でセーブ画面が出る
- メニュー表示中「終了」のメニュー項目で"Z"キー押下でゲーム終了
- メニュー表示中「戻る」のメニュー項目で"Z"キー押下でゲーム画面に戻る
- セーブ画面表示中で"ESC"キー押下でメニュー画面に戻る
- メニュー表示中"ESC"キー押下でゲーム画面に戻る
- ゲーム画面中"ESC"キー押下でゲーム終了
という仕様でゲームを作ると…
これが状態遷移図になります。
以下に3パターンの実装方法で実装したサンプルプログラムを示します。
if文で無理やり作った場合
無理やりif文で実装するとこうなります。状態数もさほど多くありませんし、ガチガチのハードコーディングでもこの程度なら案外なんとでもなります。
今回はゲームプログラミングと言いながらも、表示系とか入力系とか音声系もろもろをガチで作る話ではないので、DFLとかWinAPIとかつかったり、画像を固定したりしてごまかしています。以下のサンプルコードでは状態遷移に関わる箇所のみピックアップしています。
サンプルプログラム2 の if_direct.d 参照。
if (state == State.game)
{
if (e.keyCode == Keys.C)
{
idx = 1;
_pBox.image = _images[idx];
_sounds[0].play();
state = State.menu;
}
else if (e.keyCode == Keys.ESCAPE)
{
_sounds[3].playSync();
close();
}
}
else if (state == State.menu)
{
if (e.keyCode == Keys.Z && idx == 5)
{
idx = _images.length-1;
_pBox.image = _images[idx];
_sounds[2].play();
state = State.menu_save;
}
else if (e.keyCode == Keys.Z && idx == 7)
{
_sounds[3].playSync();
close();
}
else if (e.keyCode == Keys.Z && idx == 8)
{
idx = 0;
_pBox.image = _images[idx];
_sounds[3].play();
state = State.game;
}
else if (e.keyCode == Keys.UP)
{
if (idx > 1)
--idx;
_pBox.image = _images[idx];
_sounds[1].play();
}
else if (e.keyCode == Keys.DOWN)
{
if (idx < _images.length-2)
++idx;
_pBox.image = _images[idx];
_sounds[1].play();
}
else if (e.keyCode == Keys.ESCAPE)
{
idx = 0;
_pBox.image = _images[idx];
_sounds[3].play();
state = State.game;
}
}
else if (state == State.menu_save)
{
if (e.keyCode == Keys.ESCAPE)
{
idx = 1;
_pBox.image = _images[idx];
_sounds[3].play();
state = State.menu;
}
}
これだと状態が増えたり、条件が増えたり、仕様変更があったりするとすぐに破綻することは想像に難くないと思います。
Stateパターンで作った場合
Stateパターンとかつかってやると下記のようになります。これで少しは再利用性が上がり、仕様変更にもそれなりに強くなるでしょう。
サンプルプログラム2 の state_pattern.d 参照。
class GameState: State
{
void onMenu()
{
idx = 1;
_pBox.image = _images[idx];
_sounds[0].play();
_state = _states[1];
}
void onExitGame()
{
_sounds[3].playSync();
close();
}
void opCall(Keys k)
{
if (k == Keys.C)
onMenu();
if (k == Keys.ESCAPE)
onExitGame();
}
}
class MenuState: State
{
void onUp()
{
if (idx > 1)
--idx;
_pBox.image = _images[idx];
_sounds[1].play();
}
void onDown()
{
if (idx < _images.length-2)
++idx;
_pBox.image = _images[idx];
_sounds[1].play();
}
void onReturnGame()
{
idx = 0;
_pBox.image = _images[idx];
_sounds[3].play();
_state = _states[0];
}
void onSaveEnter()
{
idx = _images.length-1;
_pBox.image = _images[idx];
_sounds[2].play();
_state = _states[2];
}
void onExitGame()
{
_sounds[3].playSync();
close();
}
void opCall(Keys k)
{
if (k == Keys.UP)
onUp();
else if (k == Keys.DOWN)
onDown();
else if (k == Keys.ESCAPE)
onReturnGame();
else if (k == Keys.Z && idx == 5)
onSaveEnter();
else if (k == Keys.Z && idx == 7)
onExitGame();
else if (k == Keys.Z && idx == 8)
onReturnGame();
}
}
class MenuSaveState: State
{
void onReturnMenu()
{
idx = 5;
_pBox.image = _images[idx];
_sounds[3].play();
_state = _states[1];
}
void opCall(Keys k)
{
if (k == Keys.ESCAPE)
onReturnMenu();
}
}
状態遷移表を使った場合
これらと同等のことを状態遷移表でやりますが、今回、状態が入れ子になっていることがわかります。(ゲーム画面とメニュー画面の大枠の状態2つと、メニュー画面の中にいくつもの状態があります。セーブ画面にしろ、今後の拡張性から言えば入れ子になることは想像できます。)
入れ子の状態遷移の管理を行うのに適切なのが拡張階層化状態遷移表(EHSTM: Extended Hierarchy State Transition Matrix)と呼ばれる状態遷移表なのですが…
voile.stmでは、拡張階層化状態遷移表をサポートしていません。
なぜなら、複雑だから。(子階層の初期状態とか子階層から親階層の遷移を制御するとか親の遷移時の子の遷移とかいろいろいろいろ。)
複雑なのは、設計が難しく、デバッグも大変。(ということにしておこう。決して実装が面倒になったとかじゃないですよ！多分！)
しかしながら、D言語では、nested classなどなど、簡単に入れ子構造を取り入れることのできる文法が提供されていますし、工夫次第でただのSTMだけでも十分対応可能です。
ここでは先ほどのステートパターンと状態遷移表の組み合わせを使うと、いい塩梅に拡張階層化状態遷移表と似たような設計をすることができます。
サンプルプログラム2 の stm.d 参照。
/// ゲーム
class GameState: StateBase
{
void enable() { _pBox.image = _images[0]; }
void opCall(Keys k) { /* stub */ }
}
/// メニュー
class MenuState: StateBase
{
/// メニュ_セーブ
class MenuSaveState: StateBase
{
mixin(parseCsvStm(import("menu_save.stm.csv"), import("menu_save.map.csv")));
Stm!(State, Event) _stm;
this() { _stm = stmFactory(); }
void enable() { _stm.put(Event.enable); }
void opCall(Keys k)
{
switch (k)
{
case Keys.UP: _stm.put(Event.up); break;
case Keys.DOWN: _stm.put(Event.down); break;
case Keys.ESCAPE: _stm.put(Event.cancel); break;
case Keys.Z: _stm.put(Event.confirm); break;
default: break;
}
}
}
MenuSaveState _menuSave;
mixin(parseCsvStm(import("menu.stm.csv"), import("menu.map.csv")));
Stm!(State, Event) _stm;
this()
{
_menuSave = new MenuSaveState;
_stm = stmFactory();
}
void enable() { _stm.put(Event.enable); }
void opCall(Keys k)
{
switch (k)
{
case Keys.UP: _stm.put(Event.up); break;
case Keys.DOWN: _stm.put(Event.down); break;
case Keys.ESCAPE: _stm.put(Event.cancel); break;
case Keys.Z: _stm.put(Event.confirm); break;
default: break;
}
}
}
mixin(parseCsvStm(import("main.stm.csv"), import("main.map.csv")));
Stm!(State, Event) _stm;
まとめ
状態遷移表設計をD言語で利用する方法についてお話しました。
若干主観的意見も入りますが、利点としては、
- 状態遷移表は状態とイベントを網羅的に見ることに長ける
- 設計したものがそのままコンパイル可能
- 設計が視覚化される
- 状態の追加が容易(列を追加して各イベントに対応するだけ)
- イベントの追加が容易(行を追加して各状態での振る舞いに対応するだけ)
- 状態と振る舞いの規則性が浮き彫りになる
- C1カバレッジが簡単に可視化できる(全部のセル通ればOK)
といったものが挙げられます。
その他、D言語で使うと重宝しそうな場面としては、
- 非同期系のイベント処理(std.concurrency等)
- 通信処理のハンドシェイク等フロー制御
- GUIのイベント処理(ゲームプログラミングのパターンと同様ですね)
などに特に有用なようです。今回例として挙げましたが、構文解析に使うケースもあるようです。(構文解析用のライブラリ使うのと比べたら、サクッと作れる、とは口が裂けても言えないと思いますが)
なお、勘違いしてはいけないのですが、状態遷移表だから簡単になるというわけではありません。
複雑なものは何したって複雑だし、状態遷移表設計にも独特なノウハウがありますので、割りと万能なツールではあっても、あらゆる場面で最良というわけでは無いことを念頭に置きつつご利用くださいませ。
(実際私もゲームのサンプルプログラム書くのに、if文やステートパターンに比べて、状態遷移表を使うのは5倍くらい時間かけました)
さて、次は23日目 @iduru_kazumi です。