3. 状態遷移プログラミング

本日の話題

「状態遷移機械」とプログラミング

状態とは?

現在の状況を示す値

例

現在位置

何をしているか

いくら持ってるか

状態遷移機械

イベントによって状態が変わる

論理回路、プログラム、スイッチなどなんでも

「オートマトン」

ステートパタン

「パターンランゲージ」のパタンのひとつ

クラスで状態遷移を扱う

Rubyの状態遷移パタン

状態遷移の例

ゲーム

電灯のスイッチ

プログラム

将棋

駒の位置 = 状態

https://gyazo.com/f166875cb4a96aabcd6687a0dc8558cf

状態遷移指向プログラミング

複雑なユーザインタフェース

通信プロトコル

パターンマッチング

「エスケープシーケンス」

プログラム中のコメント処理

ローマ字かな変換

パズル

ローマ字かな変換

http://gyazo.com/caaf304022fdd558037e55e20bb83b4a.png

エスケープシーケンス

特殊な文字列でカーソルを動かす

「VT100」などの端末で利用されている

Terminal.app

xterm

VT100

http://gyazo.com/ab7ab81befe7f5a4a3a9e2fef1207760.png

画面消去

code:c

main(){

printf("\x1b[2J");

printf("\x1b[0;0f");

}

「SL」コマンド

「curses」ライブラリでSLの動きを表現

http://gyazo.com/b79401fc6d7925e603d3450db23d7346.png

人間の状態遷移

https://gyazo.com/45b640ee9804688b5ff4e9947394a108

電灯スイッチの状態遷移

http://gyazo.com/f8b9cf57199c5ed2501770dce007805c.png

ヒステリシスつき状態遷移

http://gyazo.com/57efa56efe41ff54ff6c008e0ebbab70.png

TCP/IPの状態遷移

https://gyazo.com/f5f8de9d6cdf2f8366d505397e971e30

パズルの状態遷移

http://gyazo.com/e91195d80701b5541bc71d9c147f3f05.png

https://www.youtube.com/watch?v=xjZ1bbAwiV0

Cのコメントを検出する状態遷移機械

Cのソースコードから /* ... */ を削除

http://gyazo.com/c0d7354659a4eaa51af15edfa5c542b7.png

日本語入力システムの状態遷移

http://gyazo.com/58b6691a0c3dac9880fcecac03c1e509.png

「Slime」の状態遷移

http://gyazo.com/05d1826ac1137cdb88d564ca8d3c6e73.png

デモ: 日本語IME「Slime」

https://www.youtube.com/watch?v=Ldyl5UbbSA8

すべてのコンピュータは状態遷移機械

クロックで状態が変換

プログラム実行 = 状態遷移

CPU = 複雑な状態遷移機械

組合せ論理回路

状態は存在しない

PLA (Programmable Logic Array) の例

http://gyazo.com/41bf1869e379af7498d83dd3ba2b4abe.png

順序回路

クロック毎に状態が変わる

現在の状態が次の状態に影響する

http://gyazo.com/4018d6838089c0d3a10238efd8526f9a.png

非決定性有限オートマトンと決定性有限オートマトン

オートマトン (Wikipedia)

決定性有限オートマトン (DFA)

単純

実装が簡単

非決定性有限オートマトン (Non-Deterministic Finite Automaton: NDFA)

イベントによって複数の状態に遷移可能

正規表現とNDFA

正規表現

(abc|ade) abc または ade

ab*c a + 0回以上のb + c

正規表現はNDFAに変換可能

(SUB)*SECTION section, subsection, subsubsection, ...

NDFAをDFAに変換

あらゆるNDFAはDFAに変換可能

状態の数は増える

変換の例

(SUB)*SECTION

SECTION, SUBSECTION, SUBSUBSECTION, ... にマッチする

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

変換

http://gyazo.com/d9e5779fe46637b3fedf7783e0e2d1d3.png

生成されたDFA

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

生成されたDFA

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

もとのNDFA

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

Unixのegrepコマンド

正規表現からNFAを作成

NFAからDFAを作成

DFAから状態遷移表を作成

デモ: egrep

code:egrep.sh

% egrep '(sub)*section'

デモ: egrep

code:poker.rb

suits = 'S', 'D', 'H', 'C' # ♠ ♦ ♥ ♣

numbers = 'A', '2', '3', '4', '5', '6', '7', '8', '9', 'X', 'J', 'Q', 'K'

(0..51).to_a.combination(5) { |a|

puts a.collect { |i|

suitsi%4 + numbersi/4

}.join('')

}

code:find.sh

SAS2S3H4S5

SAS2S3H4D5

SAS2S3H4H5

SAS2S3H4C5

...

DFAのプログラミング方法

プログラムの実行位置を状態として利用

状態変数を利用

状態遷移表を利用

こういう状態遷移をどうプログラムするか?

http://gyazo.com/05d1826ac1137cdb88d564ca8d3c6e73.png

フローチャート

http://gyazo.com/ba6a0d78000d76428b935d3a1d63c4af.png

C言語のコメント認識

/* ... */

http://gyazo.com/e3114c38659d39bd4598116103724ee6.png

プログラムの実行位置で状態を表現

今動いているところが状態になる

code:state.txt

仕事1を実行() # 状態1になる

仕事2を実行() # 状態2になる

仕事3を実行() # 状態3になる

....

comment1.c

code:comment1.c

#include <stdio.h>

main()

{　

int c;

while(1){

c = get_c();

while(c == '/'){

c = get_c();

if(c == '*'){

printf("/*");

int done = 0;

while(! done){

c = get_c();

printf("%c",c);

while(c == '*'){

c = get_c();

printf("%c",c);

if(c == '/'){

done = 1;

c = get_c();

break;

}

結果

プログラムの実行位置で状態を表現する方法

状態遷移が単純なときは大丈夫

複雑な状態遷移のときは大変

状態変数を利用する方法

変数の値で状態を表現する

条件文で状態を判定

比較的単純な状態遷移には有効

単純なフラグも状態変数

状態変数を沢山使うと大変になる

あらゆる組合せをチェックすることが不可能

comment2.c

code:comment2.c

typedef enum {

S1, S2, C1, C2

} State;

State state = S1;

trans(int c)

{

switch(state){

case S1:

if(c == '/') state = S2;

break;

case S2:

if(c == '/') state = S2;

else if(c == '*'){

printf("/*");

state = C1;

}

else state = S1;

break;

case C1:

printf("%c",c);

if(c == '*') state = C2;

break;

case C2:

printf("%c",c);

if(c == '*') state = C2;

else if(c == '/') state = S1;

else state = C1;

break;

}

main()

{

char buf1000;

char *s;

while(fgets(buf,1000,stdin)){

for(s=buf;*s;s++){

trans(*s);

}

状態遷移表で状態遷移プログラミング

状態とイベントを整数値で

自動/手動で表現を作成

状態遷移表

http://gyazo.com/adb22100f07d3c58e4d00192368589d9.png

comment3.c

code:comment3.c

enum {

S1, S2, C1, C2

};

int trans40x100;

int state = S1;

void init()

{

int i;

for(i=0;i<0x100;i++){

transS1i = S1;

transS2i = S1;

transC1i = C1;

transC2i = C1;

}　

transS1'/' = S2;

transS2'/' = S2;

transS2'*' = C1;

transC1'*' = C2;

transC2'*' = C2;

transC2'/' = S1;

state = S1;

}

main()

{

unsigned char buf1000;

unsigned char *s;

init();

while(fgets(buf,1000,stdin)){

for(s=buf;*s;s++){

int oldstate = state;

state = transstate*s;

if(oldstate == S2 && state == C1) printf("/*");

if(oldstate == C1 || oldstate == C2) printf("%c",*s);

}

状態遷移表の自動生成

正規表現などを表やプログラムに変換

lex

flex

Lex

字句解析プログラムを生成

Eric Schmidt が作った

以前のGoogle CEO

Lexの表記例

code:lexsample.l

%option noyywrap

%option array

int line=1;

%state COMMENT

COMIN \/\*

COMOUT \*\/

<INITIAL>^#.*$ {line++;}

<INITIAL>\"^\"*\" ;

<INITIAL>{COMIN} {BEGIN COMMENT;}

<COMMENT>. { printf("%s",yytext);}

<COMMENT>"\n" {line++;printf("%s",yytext);}

<COMMENT>{COMOUT} {BEGIN INITIAL;}

<INITIAL>. ;

<INITIAL>"\n" {line++;}

int main(void){

yylex();

printf("%d lines read.\n",line);

return(0);

}

Lex使用例

% lex lexsample.l

% cc -ll lex.yy.c

% ./a.out

状態遷移図の拡張

Petri net

StateChart

Petri net

トークン、棒(brace)、矢印

複数のトークンが準備できたとき次に移動可能

トークンは並列動作

http://gyazo.com/ae0ec7c3b9aae443e9c5ca813f095297.png

自動販売機

http://gyazo.com/ace3c9e593434fc2aa53e71cf7a37458.png

StateChart

階層的状態遷移図

複数の状態をひとまとめにできる

単純な状態遷移図に展開可能

http://gyazo.com/65ff0aa39a149e6b44605730b0b5e2e3.png

CDプレーヤのStateChart記述

http://gyazo.com/4d631d6d3d371c03dc5080f0f7a3a699.png

CDプレーヤのStateChart記述

http://gyazo.com/77718e8f3a6b40d9df9e98bef2cbed0c.png

ケータイの日本語入力システムの状態遷移

http://gyazo.com/58b6691a0c3dac9880fcecac03c1e509.png

StateChartの実装

特殊ツールを使う

特殊ツールなしにStateChartを使う

状態を関数で表現

自分で取り扱えないイベントは親に渡す

http://hondana.org/%E5%A2%97%E4%BA%95/1578201101 http://gyazo.com/e9a9a3673399c33937c1ebd8e3b68f8f.png

JavaScriptで実装したCDプレーヤの状態遷移

code:statechart.js

funcftion state_play(c){

switch(c){

case undefined: print("this is state_play"); return;

case 'stop_pressed': state = state_stopped; return false;

case 'pause_pressed': state = state_paused; return false;

default: return state_normal;

}

function state_paused(c){

switch(c){

case undefined: print("this is state_paused"); return;

case 'stop_pressed': state = state_stopped; return false;

case 'play_pressed': state = state_play; return false;

default: return state_normal;

}

function state_stopped(c){

switch(c){

case undefined: print("this is state_stopped"); return;

case 'play_pressed': state = state_play; return false;

default: return state_normal;

}

function state_normal(c){

switch(c){

case undefined: print("this is state_normal"); state_stopped();

case 'ff_pressed': state = state_forward; return false;

default: return false;

}

function state_forward(c){

switch(c){

case undefined: print("this is state_forward"); return;

case 'ff_released': state = state_play;return false;

default: return false;

}

function trans(c){

while(newstate = state(c)){

state = newstate;

}

state();

}

state = state_normal;

trans('play_pressed');

trans('ff_pressed');

trans('ff_released');

trans('stop_pressed');

trans('ff_pressed');

trans('ff_released');

どの方法を使えば良いか?

複雑なものはStateChart

状態変数も普通に便利

文書化は大事

e.g. 文芸的プログラミング

課題

簡単な状態遷移プログラムを書く

文芸的プログラミングの方法でScrapboxで書く

例

Cのコメント抽出

http://gyazo.com/c0d7354659a4eaa51af15edfa5c542b7.png

3の倍数を検出する