Finite State Machine

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)))

  • Thinking in Scenarios Simplifies Scoping

    When scoping out and planning work, an easy way to get a comprehensive understanding of everything that needs to happen is to enumerate every scenario. I find this technique saves a lot of time and clarifies what to do in a way that avoids surprises later.