3. State programming
Today's topic
“State machine” and programming
Create your account on Scrapbox for taking the course.
You need a Google account (for GMail, etc.) to create a Scrapbox account.
You can create a Google accout here.
You can also use your keio.jp account (G suite account).
You can create a Scrapbox account at https://Scrapbox.io/ using your Google account.
What is a State?
Values representing current status
State machine
A machine whose state changes according to various events
Logic circuit, program, switch, etc.
Also called as “automaton”
State pattern
One of the patterns defined in “pattern languages”
Handling state transition in a class
State transition examples
Games
Light switch
Programs
Ages, grades, positions
Monopoly
state = Piece position and property
State-aware programming
Complicated user interface
Communication protocols
Pattern matching
"Escape sequence" programming
Handling comments in programs
Roma-Kana conversion
Puzzle
Roma-Kana conversion
Escape sequence
Control display with special character sequences
Used on VT100 and compatible systems
Terminal.app
xterm
Erase the whole screen
cmain(){
printf("\x1b[2J");
printf("\x1b[0;0f");
}Generate escape sequences using 'curses' library
Human state transition
State transition of a light toggle switch
State transition with hysteresis
TCP/IP state machine
State transition of a puzzle
State transition of detecting C comments
Delete
/* ... */ 
State transition of Japnese text input
Demo: Slime text input
All computers are state machines
State change by clock signals
Programming = state transition
CPU = complicated state transition machine
Combinational logic circuit
No state information
PLA (Programmable Logic Array)
Sequential circuit
State changes based on a clock signal
Current state is used in following calculation
Non-Deterministic Finite-state Automaton
Can move to multiple state
DFA
Simple
Easily implemented
Regular expressions can be easily converted to NDFA
(SUB)*SECTION (abc|ade) Converting NDFA to DFA
Any NDFA can be converted to DFA
Number of states increases
Example of conversion
(SUB)*SECTION Match with
SECTION , SUBSECTION , SUBSUBSECTION , ...
Conversion
Generated DFA
Generated DFA
Original NDFA
egrep command on Unix
Generate an NFA from a regular rexpression
Convert an NFA to DFA
Create a state transition table for DFA
Demo: egrep
Programming a DFA
Treat the execution context as the state
Use state variables
Use state transition tables
How do you program a state transition like this?
Flowchart
Detecting comment areas in C
/* ... */
Using the execution context as the state
Program execution point represents the state
comment1.c
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;
}
}
}
}
}
}
}
Results
Using the execution position
OK if state transition is straightforward
Not good for complicted state transition
Difficult to understand even simpletransitions
Using state variables
States can be represented by the values of state variables
Use if/switch for checking states
Good for simple state transitions
Simple flags are state variables
Difficult to use many state variables consistently
Impossible to check all combinations
comment2.c
comment2.ctypedef 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 buf[1000];
char *s;
while(fgets(buf,1000,stdin)){
for(s=buf;*s;s++){
trans(*s);
}
}
} State transition programming with a state transition table
States are represented as an integer value
Use a state transition table
By hand
Using a tool
State transition table
comment3.c
comment3.cenum {
S1, S2, C1, C2
};
int trans[4][0x100];
int state = S1;
void init()
{
int i;
for(i=0;i<0x100;i++){
trans[S1][i] = S1;
trans[S2][i] = S1;
trans[C1][i] = C1;
trans[C2][i] = C1;
}
trans[S1]['/'] = S2;
trans[S2]['/'] = S2;
trans[S2]['*'] = C1;
trans[C1]['*'] = C2;
trans[C2]['*'] = C2;
trans[C2]['/'] = S1;
state = S1;
}
main()
{
unsigned char buf[1000];
unsigned char *s;
init();
while(fgets(buf,1000,stdin)){
for(s=buf;*s;s++){
int oldstate = state;
state = trans[state][*s];
if(oldstate == S2 && state == C1) printf("/*");
if(oldstate == C1 || oldstate == C2) printf("%c",*s);
}
}
}State transition table generator
Converting a RegExp to a C program
lex
flex
General-purpose lexical analyzer generator
Created by Eric Schmidt
Former CEO of Google
Lex description example
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);
}
Example: lex
% lex lexsample.l% cc -ll lex.yy.c% ./a.outExtended state transition diagram
Petri net
StateChart
Petri net
Tokens, braces, transitions
The token moves when tokens are ready at the input of a transition box
Vending machine example
StateChart
Hierarchical state transition machine
Multiple states are represented as one state in an upper layer
Can be converted to conventional state machine
A CD player specification in StateChart
A CD player specification in StateChart
State transition of a Japanese text input system
Implementations
Conversion tools for StateChart
Special tools required
Using StateChart without special tools
Represent a state as a function
Pass arguments to the parent state if they cannot be handled
State is represented as the current function
A CD player implemented in JavaScript
statechart.jsfuncftion 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');
What method should we use?
Statechart for complicated state transiton
State variable may be okay for simple programs
Try using statecharts
Documents are important
Exercise
Write a simple state transition program
Use literate programming style with HTML
Extract code from the HTML document