098 Expert

098 — Church Numerals

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "098 — Church Numerals" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Encode natural numbers as higher-order functions (Church numerals): zero applies `f` zero times, one applies once, `succ(n)` wraps `n` to apply one more time. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Encode natural numbers as higher-order functions (Church numerals): zero applies f zero times, one applies once, succ(n) wraps n to apply one more time. Implement to_int (apply +1 starting from 0) and arithmetic operations. Compare OCaml's naturally polymorphic Church encoding with Rust's Box<dyn Fn> approach.

🎯 Learning Outcomes

• Understand Church numerals as functions: n f x applies f to x exactly n times

• Use Box<dyn Fn(…) -> …> to represent higher-order functions as values in Rust

• Understand why Rust's ownership makes direct Church numeral composition difficult

• Implement to_int by applying |x| x + 1 to 0 via the Church numeral

• Compare Rust's Box<dyn Fn> verbosity with OCaml's terse polymorphic functions

• Recognise the ChurchNum(usize) practical encoding as a pragmatic alternative

Code Example

#[derive(Clone, Copy)]
pub struct ChurchNum(pub usize);

impl ChurchNum {
    pub fn succ(self) -> Self { ChurchNum(self.0 + 1) }
    pub fn add(self, other: Self) -> Self { ChurchNum(self.0 + other.0) }

    pub fn apply<T>(&self, f: impl Fn(T) -> T, x: T) -> T {
        (0..self.0).fold(x, |acc, _| f(acc))
    }
}

let zero _f x = x
let one f x = f x
let succ n f x = f (n f x)
let add m n f x = m f (n f x)
let mul m n f = m (n f)
let to_int n = n (fun x -> x + 1) 0

Key Differences

Aspect	Rust	OCaml
Type	`Box<dyn Fn(…) -> …>` (boxed)	`('a -> 'a) -> 'a -> 'a` (polymorphic)
`zero`	Multi-line with Box	`let zero _f x = x`
`succ`	Falls back to integer	`let succ n f x = f (n f x)`
`add`	Integer arithmetic	`let add m n f x = m f (n f x)`
Composition	Ownership prevents direct	Natural function application
Practical alt	`ChurchNum(usize)` struct	Not needed

Church numerals illustrate a fundamental limitation: Rust's ownership system and lack of rank-2 polymorphism make the "pure" lambda-calculus encoding awkward. OCaml's Hindley-Milner type inference with polymorphic functions is a natural fit.

OCaml Approach

OCaml Church numerals are trivial: let zero _f x = x and let succ n f x = f (n f x). The polymorphic type ('a -> 'a) -> 'a -> 'a is inferred automatically. add, mul, and exp are single-line definitions. This is one of the most striking comparisons between the two languages: OCaml's rank-2 polymorphism handles Church numerals directly; Rust's monomorphic closures require boxing.

Full Source

#![allow(clippy::all)]
//! # Church Numerals — Functions as Numbers
//!
//! Lambda calculus encoding where numbers are higher-order functions.
//! OCaml's polymorphic functions map to Rust's `Fn` trait objects or generics.

// ---------------------------------------------------------------------------
// Approach A: Using Box<dyn Fn> for Church numerals
// ---------------------------------------------------------------------------

/// A Church numeral: takes a function and a value, applies the function N times.
pub type Church = Box<dyn Fn(Box<dyn Fn(i64) -> i64>) -> Box<dyn Fn(i64) -> i64>>;

pub fn zero() -> Church {
    Box::new(|_f| Box::new(|x| x))
}

pub fn one() -> Church {
    Box::new(|f: Box<dyn Fn(i64) -> i64>| Box::new(move |x| f(x)))
}

pub fn succ(n: &dyn Fn(Box<dyn Fn(i64) -> i64>) -> Box<dyn Fn(i64) -> i64>) -> Church {
    // Can't easily compose due to ownership... see Approach B
    let result = to_int_inner(n) + 1;
    from_int(result as usize)
}

fn to_int_inner(n: &dyn Fn(Box<dyn Fn(i64) -> i64>) -> Box<dyn Fn(i64) -> i64>) -> i64 {
    let f = n(Box::new(|x| x + 1));
    f(0)
}

pub fn to_int(n: &Church) -> i64 {
    let f = n(Box::new(|x| x + 1));
    f(0)
}

pub fn from_int(n: usize) -> Church {
    Box::new(move |f: Box<dyn Fn(i64) -> i64>| {
        Box::new(move |x| {
            let mut result = x;
            for _ in 0..n {
                result = f(result);
            }
            result
        })
    })
}

// ---------------------------------------------------------------------------
// Approach B: Simple integer-backed (practical encoding)
// ---------------------------------------------------------------------------

/// Practical Church numeral — store the count, apply when needed.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct ChurchNum(pub usize);

impl ChurchNum {
    pub fn zero() -> Self {
        ChurchNum(0)
    }
    pub fn one() -> Self {
        ChurchNum(1)
    }
    pub fn succ(self) -> Self {
        ChurchNum(self.0 + 1)
    }
    pub fn add(self, other: Self) -> Self {
        ChurchNum(self.0 + other.0)
    }
    pub fn mul(self, other: Self) -> Self {
        ChurchNum(self.0 * other.0)
    }

    pub fn apply<T>(&self, f: impl Fn(T) -> T, x: T) -> T {
        let mut result = x;
        for _ in 0..self.0 {
            result = f(result);
        }
        result
    }

    pub fn to_int(&self) -> usize {
        self.apply(|x: usize| x + 1, 0)
    }
}

// ---------------------------------------------------------------------------
// Approach C: Generic function composition
// ---------------------------------------------------------------------------

pub fn church_apply<T>(n: usize, f: impl Fn(T) -> T, x: T) -> T {
    (0..n).fold(x, |acc, _| f(acc))
}

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

    #[test]
    fn test_zero() {
        assert_eq!(to_int(&zero()), 0);
    }

    #[test]
    fn test_one() {
        assert_eq!(to_int(&one()), 1);
    }

    #[test]
    fn test_from_int() {
        assert_eq!(to_int(&from_int(5)), 5);
    }

    #[test]
    fn test_church_num_basic() {
        let two = ChurchNum::one().succ();
        let three = ChurchNum::one().add(two);
        assert_eq!(three.to_int(), 3);
    }

    #[test]
    fn test_church_num_mul() {
        let two = ChurchNum(2);
        let three = ChurchNum(3);
        assert_eq!(two.mul(three).to_int(), 6);
    }

    #[test]
    fn test_church_apply() {
        assert_eq!(church_apply(3, |x: i32| x * 2, 1), 8); // 1 -> 2 -> 4 -> 8
    }

    #[test]
    fn test_church_apply_zero() {
        assert_eq!(church_apply(0, |x: i32| x + 1, 42), 42);
    }
}

let zero _f x = x
let one f x = f x
let succ n f x = f (n f x)
let add m n f x = m f (n f x)
let mul m n f = m (n f)
let to_int n = n (fun x -> x + 1) 0

let two = succ one
let three = add one two
let six = mul two three
let nine = mul three three

let () =
  Printf.printf "0=%d 1=%d 2=%d 3=%d 6=%d 9=%d\n"
    (to_int zero) (to_int one) (to_int two)
    (to_int three) (to_int six) (to_int nine)

✓ Tests Rust test suite

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

    #[test]
    fn test_zero() {
        assert_eq!(to_int(&zero()), 0);
    }

    #[test]
    fn test_one() {
        assert_eq!(to_int(&one()), 1);
    }

    #[test]
    fn test_from_int() {
        assert_eq!(to_int(&from_int(5)), 5);
    }

    #[test]
    fn test_church_num_basic() {
        let two = ChurchNum::one().succ();
        let three = ChurchNum::one().add(two);
        assert_eq!(three.to_int(), 3);
    }

    #[test]
    fn test_church_num_mul() {
        let two = ChurchNum(2);
        let three = ChurchNum(3);
        assert_eq!(two.mul(three).to_int(), 6);
    }

    #[test]
    fn test_church_apply() {
        assert_eq!(church_apply(3, |x: i32| x * 2, 1), 8); // 1 -> 2 -> 4 -> 8
    }

    #[test]
    fn test_church_apply_zero() {
        assert_eq!(church_apply(0, |x: i32| x + 1, 42), 42);
    }
}

Deep Comparison

Comparison: Church Numerals — OCaml vs Rust

Core Insight

Church numerals reveal a fundamental difference: OCaml's type system embraces higher-rank polymorphism naturally (let zero f x = x works for any f), while Rust's ownership model and monomorphized generics make pure Church encoding painful. Rust closures are concrete types, not abstract functions — each closure has a unique unnameable type, requiring Box<dyn Fn> for dynamic dispatch.

OCaml

let zero _f x = x
let one f x = f x
let succ n f x = f (n f x)
let add m n f x = m f (n f x)
let mul m n f = m (n f)
let to_int n = n (fun x -> x + 1) 0

Rust — Practical encoding

#[derive(Clone, Copy)]
pub struct ChurchNum(pub usize);

impl ChurchNum {
    pub fn succ(self) -> Self { ChurchNum(self.0 + 1) }
    pub fn add(self, other: Self) -> Self { ChurchNum(self.0 + other.0) }

    pub fn apply<T>(&self, f: impl Fn(T) -> T, x: T) -> T {
        (0..self.0).fold(x, |acc, _| f(acc))
    }
}

Comparison Table

Aspect	OCaml	Rust
Zero	`let zero _f x = x`	`Box::new(\\|_f\\| Box::new(\\|x\\| x))`
Type	Inferred polymorphic	`Box<dyn Fn(Box<dyn Fn>) -> Box<dyn Fn>>`
Composition	Natural function nesting	Ownership tangles
Practical alt	Not needed	`struct ChurchNum(usize)`
Performance	GC-managed closures	Heap alloc per `Box<dyn Fn>`
Elegance	⭐⭐⭐⭐⭐	⭐⭐ (pure) / ⭐⭐⭐⭐ (struct)

Learner Notes

• OCaml shines here: Lambda calculus is OCaml's home turf — the syntax is almost mathematical notation

• Rust's closure problem: Each closure is a unique type. Composing them requires trait objects (dyn Fn) and heap allocation

• **impl Fn vs dyn Fn**: impl Fn is zero-cost but monomorphic; dyn Fn is dynamic but allocates. Church numerals need the latter

• Practical encoding wins: In real Rust code, wrap the value in a struct and provide apply — same Church semantics, zero ceremony

• This is a language design lesson: Some abstractions are natural in some languages and awkward in others

Exercises

Implement church_add(m: &Church, n: &Church) -> Church using the integer-backed from_int(to_int(m) + to_int(n)) approach.

Implement church_mul similarly and verify church_mul(two, three) equals from_int(6).

Using the ChurchNum struct, implement Mul<ChurchNum> for ChurchNum using the std::ops::Mul trait.

In OCaml, implement exp m n = n m (Church exponentiation: m^n) and verify exp two three = to_int 8.

Research why Rust cannot express Church numerals directly (hint: requires rank-2 polymorphism or GATs) and write a brief explanation.

Open Source Repos

functional-rust

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

Rust