250 Expert

Grand Synthesis

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Grand Synthesis" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. This capstone example weaves together every major concept from this series: recursion schemes, optics, free monads, comonads, type-level programming, parser combinators, and categorical abstractions. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

This capstone example weaves together every major concept from this series: recursion schemes, optics, free monads, comonads, type-level programming, parser combinators, and categorical abstractions. The goal is to build a small but complete functional language interpreter that demonstrates how these patterns compose: the AST is defined as a fixed-point type, evaluation uses a catamorphism, variable scoping uses the Reader monad, a free monad models effectful operations, lenses navigate nested state, and Cofree annotates the AST with type information.

🎯 Learning Outcomes

• Compose recursion schemes, optics, monads, and comonads in a single coherent system

• See how each abstraction handles exactly the problem it was designed for

• Understand the layered architecture of a functional interpreter

• Recognize the categorical structure underlying practical programming patterns

• Appreciate how Rust's type system enforces correctness at each layer

Code Example

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

(* Grand synthesis: a mini functional system combining:
   - Type-safe DSL (tagless final)
   - Monadic error handling
   - Functors and natural transformations
   - CPS and trampolining
   The goal: a validated data pipeline with logging *)

(* Validation applicative *)
type ('a, 'e) validated =
  | Valid   of 'a
  | Invalid of 'e list

let valid x    = Valid x
let invalid e  = Invalid [e]

let map_v f = function
  | Valid x     -> Valid (f x)
  | Invalid es  -> Invalid es

let apply_v f_v x_v = match f_v, x_v with
  | Valid f, Valid x             -> Valid (f x)
  | Invalid e, Valid _           -> Invalid e
  | Valid _, Invalid e           -> Invalid e
  | Invalid e1, Invalid e2       -> Invalid (e1 @ e2)

(* Validated pipeline for a user record *)
type user = { name: string; age: int; email: string }

let validate_name s =
  if String.length s >= 2 then valid s
  else invalid "name too short (min 2 chars)"

let validate_age n =
  if n >= 0 && n < 150 then valid n
  else invalid (Printf.sprintf "age %d out of range" n)

let validate_email s =
  if String.contains s '@' then valid s
  else invalid "email missing @"

let make_user name age email = { name; age; email }

let validate_user name age email =
  apply_v
    (apply_v (map_v make_user (validate_name name))
             (validate_age age))
    (validate_email email)

(* CPS logger *)
let with_log label f x k =
  let result = f x in
  k (Printf.sprintf "[%s] %s -> " label x) result

let () =
  (* Valid user *)
  (match validate_user "Alice" 30 "alice@example.com" with
   | Valid u    -> Printf.printf "Valid user: %s, %d, %s\n" u.name u.age u.email
   | Invalid es -> Printf.printf "Errors: %s\n" (String.concat "; " es));

  (* Multiple validation errors accumulate *)
  (match validate_user "A" 200 "bad-email" with
   | Valid _    -> assert false
   | Invalid es ->
     Printf.printf "Errors (%d):\n" (List.length es);
     List.iter (Printf.printf "  - %s\n") es);

  Printf.printf "\nGrand synthesis: FP patterns compose.\n"

Key Differences

Aspect	Rust	OCaml
Recursive types	`Box<ExprF<Expr>>`	native recursive types
Pattern matching	exhaustive, verbose	exhaustive, concise
Free monad	trait objects	polymorphic variants
Lens	explicit get/set fns	record functional update
Effects	enum + interpreter	`Effect` library / algebraic effects
Performance	zero-cost abstractions	GC overhead, JIT optim

The grand synthesis reveals the payoff of learning each abstraction individually: they compose cleanly, each handling one concern, and the Rust type system ensures each boundary is sound.

OCaml Approach

OCaml achieves the same architecture more concisely:

type expr_f = Lit of float | Var of string | Add of 'r * 'r
            | Let of string * 'r * 'r | Lam of string * 'r | App of 'r * 'r

(* Catamorphism via fold *)
let rec eval env = function
  | Lit n -> Ok (Num n)
  | Var x -> List.assoc_opt x env |> Option.to_result ~none:(Printf.sprintf "Unbound: %s" x)
  | Add (l, r) -> ...
  | Let (name, v, b) -> eval env v >>= fun vv -> eval ((name, vv) :: env) b
  | Lam (p, b) -> Ok (Closure (p, b, env))
  | App (f, x) -> eval env f >>= function
      | Closure (p, b, ce) -> eval env x >>= fun xv -> eval ((p, xv) :: ce) b
      | _ -> Error "Not a function"

OCaml's algebraic types, pattern matching, >>= operator, and lack of explicit boxing make the interpreter visually cleaner while carrying the same categorical structure.

Full Source

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

(* Grand synthesis: a mini functional system combining:
   - Type-safe DSL (tagless final)
   - Monadic error handling
   - Functors and natural transformations
   - CPS and trampolining
   The goal: a validated data pipeline with logging *)

(* Validation applicative *)
type ('a, 'e) validated =
  | Valid   of 'a
  | Invalid of 'e list

let valid x    = Valid x
let invalid e  = Invalid [e]

let map_v f = function
  | Valid x     -> Valid (f x)
  | Invalid es  -> Invalid es

let apply_v f_v x_v = match f_v, x_v with
  | Valid f, Valid x             -> Valid (f x)
  | Invalid e, Valid _           -> Invalid e
  | Valid _, Invalid e           -> Invalid e
  | Invalid e1, Invalid e2       -> Invalid (e1 @ e2)

(* Validated pipeline for a user record *)
type user = { name: string; age: int; email: string }

let validate_name s =
  if String.length s >= 2 then valid s
  else invalid "name too short (min 2 chars)"

let validate_age n =
  if n >= 0 && n < 150 then valid n
  else invalid (Printf.sprintf "age %d out of range" n)

let validate_email s =
  if String.contains s '@' then valid s
  else invalid "email missing @"

let make_user name age email = { name; age; email }

let validate_user name age email =
  apply_v
    (apply_v (map_v make_user (validate_name name))
             (validate_age age))
    (validate_email email)

(* CPS logger *)
let with_log label f x k =
  let result = f x in
  k (Printf.sprintf "[%s] %s -> " label x) result

let () =
  (* Valid user *)
  (match validate_user "Alice" 30 "alice@example.com" with
   | Valid u    -> Printf.printf "Valid user: %s, %d, %s\n" u.name u.age u.email
   | Invalid es -> Printf.printf "Errors: %s\n" (String.concat "; " es));

  (* Multiple validation errors accumulate *)
  (match validate_user "A" 200 "bad-email" with
   | Valid _    -> assert false
   | Invalid es ->
     Printf.printf "Errors (%d):\n" (List.length es);
     List.iter (Printf.printf "  - %s\n") es);

  Printf.printf "\nGrand synthesis: FP patterns compose.\n"

Deep Comparison

OCaml vs Rust: Grand Synthesis

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

Extend the interpreter with recursive let (letrec) using a Rc<RefCell<Option<Value>>> thunk for self-reference.

Add a type inference pass as a separate catamorphism that annotates the AST with Type using the Cofree pattern.

Replace the free monad effect system with an algebraic effect handler that supports resumable exceptions (use the delimited continuation pattern from example 196).

Add lenses for all fields of InterpreterState and compose them to build a transaction-style update that rolls back on error.

Implement a pretty-printer for the AST using an anamorphism (unfold) into a document algebra, then render via a second catamorphism over the document type.

Open Source Repos

functional-rust

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

Rust