A model of computation where there is exactly one state at a time of a fixed number states. The current state can be changed by transitioning to another. Using state machines has the benefit of 1) being easy to reason about what the program does e.g. security audit and 2) making obvious what a valid state is so the programmer doesn’t accidentally put into a ‘bad’ state i.e. reduce bugs.
Example applications:
- Modeling authentication flows using a deterministic state machine to prove it can not be exploited
- Modeling a user interface that has several modes to prevent bugs where a user gets stuck in an unrecoverable state
The following example uses rustlang’s type system to model a finite state machine where transitions can be passed additional typed arguments:
pub struct StateMachine<T> {
pub state: T
}
pub struct StateMachineWithArgs<T> {
pub state: T,
}
pub trait TransitionFrom<T, R> {
fn transition_from(state: T, args: R) -> Self;
}
pub trait State {
type Args;
fn new(args: Self::Args) -> Self;
}
impl<T> StateMachineWithArgs<T> where T: State {
pub fn new(state: T) -> Self {
StateMachineWithArgs { state }
}
}
struct StateOne;
impl State for StateOne {
type Args = ();
fn new(args: Self::Args) -> Self {
Self {}
}
}
struct StateTwo;
impl State for StateTwo {
type Args = ();
fn new(args: Self::Args) -> Self {
Self {}
}
}
struct StateThree;
impl State for StateThree {
type Args = ();
fn new(args: Self::Args) -> Self {
Self {}
}
}
// Implement state transitions by implementing the TransitionFrom trait.
// Doing this enforces only known transitions at compile time i.e.
// you get a compile time error that two states can't be transitioned to
impl TransitionFrom<StateMachineWithArgs<StateOne>, ()> for StateMachineWithArgs<StateTwo> {
fn transition_from(state: StateMachineWithArgs<StateOne>, args: ()) -> StateMachineWithArgs<StateTwo> {
StateMachineWithArgs::new(StateTwo::new(args))
}
}
impl TransitionFrom<StateMachineWithArgs<StateTwo>, ()> for StateMachineWithArgs<StateThree> {
fn transition_from(state: StateMachineWithArgs<StateTwo>, args: ()) -> StateMachineWithArgs<StateThree> {
StateMachineWithArgs::new(StateThree::new(args))
}
}
mod test_state_machine {
use super::*;
#[test]
fn it_works() {
// Initialize the state machine starting with the first state
let state_one = StateMachineWithArgs::new(StateOne::new(()));
// Transition to the next state
let state_two = StateMachineWithArgs::<StateTwo>::transition_from(state_one, ());
// This won't compile because it's not a valid transition!
StateMachineWithArgs::<StateThree>::transition_from(state_one, ());
}
}
In python with typing:
import typing as t
from functools import singledispatch
from dataclasses import dataclass
@dataclass
class State1():
check_me: bool
class State2():
pass
class State3():
pass
class State4():
pass
State = t.Union[
State1,
State2,
State3,
State4,
]
@singledispatch
def transition(state: State) -> t.Optional[State]:
pass
@transition.register
def state1_to_state2(state: State1) -> t.Optional[t.Union[State2, State3]]:
if state.check_me:
return State2()
return State3()
@transition.register
def state2_to_state3(state: State2) -> t.Optional[State3]:
return State3()
@transition.register
def state3_to_state4(state: State3) -> t.Optional[State4]:
return State4()
# Run the state machine to completion
transition(transition(transition(State1(check_me=True))))
transition(transition(State1(check_me=False)))