ブログ: 複雑な状態遷移機械をうまく表現できるStateChartの実装法.

ブログ: 複雑な状態遷移機械をうまく表現できるStateChartの実装法.

(expanded from Statechart このページは編集しないでください)

(2018/7/29)

プログラムで状態遷移を表現する方法はいろいろあるが、状態変数を用意して状態を表現することが多いだろう。以下のプログラムを実行すると、クリックするたびに状態変数 state の値がトグルする。

state1.js
Copied!
var state;
function setup(){
state = 0;
}
function mousePressed() {
state = (state == 0 ? 1 : 0);
alert(`state => ${state}`);
}

表を使って状態遷移を表現することもできる。 transition[][] のような遷移表を作っておき、 state = transition[state][input] のように現在の状態と入力から次の状態を計算するようにしておけばプログラムは簡単になる。 正確な遷移表を作ることだけ注意すれば良い。

state2.js
Copied!
var state; // 状態変数
const transition = [ // 状態遷移表
[1, 0], // 状態0からの状態遷移
[0, 1] // 状態1からの状態遷移
];
function setup(){
state = 0;
}
function mousePressed() {
input = (Math.random() > 0.5 ? 1 : 0); // ランダムな入力
state = transition[state][input]; // 次の状態を計算
alert(`state => ${state}`);
}
実行

単純な状態遷移の場合はこれで良いのだが、遷移が複雑になって状態変数が増えると面倒なことになる。たとえばマルチタップでひらがなを入力するガラケーの状態遷移は以下のようになるかもしれない。

同じキーを連打すると「あ」⇒「い」⇒「う」のように遷移 (段を示す変数を使う?)
別のキーを押すと「か」「さ」など別の子音に遷移 (行を示す変数を使う?)
濁音キーを押すと「か」や「が」をトグル (濁音かどうかを示す変数を使う?)
小文字キーを押すと「あ」や「ぁ」をトグル (小文字かどうかを示す変数を使う?)

ここでは4個の状態変数が必要になってしまう。4個ぐらい問題ないと思うかもしれないが、「ま行」の「濁音」のような変な状態が出現する可能性を考慮するとプログラムが複雑になるしテストも難しくなる。条件が増えるたびに無闇に状態変数を増やしたりすると状態の数が指数的に増えて収拾がつかなくなってしまう。

上のような仕様は以下のような階層的な状態遷移図を使えばわかりやすく表現できる。左の「あ行」のブロックの中だけ見ると普通の状態遷移図であるが、状態が「あ」でも「ぇ」でも か キーを押せば「か」行の処理に遷移するべきなので、「あ」から「ぉ」までをグループ化してある。こういう階層的な状態遷移図は「Statechart」と呼ばれ、1980年代にDavid Harelにより発明された。

Statechartは複雑な状態遷移をわかりやすく表現できるので便利であるが、このような図表現を状態変数や遷移表を使うプログラムに変換するのは面倒だし間違えやすい。Statechart専用のエディタで作成した遷移図をプログラムに変換するシステムも存在するようだが一般的ではない。上図のような状態遷移図をそのまま読みやすいプログラムに変換する手法があれば嬉しいだろう。
ありがたいことに、特殊なエディタや変換システムを利用せずにStatechartを使うためのテクニックが「Practical Statecharts in C/C++」という本で解説されており、この方法を使うと簡単にStatechartで表現された状態遷移機械プログラムを作成することができる。


ここで提案されている手法は、状態変数を使うかわりに現在の状態を示す関数を使うというものである。たとえば「あ」という状態は あ() という関数で表現し、「い」という状態は い() という関数で表現する。「あ」や「い」という状態の上位階層として「あ行」という状態が存在するので、それは あ行() のような関数で表現する。このように、あらゆる状態を関数として表現するところがミソである。
現在の状態が あ() であるとき あ キーが押されると状態は い() に変化し、再度 あ キーが押されると状態は う() に変化する。ところがこれらのどの状態にあっても か キーが押された場合は状態は か() に移動してほしいので、状態 あ() において あ 以外のキーが入力されたときは自力では処理せず、親状態である あ行() に処理を依頼する。 あ行() で か キーが入力された場合は か() に遷移を行なう。このような処理を以下のようなプログラムで実現できる。

statechart.js
Copied!
var state;
function あ(key){
switch(key){
case undefined: alert("あ"); return;
case 'あ': state = い; return false; // 普通に状態遷移
default: return あ行; // 親状態に処理を依頼
}
}
function い(key){
switch(key){
case undefined: alert("い"); return;
case 'あ': state = う; return false;
default: return あ行;
}
}
function う(key){
switch(key){
case undefined: alert("う"); return;
case 'あ': state = あ; return false; // 本当は え、お... になるのだが省略
default: return あ行;
}
}
function あ行(key){
switch(key){
case undefined: alert("あ行"); return;
case 'か': state = か; return false;
case 'さ': state = さ; return false;
// た、な、... を省略
default: return false;
}
}
function か(key){
switch(key){
case undefined: alert("か"); return;
case 'か': state = き; return false;
default: return か行;
}
}
function き(key){
switch(key){
case undefined: alert("き"); return;
case 'か': state = く; return false;
default: return か行;
}
}
function か行(key){
switch(key){
case undefined: alert("か行"); return;
case 'あ': state = あ; return false;
case 'さ': state = さ; return false;
// た、な、...
default: return false;
}
}
// この調子ですべての状態を関数で記述

function trans(c){ // 状態遷移関数
var newstate;
while(newstate = state(c)){ // 階層的状態遷移の処理
state = newstate;
}
state();
}
function setup(){
// 遷移の例
state = あ;
trans('あ'); // あ を押すと い に遷移
trans('あ'); // あ を押すと う に遷移
trans('か'); // か を押すと か に遷移
}
実行

状態の数だけ関数を用意しなければならないが、階層的な状態遷移構造を普通のプログラムテキストで表現できるし、特殊なツールを必要としないので上手いやり方だといえる。iPhoneのフリック入力はマルチタップもサポートしていたため複雑な状態遷移の記述が必要だったのだが、この技法を利用することによって綺麗にプログラムを書くことができたのであった。

(状態遷移プログラミング一般に関しては講義資料で解説している。)

Web開発で便利に使えるXstateというのがあるらしい

#プログラミング #状態遷移機械 #ブログ #技術情報
2018/7/29

関連ページ

Powered by Helpfeel