188 Expert

Operational Monad

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Operational Monad" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. The operational monad is a variant of the free monad that separates the description of primitive instructions from the composition mechanism (bind/sequence). Key difference from OCaml: 1. **Result type tracking**: OCaml's GADT `'a instruction` encodes the result type per instruction; Rust's `Instruction<A>` simulates this with continuations.

Tutorial

The Problem

The operational monad is a variant of the free monad that separates the description of primitive instructions from the composition mechanism (bind/sequence). Instead of encoding both instructions and sequencing in one recursive type, the operational monad has two layers: Instruction<A> (user-defined operations) and Program<A> (sequencing). This reduces boilerplate compared to free monads and makes adding new instructions simpler — only the instruction type changes.

🎯 Learning Outcomes

• Understand the operational monad as an alternative to free monads

• Learn how Program<A> wraps instructions with a universal bind mechanism

• See how the two-layer design simplifies adding new instruction types

• Understand the trade-offs between free monads and the operational monad in Rust

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Operational monad: instructions are a GADT; programs build the sequence.
   Similar to free monad but more explicit about the instruction set. *)

(* Instruction set for a simple IO DSL *)
type _ instr =
  | Read  : string instr
  | Write : string -> unit instr

(* Programs: sequence of instructions *)
type _ prog =
  | Return : 'a -> 'a prog
  | Instr  : 'a instr * ('a -> 'b prog) -> 'b prog

let return x     = Return x
let read ()      = Instr (Read,    return)
let write s      = Instr (Write s, fun () -> Return ())

let rec bind m f = match m with
  | Return x         -> f x
  | Instr (i, cont)  -> Instr (i, fun x -> bind (cont x) f)

(* Pure interpreter using a list as stdin *)
let run_pure inputs prog =
  let buf = Buffer.create 64 in
  let inputs = ref inputs in
  let rec go : type a. a prog -> a = function
    | Return x -> x
    | Instr (Read, cont) ->
      let line = List.hd !inputs in
      inputs := List.tl !inputs;
      go (cont line)
    | Instr (Write s, cont) ->
      Buffer.add_string buf (s ^ "\n");
      go (cont ())
  in
  (go prog, Buffer.contents buf)

let () =
  let prog =
    bind (write "Enter name:") (fun () ->
    bind (read ())              (fun name ->
    bind (write ("Hello, " ^ name ^ "!")) (fun () ->
    return name)))
  in
  let (result, output) = run_pure ["Alice"] prog in
  Printf.printf "Output:\n%s" output;
  Printf.printf "Result: %s\n" result

Key Differences

Result type tracking: OCaml's GADT 'a instruction encodes the result type per instruction; Rust's Instruction<A> simulates this with continuations.

Two layers: Both separate instruction definitions from sequencing; the operational monad's two-type design is explicit where free monads combine both in one recursive type.

Adding instructions: Adding a new instruction requires only a new variant in Instruction; the Program wrapper and interpreter are unaffected (open-closed principle).

Efficiency: The operational monad has the same theoretical complexity as free monads; both build heap-allocated trees proportional to program size.

OCaml Approach

OCaml's operational monad uses GADTs for the instruction type:

type _ instruction =
  | ReadLine : string instruction
  | Print : string -> unit instruction
type _ program =
  | Done : 'a -> 'a program
  | Instr : 'a instruction * ('a -> 'b program) -> 'b program

The GADT instruction type ensures that ReadLine : string instruction — the instruction's result type is tracked. Rust's version uses boxed closures to simulate this.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Operational monad: instructions are a GADT; programs build the sequence.
   Similar to free monad but more explicit about the instruction set. *)

(* Instruction set for a simple IO DSL *)
type _ instr =
  | Read  : string instr
  | Write : string -> unit instr

(* Programs: sequence of instructions *)
type _ prog =
  | Return : 'a -> 'a prog
  | Instr  : 'a instr * ('a -> 'b prog) -> 'b prog

let return x     = Return x
let read ()      = Instr (Read,    return)
let write s      = Instr (Write s, fun () -> Return ())

let rec bind m f = match m with
  | Return x         -> f x
  | Instr (i, cont)  -> Instr (i, fun x -> bind (cont x) f)

(* Pure interpreter using a list as stdin *)
let run_pure inputs prog =
  let buf = Buffer.create 64 in
  let inputs = ref inputs in
  let rec go : type a. a prog -> a = function
    | Return x -> x
    | Instr (Read, cont) ->
      let line = List.hd !inputs in
      inputs := List.tl !inputs;
      go (cont line)
    | Instr (Write s, cont) ->
      Buffer.add_string buf (s ^ "\n");
      go (cont ())
  in
  (go prog, Buffer.contents buf)

let () =
  let prog =
    bind (write "Enter name:") (fun () ->
    bind (read ())              (fun name ->
    bind (write ("Hello, " ^ name ^ "!")) (fun () ->
    return name)))
  in
  let (result, output) = run_pure ["Alice"] prog in
  Printf.printf "Output:\n%s" output;
  Printf.printf "Result: %s\n" result

Deep Comparison

OCaml vs Rust: Operational Monad

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Add a Sleep(duration_ms: u64) instruction and implement both a real (actual sleep) and mock (instant) interpreter for it.

Implement instruction fusion: detect and merge consecutive Print operations into a single buffered write.

Write a to_io_actions(program: Program<A>) -> Vec<IoAction> function that serializes a program to a list of actions without executing them.

Open Source Repos

functional-rust

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

Rust