588 Fundamental

Pattern State Automata

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Pattern State Automata" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Pattern matching in Rust goes beyond simple value checks — it enables powerful dispatch mechanisms for type-safe command processing, visitor-pattern traversals, state machine transitions, and recursive data structure manipulation. Key difference from OCaml: 1. **Box deref**: Rust requires `Box<T>` for recursive types and Rust's patterns transparently deref through `Box`; OCaml's GC manages recursive variant pointers automatically.

Tutorial

The Problem

Pattern matching in Rust goes beyond simple value checks — it enables powerful dispatch mechanisms for type-safe command processing, visitor-pattern traversals, state machine transitions, and recursive data structure manipulation. This example demonstrates advanced pattern matching techniques that arise in compiler construction, game engines, protocol implementations, and functional programming idioms applied to real systems code.

🎯 Learning Outcomes

• Advanced pattern matching constructs specific to this example's domain

• How Rust's exhaustiveness checking prevents missed cases in complex dispatch

• How patterns interact with ownership — matching by value vs by reference

• How recursive enum patterns (trees, ASTs) work with variants

• Where this technique appears in real-world Rust: compilers, game engines, CLI tools

Code Example

enum State { Idle, Running(u32), Paused(u32), Done(u32) }
enum Event { Start, Tick, Pause, Resume, Stop }

type state = Idle | Running of int | Paused of int | Done of int
type event = Start | Tick | Pause | Resume | Stop

Key Differences

Box deref: Rust requires Box<T> for recursive types and Rust's patterns transparently deref through Box; OCaml's GC manages recursive variant pointers automatically.

Const patterns: Rust allows named const values in patterns; OCaml can use let open Consts in to bring constants into scope for pattern matching.

Visitor pattern: OCaml's idiomatic style uses recursive functions directly; Rust often uses both direct recursion and the trait-based visitor pattern for separation of concerns.

State machines: Both languages naturally express state machines with variant enums + match — this is one of the strongest arguments for algebraic types over OOP class hierarchies.

OCaml Approach

OCaml's ML heritage makes it the reference implementation for these patterns. Variant types, exhaustive matching, and recursive type handling in OCaml are equivalent in power:

(* Pattern matching in OCaml handles:
   - Variant constructors with data: Cmd (arg1, arg2) -> ...
   - Guards: | x when x > threshold -> ...  
   - Nested patterns: Node { left; right } -> ...
   - Recursive cases: the natural form for tree traversal *)

Full Source

#![allow(clippy::all)]
//! # State Automata with Pattern Matching
//!
//! Implement finite state machines using enum states and tuple matching
//! for state transitions.

/// Process state with associated data.
#[derive(Debug, Clone, PartialEq)]
pub enum State {
    Idle,
    Running(u32),
    Paused(u32),
    Done(u32),
}

/// Events that can trigger state transitions.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Event {
    Start,
    Tick,
    Pause,
    Resume,
    Stop,
}

/// State transition function using tuple matching.
pub fn transition(state: State, event: Event) -> State {
    match (state, event) {
        (State::Idle, Event::Start) => State::Running(0),
        (State::Running(n), Event::Tick) => State::Running(n + 1),
        (State::Running(n), Event::Pause) => State::Paused(n),
        (State::Running(n), Event::Stop) => State::Done(n),
        (State::Paused(n), Event::Resume) => State::Running(n),
        (State::Paused(n), Event::Stop) => State::Done(n),
        (s, _) => s, // Ignore invalid transitions
    }
}

/// Describe current state in human-readable form.
pub fn describe(s: &State) -> String {
    match s {
        State::Idle => "idle".into(),
        State::Running(n) => format!("running (tick {})", n),
        State::Paused(n) => format!("paused at {}", n),
        State::Done(n) => format!("done after {} ticks", n),
    }
}

/// Check if state is terminal.
pub fn is_terminal(s: &State) -> bool {
    matches!(s, State::Done(_))
}

/// Check if state is active (running or paused).
pub fn is_active(s: &State) -> bool {
    matches!(s, State::Running(_) | State::Paused(_))
}

/// Run a sequence of events.
pub fn run_sequence(events: &[Event]) -> State {
    events.iter().fold(State::Idle, |s, &e| transition(s, e))
}

/// Traffic light state machine.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Traffic {
    Red,
    Green,
    Yellow,
}

/// Get next traffic light state (simple cycle).
pub fn next_traffic(t: Traffic) -> Traffic {
    match t {
        Traffic::Red => Traffic::Green,
        Traffic::Green => Traffic::Yellow,
        Traffic::Yellow => Traffic::Red,
    }
}

/// Traffic light with timer.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum TrafficTimed {
    Red(u32),
    Green(u32),
    Yellow(u32),
}

/// Tick traffic light timer.
pub fn tick_traffic(t: TrafficTimed) -> TrafficTimed {
    match t {
        TrafficTimed::Red(0) => TrafficTimed::Green(30), // Green for 30 ticks
        TrafficTimed::Red(n) => TrafficTimed::Red(n - 1),
        TrafficTimed::Green(0) => TrafficTimed::Yellow(5), // Yellow for 5 ticks
        TrafficTimed::Green(n) => TrafficTimed::Green(n - 1),
        TrafficTimed::Yellow(0) => TrafficTimed::Red(30), // Red for 30 ticks
        TrafficTimed::Yellow(n) => TrafficTimed::Yellow(n - 1),
    }
}

/// Connection state machine.
#[derive(Debug, Clone, PartialEq)]
pub enum ConnState {
    Disconnected,
    Connecting(String),
    Connected(String),
    Disconnecting,
}

#[derive(Debug, Clone, PartialEq)]
pub enum ConnEvent {
    Connect(String),
    Ack,
    Disconnect,
    Timeout,
}

/// Connection state transition.
pub fn conn_transition(state: ConnState, event: ConnEvent) -> ConnState {
    match (state, event) {
        (ConnState::Disconnected, ConnEvent::Connect(addr)) => ConnState::Connecting(addr),
        (ConnState::Connecting(addr), ConnEvent::Ack) => ConnState::Connected(addr),
        (ConnState::Connecting(_), ConnEvent::Timeout) => ConnState::Disconnected,
        (ConnState::Connected(_), ConnEvent::Disconnect) => ConnState::Disconnecting,
        (ConnState::Disconnecting, ConnEvent::Ack) => ConnState::Disconnected,
        (s, _) => s,
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_idle_to_running() {
        let s = transition(State::Idle, Event::Start);
        assert_eq!(s, State::Running(0));
    }

    #[test]
    fn test_running_tick() {
        let s = transition(State::Running(5), Event::Tick);
        assert_eq!(s, State::Running(6));
    }

    #[test]
    fn test_pause_resume() {
        let s = transition(State::Running(5), Event::Pause);
        assert_eq!(s, State::Paused(5));

        let s2 = transition(s, Event::Resume);
        assert_eq!(s2, State::Running(5));
    }

    #[test]
    fn test_stop_from_running() {
        let s = transition(State::Running(10), Event::Stop);
        assert_eq!(s, State::Done(10));
    }

    #[test]
    fn test_stop_from_paused() {
        let s = transition(State::Paused(7), Event::Stop);
        assert_eq!(s, State::Done(7));
    }

    #[test]
    fn test_invalid_transition_ignored() {
        let s = transition(State::Done(5), Event::Start);
        assert_eq!(s, State::Done(5));
    }

    #[test]
    fn test_describe() {
        assert_eq!(describe(&State::Idle), "idle");
        assert_eq!(describe(&State::Running(3)), "running (tick 3)");
        assert_eq!(describe(&State::Paused(5)), "paused at 5");
        assert_eq!(describe(&State::Done(10)), "done after 10 ticks");
    }

    #[test]
    fn test_is_terminal() {
        assert!(!is_terminal(&State::Idle));
        assert!(!is_terminal(&State::Running(0)));
        assert!(is_terminal(&State::Done(0)));
    }

    #[test]
    fn test_run_sequence() {
        let events = [
            Event::Start,
            Event::Tick,
            Event::Tick,
            Event::Pause,
            Event::Resume,
            Event::Tick,
            Event::Stop,
        ];
        let final_state = run_sequence(&events);
        assert_eq!(final_state, State::Done(3));
    }

    #[test]
    fn test_traffic_cycle() {
        let mut t = Traffic::Red;
        t = next_traffic(t);
        assert_eq!(t, Traffic::Green);
        t = next_traffic(t);
        assert_eq!(t, Traffic::Yellow);
        t = next_traffic(t);
        assert_eq!(t, Traffic::Red);
    }

    #[test]
    fn test_traffic_timed() {
        let mut t = TrafficTimed::Red(2);
        t = tick_traffic(t);
        assert_eq!(t, TrafficTimed::Red(1));
        t = tick_traffic(t);
        assert_eq!(t, TrafficTimed::Red(0));
        t = tick_traffic(t);
        assert_eq!(t, TrafficTimed::Green(30));
    }

    #[test]
    fn test_connection_happy_path() {
        let s = ConnState::Disconnected;
        let s = conn_transition(s, ConnEvent::Connect("127.0.0.1".into()));
        assert!(matches!(s, ConnState::Connecting(_)));
        let s = conn_transition(s, ConnEvent::Ack);
        assert!(matches!(s, ConnState::Connected(_)));
        let s = conn_transition(s, ConnEvent::Disconnect);
        assert_eq!(s, ConnState::Disconnecting);
        let s = conn_transition(s, ConnEvent::Ack);
        assert_eq!(s, ConnState::Disconnected);
    }

    #[test]
    fn test_connection_timeout() {
        let s = ConnState::Connecting("host".into());
        let s = conn_transition(s, ConnEvent::Timeout);
        assert_eq!(s, ConnState::Disconnected);
    }
}

(* Finite automaton in OCaml *)
type state = Idle | Running of int | Paused of int | Done of int

type event = Start | Tick | Pause | Resume | Stop

let transition state event =
  match (state, event) with
  | (Idle,       Start)  -> Running 0
  | (Running n,  Tick)   -> Running (n+1)
  | (Running n,  Pause)  -> Paused n
  | (Running n,  Stop)   -> Done n
  | (Paused n,   Resume) -> Running n
  | (Paused n,   Stop)   -> Done n
  | (s, _)               -> s

let describe = function
  | Idle      -> "idle"
  | Running n -> Printf.sprintf "running (tick %d)" n
  | Paused n  -> Printf.sprintf "paused at %d" n
  | Done n    -> Printf.sprintf "done after %d ticks" n

let () =
  let events = [Start;Tick;Tick;Pause;Resume;Tick;Stop] in
  let state = List.fold_left (fun s e ->
    let s' = transition s e in
    Printf.printf "-> %s\n" (describe s'); s'
  ) Idle events in
  ignore state

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_idle_to_running() {
        let s = transition(State::Idle, Event::Start);
        assert_eq!(s, State::Running(0));
    }

    #[test]
    fn test_running_tick() {
        let s = transition(State::Running(5), Event::Tick);
        assert_eq!(s, State::Running(6));
    }

    #[test]
    fn test_pause_resume() {
        let s = transition(State::Running(5), Event::Pause);
        assert_eq!(s, State::Paused(5));

        let s2 = transition(s, Event::Resume);
        assert_eq!(s2, State::Running(5));
    }

    #[test]
    fn test_stop_from_running() {
        let s = transition(State::Running(10), Event::Stop);
        assert_eq!(s, State::Done(10));
    }

    #[test]
    fn test_stop_from_paused() {
        let s = transition(State::Paused(7), Event::Stop);
        assert_eq!(s, State::Done(7));
    }

    #[test]
    fn test_invalid_transition_ignored() {
        let s = transition(State::Done(5), Event::Start);
        assert_eq!(s, State::Done(5));
    }

    #[test]
    fn test_describe() {
        assert_eq!(describe(&State::Idle), "idle");
        assert_eq!(describe(&State::Running(3)), "running (tick 3)");
        assert_eq!(describe(&State::Paused(5)), "paused at 5");
        assert_eq!(describe(&State::Done(10)), "done after 10 ticks");
    }

    #[test]
    fn test_is_terminal() {
        assert!(!is_terminal(&State::Idle));
        assert!(!is_terminal(&State::Running(0)));
        assert!(is_terminal(&State::Done(0)));
    }

    #[test]
    fn test_run_sequence() {
        let events = [
            Event::Start,
            Event::Tick,
            Event::Tick,
            Event::Pause,
            Event::Resume,
            Event::Tick,
            Event::Stop,
        ];
        let final_state = run_sequence(&events);
        assert_eq!(final_state, State::Done(3));
    }

    #[test]
    fn test_traffic_cycle() {
        let mut t = Traffic::Red;
        t = next_traffic(t);
        assert_eq!(t, Traffic::Green);
        t = next_traffic(t);
        assert_eq!(t, Traffic::Yellow);
        t = next_traffic(t);
        assert_eq!(t, Traffic::Red);
    }

    #[test]
    fn test_traffic_timed() {
        let mut t = TrafficTimed::Red(2);
        t = tick_traffic(t);
        assert_eq!(t, TrafficTimed::Red(1));
        t = tick_traffic(t);
        assert_eq!(t, TrafficTimed::Red(0));
        t = tick_traffic(t);
        assert_eq!(t, TrafficTimed::Green(30));
    }

    #[test]
    fn test_connection_happy_path() {
        let s = ConnState::Disconnected;
        let s = conn_transition(s, ConnEvent::Connect("127.0.0.1".into()));
        assert!(matches!(s, ConnState::Connecting(_)));
        let s = conn_transition(s, ConnEvent::Ack);
        assert!(matches!(s, ConnState::Connected(_)));
        let s = conn_transition(s, ConnEvent::Disconnect);
        assert_eq!(s, ConnState::Disconnecting);
        let s = conn_transition(s, ConnEvent::Ack);
        assert_eq!(s, ConnState::Disconnected);
    }

    #[test]
    fn test_connection_timeout() {
        let s = ConnState::Connecting("host".into());
        let s = conn_transition(s, ConnEvent::Timeout);
        assert_eq!(s, ConnState::Disconnected);
    }
}

Deep Comparison

OCaml vs Rust: State Automata

State and Event Types

OCaml

type state = Idle | Running of int | Paused of int | Done of int
type event = Start | Tick | Pause | Resume | Stop

Rust

enum State { Idle, Running(u32), Paused(u32), Done(u32) }
enum Event { Start, Tick, Pause, Resume, Stop }

Transition Function

OCaml

let transition state event =
  match (state, event) with
  | (Idle,       Start)  -> Running 0
  | (Running n,  Tick)   -> Running (n+1)
  | (Running n,  Pause)  -> Paused n
  | (Running n,  Stop)   -> Done n
  | (Paused n,   Resume) -> Running n
  | (Paused n,   Stop)   -> Done n
  | (s, _)               -> s

Rust

fn transition(state: State, event: Event) -> State {
    match (state, event) {
        (State::Idle, Event::Start) => State::Running(0),
        (State::Running(n), Event::Tick) => State::Running(n + 1),
        (State::Running(n), Event::Pause) => State::Paused(n),
        (State::Running(n), Event::Stop) => State::Done(n),
        (State::Paused(n), Event::Resume) => State::Running(n),
        (State::Paused(n), Event::Stop) => State::Done(n),
        (s, _) => s,
    }
}

Key Pattern: (State, Event) Tuple

The tuple (state, event) makes transition tables explicit and readable:

• Each arm is one valid transition

• Wildcard (s, _) handles invalid/ignored transitions

• Compiler ensures exhaustiveness

Running the Machine

OCaml

let final_state = List.fold_left transition Idle events

Rust

let final_state = events.iter().fold(State::Idle, |s, &e| transition(s, e));

Benefits

Clear transition table - All transitions in one place

Exhaustiveness - Compiler checks all cases

Pure function - No hidden state mutation

Testable - Easy to test individual transitions

Exercises

Extend the data type: Add a new variant or field to the main data structure and trace all the match expressions that need updating — practice the exhaustiveness feedback loop.

Accumulating visitor: Write a traversal function that collects all leaf values into a Vec<T> using only pattern matching and recursion.

State machine validation: Implement an invalid-transition error: when the state/event combination is unexpected, return Err("invalid transition") instead of panicking.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust