257: State Machine — Turnstile

Difficulty: 2 Level: Intermediate Model a finite state machine as enums and match transitions — the compiler guarantees exhaustive coverage.

The Problem This Solves

A turnstile has two states: Locked and Unlocked. Two events: Coin (insert a coin) and Push (push the arm). The transition rules are simple — coin unlocks it, push locks it (if unlocked), and invalid events leave the state unchanged. This is a finite state machine (FSM): a fixed set of states, a fixed set of events, and defined transitions between them. FSMs appear everywhere: network protocol parsers, user interface flows, vending machines, game character AI, compiler lexers. The key property is exhaustiveness: every (state, event) combination must have a defined outcome. In most languages, missing a case means a runtime error. In Rust (and OCaml), it means a compile error. This example shows how to encode FSMs idiomatically in Rust: enums for states and events, `match` on a tuple `(state, event)` for transitions, and `Iterator::fold` / `Iterator::scan` for running a sequence of events through the machine.

The Intuition

An FSM is like a flowchart with no loops to infinity. You're always in exactly one box (state). An event draws an arrow to the next box. If there's no arrow for that event from your current box, you stay put. In Rust, the entire transition table is one `match` expression on `(self, event)`. Every arm is one row in the transition table. If you add a new state or event and forget to handle a combination, the compiler refuses to compile. This is the power of exhaustive pattern matching — the type system enforces completeness. `Iterator::fold` drives the machine: start with the initial state, process each event in sequence, thread the resulting state through. `scan` is the same but collects every intermediate state — useful for tracing execution.

How It Works in Rust

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum State { Locked, Unlocked }

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Event { Coin, Push }

impl State {
 pub fn transition(self, event: Event) -> Self {
     match (self, event) {
         (Self::Locked,   Event::Coin) => Self::Unlocked, // coin unlocks
         (Self::Unlocked, Event::Push) => Self::Locked,   // push locks
         (Self::Locked,   Event::Push) => Self::Locked,   // push when locked: no-op
         (Self::Unlocked, Event::Coin) => Self::Unlocked, // coin when unlocked: no-op
     }
 }
}

// Run a sequence of events, returning the final state
pub fn run(initial: State, events: &[Event]) -> State {
 events.iter().fold(initial, |state, &event| state.transition(event))
}

// Collect every intermediate state (useful for testing and tracing)
pub fn trace(initial: State, events: &[Event]) -> Vec<State> {
 events.iter()
     .scan(initial, |state, &event| {
         *state = state.transition(event);
         Some(*state)
     })
     .collect()
}

`Copy` makes `State` and `Event` zero-cost to pass around — no cloning, no borrowing, just value semantics. This is idiomatic for small, cheaply-copied types.

What This Unlocks

Protocol parsers — model TCP states (SYN_SENT, ESTABLISHED, FIN_WAIT), HTTP parsing phases, or MQTT client states as enums.
UI flows — modal dialogs, multi-step wizards, and menu navigation become FSMs with clear compile-time guarantees.
Game AI — enemy states (Idle → Alert → Attacking → Fleeing) as enums; `transition` becomes the AI logic kernel.

Key Differences

Concept	OCaml	Rust
Type definition	`type state = Locked \	Unlocked`	`enum State { Locked, Unlocked }`
Transition	Free function `let transition state event = ...`	Method `impl State { fn transition(self, ...) }`
Tuple match	`match (state, event) with ...`	`match (self, event) { ... }` — identical syntax
Fold simulation	`List.fold_left transition initial events`	`events.iter().fold(initial, \	s, &e\	s.transition(e))`
Exhaustiveness	Type checker enforces it	`match` exhaustiveness check at compile time

/// The two states a turnstile can be in.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum State {
    Locked,
    Unlocked,
}

/// Events that can be applied to a turnstile.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Event {
    Coin,
    Push,
}

impl State {
    pub fn transition(self, event: Event) -> Self {
        match (self, event) {
            (Self::Locked, Event::Coin) => Self::Unlocked,
            (Self::Unlocked, Event::Push) => Self::Locked,
            (Self::Locked, Event::Push) => Self::Locked,
            (Self::Unlocked, Event::Coin) => Self::Unlocked,
        }
    }

    pub fn name(self) -> &'static str {
        match self {
            Self::Locked => "Locked",
            Self::Unlocked => "Unlocked",
        }
    }
}

pub fn run_machine(initial: State, events: &[Event]) -> (State, Vec<(State, State)>) {
    let mut transitions = Vec::with_capacity(events.len());
    let final_state = events.iter().fold(initial, |s, &e| {
        let next = s.transition(e);
        transitions.push((s, next));
        next
    });
    (final_state, transitions)
}

pub fn transition(state: State, event: Event) -> State {
    state.transition(event)
}

pub fn fold_events(initial: State, events: &[Event]) -> Vec<State> {
    std::iter::once(initial)
        .chain(events.iter().scan(initial, |s, &e| {
            *s = transition(*s, e);
            Some(*s)
        }))
        .collect()
}

fn main() {
    let events = [
        Event::Coin,
        Event::Push,
        Event::Push,
        Event::Coin,
        Event::Coin,
        Event::Push,
    ];

    println!("=== Turnstile state machine ===");
    let (final_state, pairs) = run_machine(State::Locked, &events);
    for (before, after) in &pairs {
        println!("{} -> {}", before.name(), after.name());
    }
    println!("Final: {}", final_state.name());

    println!("\n=== Fold trace (including initial) ===");
    let trace = fold_events(State::Locked, &events);
    for s in &trace {
        println!("{}", s.name());
    }
}

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

    #[test]
    fn test_locked_coin_unlocks() {
        assert_eq!(State::Locked.transition(Event::Coin), State::Unlocked);
    }

    #[test]
    fn test_unlocked_push_locks() {
        assert_eq!(State::Unlocked.transition(Event::Push), State::Locked);
    }

    #[test]
    fn test_locked_push_stays_locked() {
        assert_eq!(State::Locked.transition(Event::Push), State::Locked);
    }

    #[test]
    fn test_unlocked_coin_stays_unlocked() {
        assert_eq!(State::Unlocked.transition(Event::Coin), State::Unlocked);
    }

    #[test]
    fn test_ocaml_sequence_final_state() {
        let events = [
            Event::Coin,
            Event::Push,
            Event::Push,
            Event::Coin,
            Event::Coin,
            Event::Push,
        ];
        let (final_state, _) = run_machine(State::Locked, &events);
        assert_eq!(final_state, State::Locked);
    }

    #[test]
    fn test_ocaml_sequence_transitions() {
        let events = [
            Event::Coin,
            Event::Push,
            Event::Push,
            Event::Coin,
            Event::Coin,
            Event::Push,
        ];
        let (_, pairs) = run_machine(State::Locked, &events);
        assert_eq!(
            pairs,
            vec![
                (State::Locked, State::Unlocked),
                (State::Unlocked, State::Locked),
                (State::Locked, State::Locked),
                (State::Locked, State::Unlocked),
                (State::Unlocked, State::Unlocked),
                (State::Unlocked, State::Locked),
            ]
        );
    }

    #[test]
    fn test_empty_sequence() {
        let (final_state, pairs) = run_machine(State::Locked, &[]);
        assert_eq!(final_state, State::Locked);
        assert!(pairs.is_empty());
    }

    #[test]
    fn test_fold_events_trace() {
        let events = [Event::Coin, Event::Push, Event::Push];
        let trace = fold_events(State::Locked, &events);
        assert_eq!(
            trace,
            vec![
                State::Locked,
                State::Unlocked,
                State::Locked,
                State::Locked,
            ]
        );
    }

    #[test]
    fn test_free_transition_matches_method() {
        for &state in &[State::Locked, State::Unlocked] {
            for &event in &[Event::Coin, Event::Push] {
                assert_eq!(transition(state, event), state.transition(event));
            }
        }
    }

    #[test]
    fn test_state_names() {
        assert_eq!(State::Locked.name(), "Locked");
        assert_eq!(State::Unlocked.name(), "Unlocked");
    }
}

/* Output:
   === Turnstile state machine ===
   Locked -> Unlocked
   Unlocked -> Locked
   Locked -> Locked
   Locked -> Unlocked
   Unlocked -> Unlocked
   Unlocked -> Locked
   Final: Locked

   === Fold trace (including initial) ===
   Locked
   Unlocked
   Locked
   Locked
   Unlocked
   Unlocked
   Locked
*/

(* Example 257: State Machine — Turnstile *)
(* Encoding a finite state machine with algebraic types and pattern matching *)

(* Idiomatic OCaml — types and a transition function *)
type state = Locked | Unlocked
type event = Coin | Push

let transition state event = match state, event with
  | Locked, Coin -> Unlocked
  | Unlocked, Push -> Locked
  | Locked, Push -> Locked
  | Unlocked, Coin -> Unlocked

let state_name = function Locked -> "Locked" | Unlocked -> "Unlocked"

(* Recursive style — fold the event list, accumulating state *)
let rec run_machine state = function
  | [] -> state
  | event :: rest ->
    let next = transition state event in
    run_machine next rest

let () =
  (* Basic transition assertions *)
  assert (transition Locked Coin = Unlocked);
  assert (transition Unlocked Push = Locked);
  assert (transition Locked Push = Locked);
  assert (transition Unlocked Coin = Unlocked);

  (* OCaml sequence: Coin Push Push Coin Coin Push starting from Locked *)
  let events = [Coin; Push; Push; Coin; Coin; Push] in

  (* Print each step — mirrors the original snippet *)
  let _final = List.fold_left (fun s e ->
    let s' = transition s e in
    Printf.printf "%s -> %s\n" (state_name s) (state_name s');
    s'
  ) Locked events in

  (* Recursive version gives the same final state *)
  assert (run_machine Locked events = Locked);
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: State Machine — Turnstile

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

type state = Locked | Unlocked
type event = Coin | Push

let transition state event = match state, event with
| Locked, Coin -> Unlocked
| Unlocked, Push -> Locked
| Locked, Push -> Locked
| Unlocked, Coin -> Unlocked

let state_name = function Locked -> "Locked" | Unlocked -> "Unlocked"

let () =
let events = [Coin; Push; Push; Coin; Coin; Push] in
let final = List.fold_left (fun s e ->
 let s' = transition s e in
 Printf.printf "%s -> %s\n" (state_name s) (state_name s');
 s'
) Locked events in
Printf.printf "Final: %s\n" (state_name final)

Rust (idiomatic — method on enum)

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum State { Locked, Unlocked }

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Event { Coin, Push }

impl State {
 pub fn transition(self, event: Event) -> Self {
     match (self, event) {
         (Self::Locked,   Event::Coin) => Self::Unlocked,
         (Self::Unlocked, Event::Push) => Self::Locked,
         (Self::Locked,   Event::Push) => Self::Locked,
         (Self::Unlocked, Event::Coin) => Self::Unlocked,
     }
 }

 pub fn name(self) -> &'static str {
     match self { Self::Locked => "Locked", Self::Unlocked => "Unlocked" }
 }
}

pub fn run_machine(initial: State, events: &[Event]) -> (State, Vec<(State, State)>) {
 let mut transitions = Vec::with_capacity(events.len());
 let final_state = events.iter().fold(initial, |s, &e| {
     let next = s.transition(e);
     transitions.push((s, next));
     next
 });
 (final_state, transitions)
}

Rust (functional style — free function mirrors OCaml)

pub fn transition(state: State, event: Event) -> State {
 state.transition(event)
}

/// Mirrors: List.fold_left (fun s e -> transition s e) initial events
/// scan yields every intermediate state, including the initial value.
pub fn fold_events(initial: State, events: &[Event]) -> Vec<State> {
 std::iter::once(initial)
     .chain(events.iter().scan(initial, |s, &e| {
         *s = transition(*s, e);
         Some(*s)
     }))
     .collect()
}

Type Signatures

Concept	OCaml	Rust
State type	`type state = Locked \	Unlocked`	`enum State { Locked, Unlocked }`
Event type	`type event = Coin \	Push`	`enum Event { Coin, Push }`
Transition	`val transition : state -> event -> state`	`fn transition(self, Event) -> Self`
Fold over events	`List.fold_left f initial events`	`events.iter().fold(initial, f)`
Scan with trace	`List.fold_left` + side effects	`Iterator::scan`
Copy value	implicit (OCaml values copied freely)	`#[derive(Clone, Copy)]` explicit

Key Insights

1. Tuple match syntax is identical: Both OCaml `match state, event with` and Rust `match (self, event)` destructure a pair of discriminants. The arm bodies differ only in syntax, not in logic.

2. Method vs free function: OCaml's free `transition` function is equally valid in Rust, but placing it as `State::transition` is idiomatic — behaviour lives with the type. Both forms appear in `lib.rs` to show the parallel.

3. `Copy` eliminates borrowing ceremony: Marking `State` and `Event` as `Copy` means every function can take values instead of references. No `&State` vs `State` decisions needed — the type is as cheap as an integer.

4. `scan` is fold with observable intermediate states: OCaml uses `fold_left` with `printf` inside the accumulator closure to observe each step. Rust's `scan` achieves the same: it threads mutable state through an iterator, yielding every intermediate value. `once(initial).chain(scan(...))` produces the full trace including the starting state.

5. Exhaustiveness is guaranteed in both languages: The compiler verifies that every `(State, Event)` pair is handled. Adding a new variant to either enum immediately produces a compile error, making state machine evolution safe by construction.

When to Use Each Style

Use method-on-enum (idiomatic Rust) when: you want the transition logic discoverable through the type, benefit from IDE autocompletion on `state.`, and prefer keeping related behaviour co-located with the data.

Use free-function style when: you are porting OCaml directly and want the parallel to remain visually obvious, or when the transition function needs to be passed as a first-class value (e.g., `events.iter().fold(initial, |s, &e| transition(s, e))`).