186 Expert

Free Monad Interpreters

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Free Monad Interpreters" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. The power of free monads is multiple interpreters for the same program. Key difference from OCaml: 1. **Effect handlers vs. free monads**: OCaml 5's effect handlers are a native runtime mechanism; free monads are a library pattern — effect handlers are faster and more composable.

Tutorial

The Problem

The power of free monads is multiple interpreters for the same program. A console DSL program can be interpreted by a "real" interpreter that reads from stdin and writes to stdout, a "test" interpreter that uses mock I/O with predetermined inputs, and a "logging" interpreter that records every operation for debugging. The program description is shared; only the interpreter changes. This is the essence of dependency injection at the computation level.

🎯 Learning Outcomes

• Implement multiple interpreters for the same free monad DSL

• Understand how different interpreters provide testability, logging, and simulation

• Learn the interpreter pattern: fold the free monad tree with different algebras

• See the analogy to dependency injection: swapping interpreters changes the computation's context

Code Example

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

(* Free monad: build a DSL as a data structure, then interpret it.
   The program is pure; side effects only happen at interpretation. *)

(* DSL: a simple key-value store language *)
type 'a store_f =
  | Get : string * (string option -> 'a) -> 'a store_f
  | Put : string * string * 'a -> 'a store_f
  | Delete : string * 'a -> 'a store_f

(* Free monad *)
type 'a free =
  | Pure : 'a -> 'a free
  | Free : 'a free store_f -> 'a free

let pure x = Pure x

let get k f    = Free (Get (k, (fun v -> Pure (f v))))
let put k v a  = Free (Put (k, v, Pure a))
let delete k a = Free (Delete (k, Pure a))

let rec bind m f = match m with
  | Pure x -> f x
  | Free (Get (k, cont))    -> Free (Get (k, fun v -> bind (cont v) f))
  | Free (Put (k, v, next)) -> Free (Put (k, v, bind next f))
  | Free (Delete (k, next)) -> Free (Delete (k, bind next f))

(* Interpreter 1: in-memory hashtable *)
let run_memory tbl program =
  let rec go = function
    | Pure x -> x
    | Free (Get (k, cont))    -> go (cont (Hashtbl.find_opt tbl k))
    | Free (Put (k, v, next)) -> Hashtbl.replace tbl k v; go next
    | Free (Delete (k, next)) -> Hashtbl.remove tbl k; go next
  in go program

(* Interpreter 2: pure association list *)
let run_pure store program =
  let rec go store = function
    | Pure x -> (x, store)
    | Free (Get (k, cont))    -> go store (cont (List.assoc_opt k store))
    | Free (Put (k, v, next)) -> go ((k,v) :: List.filter (fun (k',_) -> k' <> k) store) next
    | Free (Delete (k, next)) -> go (List.filter (fun (k',_) -> k' <> k) store) next
  in go store program

let () =
  (* Build the program once *)
  let program =
    bind (put "name" "Alice" ()) (fun () ->
    bind (put "age"  "30"    ()) (fun () ->
    bind (get "name" (fun v -> v)) (fun name ->
    pure name)))
  in

  (* Run with two different interpreters *)
  let tbl = Hashtbl.create 4 in
  let result1 = run_memory tbl program in
  Printf.printf "memory interp: %s\n" (Option.value result1 ~default:"none");

  let (result2, _) = run_pure [] program in
  Printf.printf "pure interp:   %s\n" (Option.value result2 ~default:"none")

Key Differences

Effect handlers vs. free monads: OCaml 5's effect handlers are a native runtime mechanism; free monads are a library pattern — effect handlers are faster and more composable.

Mutual recursion: OCaml's run_io and run_test can be let rec; Rust's interpreter functions are plain functions called recursively.

State threading: The test interpreter threads mutable state (inputs, outputs) through the traversal; in OCaml this is often done with a state monad or ref cells.

Stack depth: Both interpreters recurse on the continuation tree — deep programs risk stack overflow; trampolining (example 197) resolves this.

OCaml Approach

OCaml's interpreter pattern is identical in structure. The run_io and run_test functions use let rec and pattern matching. OCaml's effect handlers (OCaml 5) provide a more efficient alternative to free monads for the same separation: effects are declared, then handled by different effect handlers — the operational semantics is similar to free monad interpreters but implemented at the runtime level.

Full Source

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

(* Free monad: build a DSL as a data structure, then interpret it.
   The program is pure; side effects only happen at interpretation. *)

(* DSL: a simple key-value store language *)
type 'a store_f =
  | Get : string * (string option -> 'a) -> 'a store_f
  | Put : string * string * 'a -> 'a store_f
  | Delete : string * 'a -> 'a store_f

(* Free monad *)
type 'a free =
  | Pure : 'a -> 'a free
  | Free : 'a free store_f -> 'a free

let pure x = Pure x

let get k f    = Free (Get (k, (fun v -> Pure (f v))))
let put k v a  = Free (Put (k, v, Pure a))
let delete k a = Free (Delete (k, Pure a))

let rec bind m f = match m with
  | Pure x -> f x
  | Free (Get (k, cont))    -> Free (Get (k, fun v -> bind (cont v) f))
  | Free (Put (k, v, next)) -> Free (Put (k, v, bind next f))
  | Free (Delete (k, next)) -> Free (Delete (k, bind next f))

(* Interpreter 1: in-memory hashtable *)
let run_memory tbl program =
  let rec go = function
    | Pure x -> x
    | Free (Get (k, cont))    -> go (cont (Hashtbl.find_opt tbl k))
    | Free (Put (k, v, next)) -> Hashtbl.replace tbl k v; go next
    | Free (Delete (k, next)) -> Hashtbl.remove tbl k; go next
  in go program

(* Interpreter 2: pure association list *)
let run_pure store program =
  let rec go store = function
    | Pure x -> (x, store)
    | Free (Get (k, cont))    -> go store (cont (List.assoc_opt k store))
    | Free (Put (k, v, next)) -> go ((k,v) :: List.filter (fun (k',_) -> k' <> k) store) next
    | Free (Delete (k, next)) -> go (List.filter (fun (k',_) -> k' <> k) store) next
  in go store program

let () =
  (* Build the program once *)
  let program =
    bind (put "name" "Alice" ()) (fun () ->
    bind (put "age"  "30"    ()) (fun () ->
    bind (get "name" (fun v -> v)) (fun name ->
    pure name)))
  in

  (* Run with two different interpreters *)
  let tbl = Hashtbl.create 4 in
  let result1 = run_memory tbl program in
  Printf.printf "memory interp: %s\n" (Option.value result1 ~default:"none");

  let (result2, _) = run_pure [] program in
  Printf.printf "pure interp:   %s\n" (Option.value result2 ~default:"none")

Deep Comparison

OCaml vs Rust: Free Monad Interp

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

Implement a "counting" interpreter that returns the number of I/O operations performed.

Write a "recording" interpreter that captures the full execution trace as a Vec<(Operation, Value)>.

Add a timeout interpreter: if the program performs more than N ReadLine operations, terminate with an error.

Open Source Repos

functional-rust

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

Rust