734 Advanced

734-typestate-basics — Typestate Basics

Functional Programming

Tutorial

The Problem

State machines are everywhere: network connections, file handles, protocol sessions, UI wizards. The standard approach encodes state as a runtime enum and adds match checks before every operation. This moves errors from compile time to runtime — you can write socket.send(data) on a closed socket and only discover the bug at runtime. The typestate pattern encodes state in the type parameter itself, making invalid transitions a compile error. Zero-cost at runtime: all phantom data is erased.

🎯 Learning Outcomes

• Encode state as zero-sized marker types (Red, Green, Yellow)

• Use PhantomData<State> to carry type-level state without runtime overhead

• Implement state transitions by consuming self and returning a different type

• Understand why invalid transitions fail at compile time rather than runtime

• Verify that size_of::<Light<Red>>() equals size_of::<Light<Green>>() — zero overhead

Code Example

#![allow(clippy::all)]
/// 734: Typestate Basics — compile-time state machine
/// Invalid transitions DO NOT compile. No runtime checks needed.
use std::marker::PhantomData;

// ── State marker types (zero-sized) ──────────────────────────────────────────

pub struct Red;
pub struct Green;
pub struct Yellow;

// ── Traffic Light ─────────────────────────────────────────────────────────────

/// `PhantomData<State>` is zero bytes at runtime.
/// The type parameter encodes which state we're in.
pub struct Light<State> {
    _state: PhantomData<State>,
}

impl Light<Red> {
    /// Only way to create a light — must start Red.
    pub fn new() -> Self {
        println!("Light: Red");
        Light {
            _state: PhantomData,
        }
    }

    /// Red → Green (consumes self, returns different type)
    pub fn go(self) -> Light<Green> {
        println!("Light: Green");
        Light {
            _state: PhantomData,
        }
    }
}

impl Light<Green> {
    /// Green → Yellow
    pub fn slow(self) -> Light<Yellow> {
        println!("Light: Yellow");
        Light {
            _state: PhantomData,
        }
    }
}

impl Light<Yellow> {
    /// Yellow → Red
    pub fn stop(self) -> Light<Red> {
        println!("Light: Red");
        Light {
            _state: PhantomData,
        }
    }
}

// ── Size check ────────────────────────────────────────────────────────────────

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

    #[test]
    fn full_cycle_compiles() {
        let red = Light::<Red>::new();
        let green = red.go();
        let yellow = green.slow();
        let _red2 = yellow.stop();
    }

    #[test]
    fn light_is_zero_sized() {
        assert_eq!(std::mem::size_of::<Light<Red>>(), 0);
        assert_eq!(std::mem::size_of::<Light<Green>>(), 0);
        assert_eq!(std::mem::size_of::<Light<Yellow>>(), 0);
    }

    // Uncommenting the test below would fail to COMPILE — which is the point:
    //
    // #[test]
    // fn invalid_transition_compile_error() {
    //     let r = Light::<Red>::new();
    //     let _ = r.slow();  // compile error: method not found
    // }
}

(* 734: Typestate Basics — OCaml GADT approach
   OCaml doesn't have zero-cost phantom types like Rust, but GADTs let us
   encode state in the type safely. *)

(* State phantom types *)
type red = Red
type green = Green
type yellow = Yellow

(* Traffic light parameterized by phantom state *)
(* We use a simple record + witness value *)
type 'state light = {
  state_name: string;
  _phantom: 'state;  (* phantom field to carry state type *)
}

(* Type-safe constructors and transitions *)
let red_light () : red light = { state_name = "Red"; _phantom = Red }

let green_of_red (l : red light) : green light =
  let _ = l in
  { state_name = "Green"; _phantom = Green }

let yellow_of_green (l : green light) : yellow light =
  let _ = l in
  { state_name = "Yellow"; _phantom = Yellow }

let red_of_yellow (l : yellow light) : red light =
  let _ = l in
  { state_name = "Red"; _phantom = Red }

let print_light l = Printf.printf "Light is: %s\n" l.state_name

let () =
  let r = red_light () in
  print_light r;
  let g = green_of_red r in
  print_light g;
  let y = yellow_of_green g in
  print_light y;
  let r2 = red_of_yellow y in
  print_light r2;
  (* Invalid: green_of_red y  ← would be a type error in OCaml too! *)
  ignore r2

Key Differences

Syntax: Rust uses impl Light<Red> { fn go(self) -> Light<Green> }; OCaml uses phantom type variables and module signatures to restrict operations.

GADTs: OCaml's GADTs can encode complex state invariants that Rust's trait system cannot easily express without macros.

Consumption: Rust's move semantics make "consume self to transition" natural; OCaml's immutable values must use abstract types to prevent reuse of old states.

Zero cost: Both approaches are zero-cost at runtime — phantom types carry no runtime representation in either language.

OCaml Approach

OCaml achieves typestate via phantom types in the module system. A ('state) light type carries a phantom type variable, and functors or abstract types prevent construction of invalid states. The classic technique uses empty types or abstract module types as state markers. OCaml's GADTs (generalized algebraic data types) provide an even more powerful mechanism for encoding state invariants directly in the type index.

Full Source

#![allow(clippy::all)]
/// 734: Typestate Basics — compile-time state machine
/// Invalid transitions DO NOT compile. No runtime checks needed.
use std::marker::PhantomData;

// ── State marker types (zero-sized) ──────────────────────────────────────────

pub struct Red;
pub struct Green;
pub struct Yellow;

// ── Traffic Light ─────────────────────────────────────────────────────────────

/// `PhantomData<State>` is zero bytes at runtime.
/// The type parameter encodes which state we're in.
pub struct Light<State> {
    _state: PhantomData<State>,
}

impl Light<Red> {
    /// Only way to create a light — must start Red.
    pub fn new() -> Self {
        println!("Light: Red");
        Light {
            _state: PhantomData,
        }
    }

    /// Red → Green (consumes self, returns different type)
    pub fn go(self) -> Light<Green> {
        println!("Light: Green");
        Light {
            _state: PhantomData,
        }
    }
}

impl Light<Green> {
    /// Green → Yellow
    pub fn slow(self) -> Light<Yellow> {
        println!("Light: Yellow");
        Light {
            _state: PhantomData,
        }
    }
}

impl Light<Yellow> {
    /// Yellow → Red
    pub fn stop(self) -> Light<Red> {
        println!("Light: Red");
        Light {
            _state: PhantomData,
        }
    }
}

// ── Size check ────────────────────────────────────────────────────────────────

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

    #[test]
    fn full_cycle_compiles() {
        let red = Light::<Red>::new();
        let green = red.go();
        let yellow = green.slow();
        let _red2 = yellow.stop();
    }

    #[test]
    fn light_is_zero_sized() {
        assert_eq!(std::mem::size_of::<Light<Red>>(), 0);
        assert_eq!(std::mem::size_of::<Light<Green>>(), 0);
        assert_eq!(std::mem::size_of::<Light<Yellow>>(), 0);
    }

    // Uncommenting the test below would fail to COMPILE — which is the point:
    //
    // #[test]
    // fn invalid_transition_compile_error() {
    //     let r = Light::<Red>::new();
    //     let _ = r.slow();  // compile error: method not found
    // }
}

(* 734: Typestate Basics — OCaml GADT approach
   OCaml doesn't have zero-cost phantom types like Rust, but GADTs let us
   encode state in the type safely. *)

(* State phantom types *)
type red = Red
type green = Green
type yellow = Yellow

(* Traffic light parameterized by phantom state *)
(* We use a simple record + witness value *)
type 'state light = {
  state_name: string;
  _phantom: 'state;  (* phantom field to carry state type *)
}

(* Type-safe constructors and transitions *)
let red_light () : red light = { state_name = "Red"; _phantom = Red }

let green_of_red (l : red light) : green light =
  let _ = l in
  { state_name = "Green"; _phantom = Green }

let yellow_of_green (l : green light) : yellow light =
  let _ = l in
  { state_name = "Yellow"; _phantom = Yellow }

let red_of_yellow (l : yellow light) : red light =
  let _ = l in
  { state_name = "Red"; _phantom = Red }

let print_light l = Printf.printf "Light is: %s\n" l.state_name

let () =
  let r = red_light () in
  print_light r;
  let g = green_of_red r in
  print_light g;
  let y = yellow_of_green g in
  print_light y;
  let r2 = red_of_yellow y in
  print_light r2;
  (* Invalid: green_of_red y  ← would be a type error in OCaml too! *)
  ignore r2

✓ Tests Rust test suite

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

    #[test]
    fn full_cycle_compiles() {
        let red = Light::<Red>::new();
        let green = red.go();
        let yellow = green.slow();
        let _red2 = yellow.stop();
    }

    #[test]
    fn light_is_zero_sized() {
        assert_eq!(std::mem::size_of::<Light<Red>>(), 0);
        assert_eq!(std::mem::size_of::<Light<Green>>(), 0);
        assert_eq!(std::mem::size_of::<Light<Yellow>>(), 0);
    }

    // Uncommenting the test below would fail to COMPILE — which is the point:
    //
    // #[test]
    // fn invalid_transition_compile_error() {
    //     let r = Light::<Red>::new();
    //     let _ = r.slow();  // compile error: method not found
    // }
}

Exercises

Add a blink() method to Light<Yellow> that returns Light<Yellow> (self-transition), and verify it compiles without allowing blink() on other states.

Model a vending machine with states Idle, ItemSelected, PaymentReceived, and Dispensing. Enforce that payment can only happen after selection.

Write a sequence function fn traffic_cycle(light: Light<Red>) -> Light<Red> that goes through a full Red→Green→Yellow→Red cycle and returns the light to its starting state.

Open Source Repos

functional-rust

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

Rust