State Machine
Introduction¶
The state machine is the tool that developers must have in their toolbox.
If you are new to the state machine, check out the reference section below.
How can a state machine help?
Typically, when building applications, we follow what's known as the event-driven — where an event happens in the application, we update the application state and render the state to the screen.
Events can happen anytime during user interactions and system interactions, while the application can be in any state. Therefore, before we start to handle the events, we first have to determine the current state and then handle the event accordingly. Sometimes it can be challenging.
The state machine provides a state-event-state mapping. Thus, before we start to handle the events, we know the current state and the future state, so that we only need to focus on the limited state-event scope.
The specific state machine we are going to use is the Mealy machine. It has an initial state and then transitions to new states based on events and its current state.
We are going to build a calculator application as an example. You will learn from this post:
- Model a state machine declaratively,
- Make the state machine type-safe
- Add the state machine to the AppRun application
Model a Calculator¶
State and Event¶
The calculator application looks like this:
const find_transition = (state_machine, state, event) => {
const current_state = state_machine[state];
if (!current_state) throw new Error(`No state: ${current_state} found in state machine`);
const event_tuple = current_state.find(s => s[0] === event);
return event_tuple ? {
next_state: event_tuple[1],
transition: event_tuple[2]
} : {}
};
const state = {
_state: 'START',
display: '0',
arg1: 0,
arg2: 0,
op: '',
stack: []
};
const view = ({ _state, op, arg1, arg2, display, stack }) => <>
<style> {`
.calculator { width: 200px; }
.buttons {
display: grid;
grid-template-columns: repeat(4, 1fr);
grid-gap: 2px;
}
button { padding: 10px; width:100%; }
button:nth-of-type(1) {
grid-column: span 2;
}
button:nth-of-type(16) {
grid-column: span 2;
}
`}
</style>
<div class="calculator">
<h1>{display}</h1>
<div class="buttons" $onclick={button_click}>
<button>CE</button>
<button>+/-</button>
<button>/</button>
<button>7</button>
<button>8</button>
<button>9</button>
<button>*</button>
<button>4</button>
<button>5</button>
<button>6</button>
<button>-</button>
<button>1</button>
<button>2</button>
<button>3</button>
<button>+</button>
<button>0</button>
<button>.</button>
<button>=</button>
</div>
<small>
{stack.length > 0 && `${stack[0][0]} ${stack[0][1]} `}
{_state.startsWith("FIRST_") && `${display}`}
{_state === "OP" && `${arg1} ${op}`}
{_state.startsWith("SECOND_") && `${arg1} ${op} ${display}`}
{_state === "EQ" && `${arg1} ${op} ${arg2} = ${display}`}
</small>
</div>
</>;
const button_click = (state, e) => {
const priority = {
'*': 2,
'/': 2,
'+': 1,
'-': 1
}
const getEvent = c => {
switch (c) {
case '+/-':
return '+/-';
case 'CE':
return 'CE';
case '.':
return 'DOT';
case '=':
return 'EQ';
default:
return /\d/.test(c) ? 'NUM' : 'OP';
}
};
const key = e.target?.textContent || e;
const event = getEvent(key);
let { _state, op, arg1, arg2, display, stack } = state;
const clear = () => {
display = '0';
arg1 = arg2 = 0;
op = '';
stack.length = 0;
}
const negative = () => {
display = display.startsWith('-') ? display.substring(1) : '-' + display;
};
const calc = () => {
display = eval(`${arg1}${op}${arg2}`).toString();
};
const op1 = () => {
op = key;
arg1 = parseFloat(display);
};
const op2 = () => {
if (priority[key] === priority[op]) {
arg2 = parseFloat(display);
calc();
op = key;
arg1 = parseFloat(display);
} else if (priority[key] < priority[op]) {
arg2 = parseFloat(display);
calc();
arg1 = parseFloat(display);
op = key;
if (stack.length) {
const f = stack.pop();
arg1 = eval(`${f[0]}${f[1]}${display}`);
display = arg1.toString();
}
} else {
stack.push([arg1, op]);
arg1 = parseFloat(display);
op = key;
}
};
const eq0 = () => {
arg1 = parseFloat(display);
calc();
};
const eq2 = () => {
arg2 = parseFloat(display);
calc();
if (stack.length) {
arg2 = parseFloat(display);
const f = stack.pop();
display = eval(`${f[0]}${f[1]}${display}`).toString();
arg1 = f[0];
op = f[1];
}
};
const state_machine = {
START: [
['NUM', 'FIRST_ARG', () => display = key],
['DOT', 'FIRST_ARG_FLOAT', () => display = '0.']
],
FIRST_ARG: [
['+/-', 'FIRST_ARG', negative],
['NUM', 'FIRST_ARG', () => display += key],
['DOT', 'FIRST_ARG_FLOAT', () => display += key],
['OP', 'OP', op1],
['CE', 'START', clear]
],
FIRST_ARG_FLOAT: [
['+/-', 'FIRST_ARG_FLOAT', negative],
['NUM', 'FIRST_ARG_FLOAT', () => display += key],
['OP', 'OP', op1],
['CE', 'START', clear]
],
OP: [
['NUM', 'SECOND_ARG', () => display = key],
['DOT', 'SECOND_ARG', () => display = '0.'],
['OP', 'OP', () => op = key],
['CE', 'START', clear]
],
SECOND_ARG: [
['+/-', 'SECOND_ARG', negative],
['NUM', 'SECOND_ARG', () => display += key],
['DOT', 'SECOND_ARG_FLOAT', () => display += key],
['EQ', 'EQ', eq2],
['OP', 'OP', op2],
['CE', 'OP', () => display = '0']
],
SECOND_ARG_FLOAT: [
['+/-', 'SECOND_ARG_FLOAT', negative],
['NUM', 'SECOND_ARG_FLOAT', () => display += key],
['EQ', 'EQ', eq2],
['OP', 'OP', op2],
['CE', 'OP', () => display = '0']
],
EQ: [
['+/-', 'FIRST_ARG', negative],
['NUM', 'FIRST_ARG', () => display = key],
['DOT', 'FIRST_ARG_FLOAT', () => display = '0.'],
['EQ', 'EQ', eq0],
['OP', 'OP', op1],
['CE', 'START', clear]
]
};
const { next_state, transition } = find_transition(state_machine, _state, event);
_state = next_state || _state;
transition && transition();
return { _state, op, arg1, arg2, display, stack };
}
app.start(document.body, state, view);
Click the 'Try the Code' button; you will see the source code.
The calculator has a grid of buttons that users can click at any time. It also displays:
- The numbers that the user typed and the calculation result on top of the grid.
- The calculation formula includes the first argument, the operator, and the second argument, and the calculation result below the gird.
Let's model the initial state of the calculator.
const state = {
display: '0',
arg1: 0,
arg2: 0,
op: '',
};
We handle the buttons' click events in the event handler, button___click. Because of the HTML event bubbling, we only need one event handler for all the buttons.
const view =
<div class="buttons" $onclick={button_click}>
......
</div>
const button_click = (state, e) => {
}
app.start(document.body, state, view);
That's all we need to do to create an AppRun application, an initial state, a view, and event handlers.
Next, we will add the state machine implementation.
State Machine¶
We follow and extend the calculator state machine from David's post. The post also provides a diagram helpful to understand the state machine.
We first define the states and events of the state machine using TypeScript Discriminated Unions.
type Events = 'NUM' | 'OP' | 'DOT' | 'CE' | 'EQ' | '+/-';
type States =
'START' |
'FIRST_ARG' |
'FIRST_ARG_FLOAT' |
'OP' |
'SECOND_ARG' |
'SECOND_ARG_FLOAT' |
'EQ';
We then define the state machine. It is a collection of all the states. Each state has a list of available events and transitions in an array. The transition is the function to update the state.
const state_machine = {
START: [
['NUM', 'FIRST_ARG', () => display = key],
['DOT', 'FIRST_ARG_FLOAT', () => display = '0.']
],
FIRST_ARG: [
['+/-', 'FIRST_ARG', negative],
['NUM', 'FIRST_ARG', () => display += key],
['DOT', 'FIRST_ARG_FLOAT', () => display += key],
['OP', 'OP', op1],
['CE', 'START', clear]
],
...
}
For example, when the current state is START, and the NUM event comes, the new state should be 'FIRST_ARG (waiting for 1st argument)'. The display property of the state should be the user's input.
Another example, when the current state is FIRST_ARG, and the +/- event comes, the display property should toggle between positive and negative.
So on and so forth. It is straightforward to create the state machine object according to the diagram.
Next, we make the state machine type-safe by adding more types.
export type Transition = () => void;
export type EventStateTransition<E, S> = [E, S, Transition];
export type StateMachine<S extends string, E> = {
[key in S]: EventStateTransition<E, S>[];
};
- The Tansition is a function to update the application state.
- The EventStateTransition is a TypeScript Tuple. It describes which event leads to which new state.
- The StateMachine is an object that uses the _States as the index key.
Now, the state machine is type-safe. The TypeScript compiler only allows you to use the states and events defined in States and Events.
const state_machine: StateMachine<States, Events> = {
START0: [ // Error on START0
['NUM0', 'FIRST_ARG', () => {}], // Error on NUM0
['DOT', 'FIRST_ARG_FLOAT0', () => {}] // Error on FIRST_ARG_FLOAT0
],
}
Also, the compiler makes sure all States have their relevant entries in the state machine.
const state_machine: StateMachine<States, Events> = {
START: [],
FIRST_ARG: [],
FIRST_ARG_FLOAT: [],
OP:[], SECOND_ARG:[],
SECOND_ARG_FLOAT:[],
//EQ:[] // Error on missing EQ state, if we commented it out
}
Add State-Machine State¶
We add a new property for tracking the state-machine state, called _state, into the initial state.
const state = {
_state: 'START' as States,
display: '0',
arg1: 0,
arg2: 0,
op: '',
};
export type State = typeof state;
Convert UI Events¶
All button clicks use the button___click event handler. We convert UI events into different state-machine events.
export const button_click = (state: State, e: any) => {
const getEvent = (c: string): Events => {
switch (c) {
case '+/-':
return '+/-';
case 'CE':
return 'CE';
case '.':
return 'DOT';
case '=':
return 'EQ';
default:
return /\d/.test(c) ? 'NUM' : 'OP';
}
};
const key = e.target?.textContent || e;
const event = getEvent(key);
}
Use State Machine¶
Now that we know the current state-machine state from the _state property of the application state. We also know which state-machine event we are in. We now can use the state___machine to find the matching transition.
Finding transitions from the state___machine is straightforward.
const find_transition = <S extends string, E>(
state_machine: StateMachine<S, E>,
state: S,
event: E
): { next_state?: S, transition?: Transition } => {
const current_state = state_machine[state];
if (!current_state) throw new Error(`No state: ${current_state} found in state machine`);
const event_tuple = current_state.find(s => s[0] === event);
return event_tuple ? {
next_state: event_tuple[1],
transition: event_tuple[2]
} : {}
};
If we found the transition, we run the transition function. It updates the destructed application state properties, such as op, arg1, arg2, and display accordingly. We then update the application state to be the next state.
const button_click = (state, e) => {
let { _state, op, arg1, arg2, display } = state;
const event = getEvent(s);
const state_machine = {
};
const { next_state, transition } = find_transition(state_machine, _state, event);
transition && transition();
_state = next_state || _state;
return { _state, op, arg1, arg2, display };
}
If no transition found, nothing will happen.
Finally, we return a new state from the event handler; AppRun will render the screen accordingly.
Now, we have successfully created the calculator application. You can see the calculator in TypeScript below.
Source
export type Transition<T = any> = (state?: T) => void;
export type EventStateTransition<E, S> = [E, S, Transition];
export type StateMachine<S extends string, E> = {
[key in S]: EventStateTransition<E, S>[];
};
export const find_transition = <S extends string, E>(
state_machine: StateMachine<S, E>,
state: S,
event: E
): { next_state?: S, transition?: Transition } => {
const current_state = state_machine[state];
if (!current_state) throw new Error(`No state: ${current_state} found in state machine`);
const event_tuple = current_state.find(s => s[0] === event);
return event_tuple ? {
next_state: event_tuple[1],
transition: event_tuple[2]
} : {}
};
import app, { Component } from '../../src/apprun';
import { StateMachine, find_transition } from './state-machine';
type Events = 'NUM' | 'OP' | 'DOT' | 'CE' | 'EQ' | '+/-';
type States = 'START' | 'FIRST_ARG' | 'FIRST_ARG_FLOAT' | 'OP' | 'SECOND_ARG' | 'SECOND_ARG_FLOAT' | 'EQ';
const state = {
_state: 'START' as States,
display: '0',
arg1: 0,
arg2: 0,
op: '',
stack: []
};
export type State = typeof state;
const view = ({ _state, op, arg1, arg2, display, stack }: State) => <>
<style> {`
.calculator { width: 200px; }
.buttons {
display: grid;
grid-template-columns: repeat(4, 1fr);
grid-gap: 2px;
}
button { padding: 10px; width:100%; }
button:nth-of-type(1) {
grid-column: span 2;
}
button:nth-of-type(16) {
grid-column: span 2;
}
`}
</style>
<div class="calculator">
<h1>{display}</h1>
<div class="buttons" $onclick={button_click}>
<button>CE</button>
<button>+/-</button>
<button>/</button>
<button>7</button>
<button>8</button>
<button>9</button>
<button>*</button>
<button>4</button>
<button>5</button>
<button>6</button>
<button>-</button>
<button>1</button>
<button>2</button>
<button>3</button>
<button>+</button>
<button>0</button>
<button>.</button>
<button>=</button>
</div>
<small>
{stack.length > 0 && `${stack[0][0]} ${stack[0][1]} `}
{_state.startsWith("FIRST_") && `${display}`}
{_state === "OP" && `${arg1} ${op}`}
{_state.startsWith("SECOND_") && `${arg1} ${op} ${display}`}
{_state === "EQ" && `${arg1} ${op} ${arg2} = ${display}`}
</small>
</div>
</>;
export const button_click = (state: State, e: any) => {
const priority = {
'*': 2,
'/': 2,
'+': 1,
'-': 1
}
const getEvent = (c: string): Events => {
switch (c) {
case '+/-':
return '+/-';
case 'CE':
return 'CE';
case '.':
return 'DOT';
case '=':
return 'EQ';
default:
return /\d/.test(c) ? 'NUM' : 'OP';
}
};
const key = e.target?.textContent || e;
const event = getEvent(key);
let { _state, op, arg1, arg2, display, stack } = state;
const clear = () => {
display = '0';
arg1 = arg2 = 0;
op = '';
stack.length = 0;
}
const negative = () => {
display = display.startsWith('-') ? display.substring(1) : '-' + display;
};
const calc = () => {
display = eval(`${arg1}${op}${arg2}`).toString();
};
const op1 = () => {
op = key;
arg1 = parseFloat(display);
};
const op2 = () => {
if (priority[key] === priority[op]) {
arg2 = parseFloat(display);
calc();
op = key;
arg1 = parseFloat(display);
} else if (priority[key] < priority[op]) {
arg2 = parseFloat(display);
calc();
arg1 = parseFloat(display);
op = key;
if (stack.length) {
const f = stack.pop();
arg1 = eval(`${f[0]}${f[1]}${display}`);
display = arg1.toString();
}
} else {
stack.push([arg1, op]);
arg1 = parseFloat(display);
op = key;
}
};
const eq0 = () => {
arg1 = parseFloat(display);
calc();
};
const eq2 = () => {
arg2 = parseFloat(display);
calc();
if (stack.length) {
arg2 = parseFloat(display);
const f = stack.pop();
display = eval(`${f[0]}${f[1]}${display}`).toString();
arg1 = f[0];
op = f[1];
}
};
const state_machine: StateMachine<States, Events> = {
START: [
['NUM', 'FIRST_ARG', () => display = key],
['DOT', 'FIRST_ARG_FLOAT', () => display = '0.']
],
FIRST_ARG: [
['+/-', 'FIRST_ARG', negative],
['NUM', 'FIRST_ARG', () => display += key],
['DOT', 'FIRST_ARG_FLOAT', () => display += key],
['OP', 'OP', op1],
['CE', 'START', clear]
],
FIRST_ARG_FLOAT: [
['+/-', 'FIRST_ARG_FLOAT', negative],
['NUM', 'FIRST_ARG_FLOAT', () => display += key],
['OP', 'OP', op1],
['CE', 'START', clear]
],
OP: [
['NUM', 'SECOND_ARG', () => display = key],
['DOT', 'SECOND_ARG', () => display = '0.'],
['OP', 'OP', () => op = key],
['CE', 'START', clear]
],
SECOND_ARG: [
['+/-', 'SECOND_ARG', negative],
['NUM', 'SECOND_ARG', () => display += key],
['DOT', 'SECOND_ARG_FLOAT', () => display += key],
['EQ', 'EQ', eq2],
['OP', 'OP', op2],
['CE', 'OP', () => display = '0']
],
SECOND_ARG_FLOAT: [
['+/-', 'SECOND_ARG_FLOAT', negative],
['NUM', 'SECOND_ARG_FLOAT', () => display += key],
['EQ', 'EQ', eq2],
['OP', 'OP', op2],
['CE', 'OP', () => display = '0']
],
EQ: [
['+/-', 'FIRST_ARG', negative],
['NUM', 'FIRST_ARG', () => display = key],
['DOT', 'FIRST_ARG_FLOAT', () => display = '0.'],
['EQ', 'EQ', eq0],
['OP', 'OP', op1],
['CE', 'START', clear]
]
};
const { next_state, transition } = find_transition(state_machine, _state, event);
_state = next_state || _state;
transition && transition();
return { _state, op, arg1, arg2, display, stack };
};
const update = {
'#calculator': state => state
};
export default element => new Component(state, view, update).mount(element);
import { button_click, State } from './calculator';
const state: State = {
_state: 'START',
display: '0',
arg1: 0,
arg2: 0,
op: '',
stack: []
};
const click = (input: string) => {
const keys = [...input];
let s = state;
keys.forEach(key => {
const new_state = button_click(s, key);
s = new_state
})
return s;
}
describe('calculator', () => {
it('case 1', () => {
const { _state, display } = click('1');
expect(display).toBe('1');
expect(_state).toBe('FIRST_ARG');
})
it('case 2', () => {
const { _state, display } = click('12');
expect(display).toBe('12');
expect(_state).toBe('FIRST_ARG');
})
it('case 3', () => {
const { _state, display, arg1, arg2 } = click('1+2=');
expect(display).toBe('3');
expect(arg1).toBe(1);
expect(arg2).toBe(2);
expect(_state).toBe('EQ');
})
it('case 4', () => {
const { _state, display } = click('1/');
expect(display).toBe('1');
expect(_state).toBe('OP');
})
it('case 5', () => {
const { _state, display } = click('1/2');
expect(display).toBe('2');
expect(_state).toBe('SECOND_ARG');
})
it('case 6', () => {
const { _state, display, op } = click('1//');
expect(display).toBe('1');
expect(op).toBe('/');
expect(_state).toBe('OP');
})
it('case 7', () => {
const { _state, display, op } = click('1/=');
expect(display).toBe('1');
expect(op).toBe('/');
expect(_state).toBe('OP');
})
it('case 8', () => {
const { _state, display, op } = click('1/+');
expect(display).toBe('1');
expect(op).toBe('+');
expect(_state).toBe('OP');
})
it('case 9', () => {
const { _state, display } = click('1/10');
expect(display).toBe('10');
expect(_state).toBe('SECOND_ARG');
})
it('case 10', () => {
const { _state, display } = click('1+1.');
expect(display).toBe('1.');
expect(_state).toBe('SECOND_ARG_FLOAT');
})
it('case 11', () => {
const { _state, display } = click('0.');
expect(display).toBe('0.');
expect(_state).toBe('FIRST_ARG_FLOAT');
})
it('case 12', () => {
const { _state, display } = click('=');
expect(display).toBe('0');
expect(_state).toBe('START');
})
it('case 13', () => {
const { _state, display } = click('/');
expect(display).toBe('0');
expect(_state).toBe('START');
})
it('case 14', () => {
const { _state, display } = click('1+2=5');
expect(display).toBe('5');
expect(_state).toBe('FIRST_ARG');
})
it('case 15', () => {
const { _state, display } = click('1+2=/');
expect(display).toBe('3');
expect(_state).toBe('OP');
})
it('case 16', () => {
const { _state, display } = click('1/+=');
expect(display).toBe('1');
expect(_state).toBe('OP');
})
it('case 17', () => {
const { _state, display } = click('1+2=*3=');
expect(display).toBe('9');
expect(_state).toBe('EQ');
})
it('case 18', () => {
const { _state, display, arg1, arg2 } = click('1+2*3=');
expect(display).toBe('7');
expect(arg1).toBe(1);
expect(arg2).toBe(6);
expect(_state).toBe('EQ');
})
it('case 19', () => {
const { _state, display, arg1, arg2 } = click('1*2+3=');
expect(display).toBe('5');
expect(arg1).toBe(2);
expect(arg2).toBe(3);
expect(_state).toBe('EQ');
})
it('case 20', () => {
const { _state, display } = click('1+2*3*');
expect(display).toBe('6');
expect(_state).toBe('OP');
})
});
Conclusion¶
We have created a declarative and type-safe state machine. The state machine data structure is technology agnostic. You can try to use it in React or other frameworks you like. It can naturally fit into AppRun applications.
AppRun is event-driven. Often I feel it is challenging to make events right. Sometimes we define too many events. Sometimes the events come out of order. By using the state machine, I can handle the events within limited state scopes. I have started to think of using more state machines to control the events.
References¶
There are many references online about the state machine. I got most of my inspiration from the following posts. I recommend you read the concept explanation of the posts and pay less attention to the implementations because using AppRun; you can do better.
-
[1] Krasimir Tsonev explains Mealy and Moore in the post: The Rise Of The State Machines
-
[2] Jon Bellah describes the paradigm shift from event-driven to the state machine in this post: A Complete Introduction to State Machines in JavaScript
-
[3] Erik Mogensen explains state machine and introduced the statechart in this post: What is a state machine?
Have fun coding!