Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 40 ยท Projects and Practice

Project: A State Machine that Makes Illegal States Impossible

Model an order workflow in OCaml with variant types and a transition function. Make invalid states unrepresentable, return result errors, replay event logs with folds and add an abstract account module.

Many real programs are state machines: orders move from cart to paid to shipped, connections open and close, parsers switch modes. In most languages, the state is a string or an enum plus a pile of nullable fields, and bugs creep in when a field is read in a state where it does not exist. In OCaml a variant type holds exactly the data each state needs, so many mistakes cannot even be written.

In this project you model an online order, write the transition function, handle errors with result, replay an event log with a fold, and then wrap an account in an abstract module.

OCaml is not available in the site's code runners, so the OCaml code is read-only (OCaml 5, standard library only). A Python mirror below runs the same workflow here, and the outputs shown come from it.

States and events

OCAML
type items = (string * int) list     (* (name, price in cents) *)

type state =
  | Cart of { items : items }
  | Placed of { items : items; total : int }
  | Paid of { total : int; receipt : string }
  | Shipped of { receipt : string; tracking : string }
  | Cancelled of { reason : string }

type event =
  | Add_item of string * int
  | Place
  | Pay of int
  | Ship of string
  | Cancel of string

type error =
  | Empty_cart
  | Wrong_amount of { expected : int; got : int }
  | Invalid_transition of { state : string; event : string }

Look at what is missing: a Cart has no receipt, a Shipped order has no items. Only a paid order has a receipt number, so no code can read a receipt from an unpaid order. This is the design principle make illegal states unrepresentable from variant types.

stateDiagram-v2
    [*] --> Cart
    Cart --> Cart: Add_item
    Cart --> Placed: Place
    Placed --> Paid: Pay
    Paid --> Shipped: Ship
    Cart --> Cancelled: Cancel
    Placed --> Cancelled: Cancel

Figure: the allowed transitions. Anything not on the diagram is an error.

The transition function

One function takes the current state and an event and returns the next state or an error. It is a single pattern match on the pair:

OCAML
let state_name = function
  | Cart _ -> "Cart" | Placed _ -> "Placed" | Paid _ -> "Paid"
  | Shipped _ -> "Shipped" | Cancelled _ -> "Cancelled"

let event_name = function
  | Add_item _ -> "Add_item" | Place -> "Place" | Pay _ -> "Pay"
  | Ship _ -> "Ship" | Cancel _ -> "Cancel"

let step state event : (state, error) result =
  match (state, event) with
  | Cart { items }, Add_item (name, price) ->
      Ok (Cart { items = (name, price) :: items })
  | Cart { items = [] }, Place -> Error Empty_cart
  | Cart { items }, Place ->
      let total = List.fold_left (fun acc (_, p) -> acc + p) 0 items in
      Ok (Placed { items; total })
  | Placed { total; _ }, Pay amount when amount = total ->
      Ok (Paid { total; receipt = Printf.sprintf "R-%d" total })
  | Placed { total; _ }, Pay amount ->
      Error (Wrong_amount { expected = total; got = amount })
  | Paid { receipt; _ }, Ship tracking -> Ok (Shipped { receipt; tracking })
  | (Cart _ | Placed _), Cancel reason -> Ok (Cancelled { reason })
  | s, e -> Error (Invalid_transition { state = state_name s; event = event_name e })

The order of arms matters: the empty-cart case comes before the general Place. The final arm catches everything else, which is acceptable here because the invalid combinations are exactly "all the rest". If you prefer the compiler to remind you about new states, list them explicitly instead.

Replaying events

A state machine is a function from states and events to states, so a whole history is a fold. Stop at the first error with Result.bind:

OCAML
let run events =
  List.fold_left
    (fun acc ev -> Result.bind acc (fun s -> step s ev))
    (Ok (Cart { items = [] }))
    events

let ok = run [ Add_item ("pen", 150); Add_item ("book", 1200); Place; Pay 1350; Ship "TRK-1" ]
(* Ok (Shipped { receipt = "R-1350"; tracking = "TRK-1" }) *)

let early_ship = run [ Add_item ("pen", 150); Ship "TRK-1" ]
(* Error (Invalid_transition { state = "Cart"; event = "Ship" }) *)

Because step is pure, you can store the event list (an event log), replay it to rebuild any state, test it without mocks, and branch from an old state to explore "what if".

Reporting

OCAML
let error_message = function
  | Empty_cart -> "cannot place an empty order"
  | Wrong_amount { expected; got } -> Printf.sprintf "expected %d but got %d" expected got
  | Invalid_transition { state; event } -> Printf.sprintf "%s is not allowed in state %s" event state

Runnable mirror in Python

Python Stand-in: the order workflow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Python version needs run-time checks for every illegal combination and cannot stop you from building ("Paid", 5) with the wrong shape. The OCaml compiler checks the shape of every state value.

An abstract account module

For state that changes over time inside a program (rather than a log of events), combine an abstract type with an imperative core, using what you learned in modules and signatures:

OCAML
module Account : sig
  type t
  type error = Insufficient_funds of int | Invalid_amount
  val create : owner:string -> t
  val balance : t -> int
  val deposit : t -> int -> (unit, error) result
  val withdraw : t -> int -> (unit, error) result
  val history : t -> string list
end = struct
  type t = { owner : string; mutable balance : int; mutable log : string list }
  type error = Insufficient_funds of int | Invalid_amount

  let create ~owner = { owner; balance = 0; log = [] }
  let balance a = a.balance
  let history a = List.rev a.log

  let record a msg = a.log <- Printf.sprintf "%s: %s" a.owner msg :: a.log

  let deposit a n =
    if n <= 0 then Error Invalid_amount
    else (a.balance <- a.balance + n; record a (Printf.sprintf "deposit %d" n); Ok ())

  let withdraw a n =
    if n <= 0 then Error Invalid_amount
    else if n > a.balance then Error (Insufficient_funds a.balance)
    else (a.balance <- a.balance - n; record a (Printf.sprintf "withdraw %d" n); Ok ())
end

Outside the module the record is invisible, so nobody can set balance directly: every change goes through deposit or withdraw, which check the rules and write the log. This is the "invariant protected by an abstract type" idea in one screen.

Ideas to extend

  • Add Refund of string and a Refunded state, and let the compiler show you every match to update.
  • Print the machine as a diagram by listing all (state, event) pairs that return Ok.
  • Persist the event list to a file as JSON using your JSON printer and replay it on start-up.
  • Write property tests: "a run never ends in Paid without passing through Placed".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does Paid carry a receipt while Cart does not?

    Variant constructors with their own fields make illegal states unrepresentable.
  2. 2. What is a good way to replay a list of events through the machine?

    The fold threads the state through each event and bind short-circuits on the first Error.
  3. 3. Why is step easy to test?

    Pure functions need no mocks. Give them an input and compare the output.
  4. 4. What does the abstract type in Account achieve?

    Hiding the representation protects invariants such as "balance never goes negative".

Summary

  • Give each state its own constructor and its own data. Illegal states then cannot be written.
  • A pure step : state -> event -> (state, error) result makes behaviour testable and replayable.
  • A fold over events rebuilds any state, and result carries the first error.
  • For long-lived mutable state, wrap it in a module with an abstract type so the rules cannot be bypassed.

Next: Practice Problems with Solutions