株式会社エス・スリー・フォー

State Map Compiler

状態遷移表

FSM(Finite State Machine:有限状態機械)は、アプリケーションの分析･設計において重要なパートのひとつです。非常に多くのアプリケーションが、その動作をFSMによって記述することができます。

FSMは”State Map:状態表”あるいは”State Transition Table:状態遷移表”と呼ばれる表の形で表現されます。

“(門番のいる)ゲート”を例に、FSMを作ってみましょう。以下のようなState Mapを用意しました。

現在の状態	イベント	次の状態	アクション
Locked	Coin	Unlocked	Unlock
Locked	Pass	Locked	Alarm
Unlocked	Coin	Unlocked	ThankYou
Unlocked	Pass	Locked	Lock

このState Mapはゲートの制御モデルを表現しています。ゲートは2つの状態Locked(閉じている)とUnlocked(開いている)をもち、2つのイベントCoinとPassを受け付けます。

Coinイベント: 門番が入場料を受け取った
Passイベント: 誰かがゲートを通過した

また、ゲートには4つのアクションが定義されています。

Unlock: ゲートを開ける
Lock: ゲートを閉じる
Alarm: 警報を鳴らす
ThankYou: 余分なお金をもらったことに礼を言う

このState Mapの読み方は以下のとおりです:

ゲートがLocked状態のとき:
- Coinイベントが発生したら、Unlocked状態に遷移してUnlockアクションを起こす。
- Passイベントが発生したら、閉じているゲートを無理矢理誰かが通過したことに対しAlarmアクションを起こす
ゲートがUnlocked状態のとき:
- Passイベントが発生したら、Locked状態に戻してLockアクションを起こす
- Coinイベントが発生したら、余分なお金を頂いた事に礼を言う(ThankYouアクションを起こす)。

さて、このState Mapに表された動作を行なうプログラムをどのように書きましょうか。

いちばん単純なのは二重のswitch文です。つまり:

  enum { Locked, Unlocked } state;
  enum { Coin, Pass }       event;

  state s = Locked; // 初期状態
  event e;

  while ( true ) { // 無限ループ
    e = 発生したイベント;
    switch ( s ) {
    case Locked :
      switch ( e ) {
      case Coin :
        s = Unlocked;
        Unlock();
        break;
      case Pass :
        s = Locked;
        Alarm();
        break;
      }
      break;
    case Unocked :
      switch ( e ) {
      case Coin :
        s = Unlocked;
        ThankYou();
        break;
      case Pass :
        s = Locked;
        Lock();
        break;
      }
      break;
    }
  }

実に素直なコードです。この例では状態とイベントが2つづつだからまだマシですが、これが状態10コ/イベント10コに増えたとしたら500 行を越える長大なswitch文になってしまいます。書くのも大変読むのも大変デバッグするのはもっと大変、とてもやってられません。

二次元配列を使えばよりエレガントになります:

  enum { Locked, Unlocked } state;
  enum { Coin, Pass }       event;

  state Locked_Coin() {
    Unlock();
    return Unlocked;
  }

  state Locked_Pass() {
    Alarm();
    return Locked;
  }

  state Unlocked_Coin() {
    ThankYou();
    return Unlocked;
  }

  state Unlocked_Pass() {
    Lock();
    return Locked;
  }

  ...

  state s = Locked; // 初期状態
  event e;

  typedef state (*transition)();
  transition table[2][2] = {
    Locked_Coin,   Locked_Pass,
    Unlocked_Coun, Unlocked_Pass
  };

  while ( true ) {
    e = 発生したイベント;
    s = (*table[s][e])();
  }

状態とイベントの組それぞれに対し関数を用意し、その中でアクションの実行と次の状態の設定を行ないます。二重のswitch文よりはずっと奇麗ですが、状態数xイベント数と同数の関数定義が必要です。もっとエレガントなコードは書けないものでしょうか…

State Map Compiler

僕の愛用するクラスライブラリのひとつに Rogue Wave社のTools.h++ Professionalというのがあります。このクラスライブラリはFTP/HTTP/SMTP/POP3のクライアントをいとも簡単に作れるクラス群を提供しています。readmeドキュメントの中に、｢プロトコルの実装にはSMC(State Map Compiler)を使いました。SMCはhttp://www.oma.com/Offerings/catalog.htmlから無料で入手できます。｣とありました。

SMCによるFSMの実装手順を説明しましょう。まず、状態遷移表に現われるアクションを定義するクラス(“Context:コンテキスト”と呼んでいます)を作ります。

// GateContext.h

#ifndef __GATECONTEXT_H__
#define __GATECONTEXT_H__

class GateContext {
public:
  void Lock();
  void Unlock();
  void Alarm();
  void ThankYou();
  void FSMError(const char*, const char*);
};

#endif

// GateContext.cpp

#include "GateContext.h"
#include <iostream>

using namespace std;

void GateContext::Lock() { cout << "ゲートを閉じます" << endl; }
void GateContext::Unlock() { cout << "ゲートを開けます" << endl; }
void GateContext::Alarm() { cout << "タダで入っちゃいけませんよ!" << endl; }
void GateContext::ThankYou() { cout << "これはどうも...有り難く頂戴します" << endl; }

void GateContext::FSMError(const char* event, const char* state) {
  cout << state << " 状態で "
       << event << " が発生するはずないのに!"
       << endl;
}

次に、状態遷移表を表現するStateMapファイルを作ります:

// GateSFM.sm
fsmname GateFSM
context GateContext
header  GateContext.h
initial Locked

{
  Locked {
    Coin Unlocked Unlock
    Pass Locked   Alarm
  }
  Unlocked {
    Coin Unlocked ThankYou
    Pass Locked   Lock
  }
}

このファイルGateFSM.smをSMCに食わせます:

 smc < GateFSM.sm

するとSMCはgateFSM.hとgateFSM.ccを出力します。簡単なテストドライバをこさえましょう:

// gate.cpp
#include "gateFSM.h"
#include 

using namespace std;

int main() {
  GateFSM fsm;
  for ( bool cont = true;  cont; ) {
    char input[32];
    cout << "現在の状態は : " << fsm.GetState().StateName() << endl;
    cout << "Coin or Pass (c/p) ? " << flush;
    cin >> input;
    switch ( *input ) {
      case 'c' : fsm.Coin(); break;
      case 'p' : fsm.Pass(); break;
      default  : cont = false;
    }
  }
  return 0;
}

これで完了です。gate.cpp, gateFSM.cc, GateContext.cppをコンパイル/リンクすれば実行形式ができあがります。実行結果を以下に示します。

現在の状態は : Locked
Coin or Pass (c/p) ? c
ゲートを開けます
現在の状態は : Unlocked
Coin or Pass (c/p) ? p
ゲートを閉じます
現在の状態は : Locked
Coin or Pass (c/p) ? p
タダで入っちゃいけませんよ!
現在の状態は : Locked
Coin or Pass (c/p) ? c
ゲートを開けます
現在の状態は : Unlocked
Coin or Pass (c/p) ? c
これはどうも...有り難く頂戴します
現在の状態は : Unlocked
Coin or Pass (c/p) ? p
ゲートを閉じます
現在の状態は : Locked
Coin or Pass (c/p) ? /

GateFSMは受理できるイベントと同名のメソッドを持っており、発生したイベントに対応するメソッドのコールを繰り返すだけです。アクションを実装し、状態遷移表を書くだけでFSMによるアプリケーションができちゃうです。

FSMのからくり

以下に示した、SMCが吐いたコードを追いかけてからくりをあばいてみましょう。

// gateFSM.h

#ifndef _H_GateFSM
#define _H_GateFSM
#include <stddef.h>
#include "GateContext.h"

class GateFSM;

class GateFSMState {
public:
  virtual const char* StateName() const = 0;
  virtual void Pass(GateFSM& s);
  virtual void Coin(GateFSM& s);
};

class GateFSMUnlockedState : public GateFSMState {
public:
  virtual const char* StateName() const
  {return("Unlocked");};
  virtual void Pass(GateFSM&);
  virtual void Coin(GateFSM&);
};

class GateFSMLockedState : public GateFSMState {
public:
  virtual const char* StateName() const
  {return("Locked");};
  virtual void Pass(GateFSM&);
  virtual void Coin(GateFSM&);
};

class GateFSM : public GateContext {
  public:
  static GateFSMUnlockedState UnlockedState;
  static GateFSMLockedState LockedState;
  GateFSM();// default constructor
  void Pass() {itsState->Pass(*this);}
  void Coin() {itsState->Coin(*this);}
  void SetState(GateFSMState& theState) {itsState=&theState;}
  GateFSMState& GetState() const {return *itsState;};
  private:
    GateFSMState* itsState;
};

#endif

#include "gateFSM.h"

static char _versID[] = "No Version.";

GateFSMUnlockedState GateFSM::UnlockedState;
GateFSMLockedState GateFSM::LockedState;

void GateFSMState::Pass(GateFSM& s)
  {s.FSMError("Pass", s.GetState().StateName());}

void GateFSMState::Coin(GateFSM& s)
  {s.FSMError("Coin", s.GetState().StateName());}

void GateFSMUnlockedState::Pass(GateFSM& s) {
  s.SetState(GateFSM::LockedState);
  s.Lock();
}

void GateFSMUnlockedState::Coin(GateFSM& s) {
  s.SetState(GateFSM::UnlockedState);
  s.ThankYou();
}

void GateFSMLockedState::Pass(GateFSM& s) {
  s.SetState(GateFSM::LockedState);
  s.Alarm();
}

void GateFSMLockedState::Coin(GateFSM& s) {
  s.SetState(GateFSM::UnlockedState);
  s.Unlock();
}

GateFSM::GateFSM() : itsState(&LockedState) {}

GateFSMは全アクションが定義されたコンテキストGateContextから導出されています。このことにより、GateFSMは必要とするアクションをすべて手に入れた(コールできる)ことになります。privateメンバitsStateの型GateFSMStateは仮想関数 Coin()とPass()を持っていて、GateFSMのメソッドCoin()/Pass()はそのままitsStateの同名のメソッドCoin() /Pass()をコールします。

さらにGateFSMは、定義されている状態に対応する2つのクラスGateFSMLockedState,GateFSMUnlockedStateをstaticメンバに持ち、そのいずれもGateFSMStateの派生クラスです。

現在の状態がLockedである、すなわちitsState == &GateFSM::GateFSMLockedStateであるGateFSMのインスタンスに対しイベントCoinを発生させる(GateFSM::Coin()をコールする)と、

 void GateFSM::Coin() {
   itsState->Coin(*this);
 }

と定義されているので、GetFSMLockedState::Coin()がコールされます。GetFSMLockedState::Coin()にはLocked状態でCoinイベントが発生したときの処理が定義されています。

void GateFSMLockedState::Coin(GateFSM& s) {
s.SetState(GateFSM::UnlockedState);
s.Unlock();
}

状態遷移表GateFSM.smに記述したとおり、Unlocked状態に遷移した後にUnlockアクションをコールしています。他の状態/イベントの組み合わせに対しても同様です。

SMCはこれらのクラスおよび各メソッドを状態遷移表から生成してくれるわけです。

SMCの文法

ではもう少し大きなFSMを作りながら、SMCの文法を説明します。C++のソースコードからコメントを除去するアプリケーション”stripper”を作りましょう。

C++でのコメントは、

“//”から始まり、改行コードまで。
“/*”から始まり、”*/”まで

です。ソースコードから1文字づつ読み出し、FSMに食わせることでコメントを除去します。

この状態遷移図と等価な状態遷移表を以下に示します。

現在の状態	イベント	次の状態	アクション
outside	Slash	startingSlash
	Star	outside	PutChar
	EOL	outside	PutChar
	Other	outside	PutChar
]startigSlash	Slash	secondSlash
	Star	starAfterSlash
	EOL	outside	PutSlash PutChar
	Other	outside	PutSlash PutChar
secondSlash	Slash	secondSlash
	Star	secondSlash
	EOL	outside	PutChar
	Other	secondSlash
starAfterSlash	Slash	starAfterSlash
	Star	startingStar
	EOL	starAfterSlash		*
	Other	starAfterSlash		*
startingStar	Slash	outside
	Star	starAfterSlash
	EOL	starAfterSlash		*
	Other	starAfterSlash		*

これを基にSMCに食わすスクリプトファイルStripFSM.smを作ります。

FSMName StripFSM
Context StripperContext
Header  stContext.h
Initial outside
Version stripFSM.sm version 1.0

{
  outside {
    Slash    startingSlash   {}
    Star     outside         PutChar
    EOL      outside         PutChar
    Other    outside         PutChar
  }

  startingSlash {
    Slash    secondSlash     {}
    Star     starAfterSlash  {}
    EOL      outside         { PutSlash PutChar }
    Other    outside         { PutSlash PutChar }
  }

  secondSlash {
    EOL      outside         PutChar
    Other    secondSlash     {}
    Star     secondSlash     {}
    Slash    secondSlash     {}
  }

  (inStarComment) {
    Other    starAfterSlash  {}
    EOL      starAfterSlash  {}
  }

  starAfterSlash : inStarComment {
    Star     startingStar    {}
    Slash    starAfterSlash  {}
  }

  startingStar : inStarComment {
    Slash    outside         {}
    Star     startingStar    {}
  }
}

スクリプトはヘッダ部と状態遷移部に分かれていて、

ヘッダ部
{
  状態遷移部
}

の形式で記述します。

ヘッダ部
- FSMName FSM名
  
  生成するFSMの名前を指定します。ここで与えた名前がクラス名となり、最初の1文字を小文字に置き換え、拡張子”.cc”,”.h”を付けたコードが出力されます。
- Context コンテキスト名
  アクションを定義したコンテキストを指定します。FSMはこのコンテキストから導出されます。
- Header ヘッダ名
  FSMヘッダで#includeするファイル(通常コンテキストが宣言されたヘッダ)を指定します。
- Initial 初期状態
  FSMのコンストラクタで、ここに指定した初期状態をセットします。これを指定しなかったときは、SetStateメソッドで明示的に初期状態を設定しなければなりません。
- Version バージョン
  任意の文字列をバージョンIDとして指定できます。
状態遷移部
状態遷移部は、
```
状態 イベント 次の状態 アクション
```
を並べたものです。ひとつの状態に対しイベント/次の状態/アクションをまとめて記述する、
```
状態 {
  イベント1 次の状態1 アクション1
  イベント2 次の状態2 アクション2
  ...
}
```
の書式が許されています。

状態の遷移のみで、実行すべきアクションがないときは、
```
状態 イベント 次の状態 {}
```
としてください。また、複数のアクションを実行したいときは、
```
状態 イベント 次の状態
 { アクション1 アクション2 }
```
のように{}で囲んでください。

また、いくつかの状態で、イベント/次の状態/アクションが完全に一致するとき、それらを一つにまとめることができます。たとえば上記の状態遷移表での*の付けられた行は一致していますから、共通の状態遷移を()で囲み、
```
(inStarComment) {
  Other    starAfterSlash  {}
  EOL      starAfterSlash  {}
}
```
そしてそれを継承するような形式でそれぞれの差分を記述することができます。
```
starAfterSlash : inStarComment {
  Star     startingStar    {}
  Slash    starAfterSlash  {}
}

startingStar : inStarComment {
  Slash    outside         {}
  Star     startingStar    {}
}
```

コンテキストおよびメインルーチンを以下に示します。

// stContext.h

#ifndef _H_stripperContext
#define _H_stripperContext

#include <iostream.h>

class StripperContext {
private:
  char itsChar;
  istream *itsIStream;
  ostream *itsOStream;
public:
  StripperContext() { }

  void SetStreams(istream& i, ostream& o) {
    itsIStream = &i;
    itsOStream = &o;
  }

  void FSMError(const char* t, const char* s) {
      cerr << "Transition error: " << t
           << " in state " << s << endl;
  }

  int ReadChar() {
    int c;
    c = itsIStream->get();
    itsChar = c;
    return c;
  }

  void PutChar() { *itsOStream << itsChar; }
  void PutSlash() { *itsOStream << '/'; }
};
#endif

// stripper.cpp
#include <iostream.h>
#include <stdlib.h>
#include "stripFSM.h"

void main() {
  StripFSM myStripper;
  myStripper.SetStreams(cin,cout);

  while ( cin )
    switch( myStripper.ReadChar() ) {
      case EOF : exit(0);            break;
      case '/' : myStripper.Slash(); break;
      case '*' : myStripper.Star();  break;
      case '\n': myStripper.EOL();   break;
      default  : myStripper.Other(); break;
    }
}

επιστημη 2006-03-30