934 Expert

934-church-numerals — Church Numerals

Functional Programming

Tutorial

The Problem

Church numerals are a demonstration that numbers and arithmetic can be encoded purely as functions — no integers required. Introduced by Alonzo Church as part of lambda calculus (1930s), a Church numeral N is a function that applies another function N times: zero = λf.λx. x, one = λf.λx. f x, two = λf.λx. f(f x). Successor, addition, and multiplication can all be defined in terms of function composition. This example is primarily educational, illustrating lambda calculus encoding in a typed language. It reveals why Rust requires Rc for shared closures and Box<dyn Fn> for type erasure.

🎯 Learning Outcomes

• Understand Church numerals as function-encoded natural numbers

• Use Box<dyn Fn> for heap-allocated first-class functions

• Use Rc to share a closure across multiple calls without Clone

• Understand why OCaml represents Church numerals more naturally than Rust

• Recognize the connection between Church numerals and higher-order functions

Code Example

#![allow(clippy::all)]
/// # Church Numerals — Functions as Numbers
///
/// Lambda calculus encoding of natural numbers using higher-order functions.
/// A Church numeral N is a function that applies `f` N times to `x`.
///
/// In Rust, we use `Box<dyn Fn>` for heap-allocated closures since
/// Rust closures have unique unnameable types (unlike OCaml's uniform representation).

/// Type alias for Church numerals: takes a function and a value, applies f n times.
type Church = Box<dyn Fn(Box<dyn Fn(i64) -> i64>) -> Box<dyn Fn(i64) -> i64>>;

/// Zero: apply f zero times (return x unchanged)
pub fn zero() -> Church {
    Box::new(|_f| Box::new(|x| x))
}

/// One: apply f once
pub fn one() -> Church {
    Box::new(|f| Box::new(move |x| f(x)))
}

/// Successor: given n, apply f one more time
pub fn succ(n: Church) -> Church {
    Box::new(move |f: Box<dyn Fn(i64) -> i64>| {
        // We need to share f between n and the extra application
        // This is tricky in Rust due to ownership — use Rc
        use std::rc::Rc;
        let f = Rc::new(f);
        let f2 = f.clone();
        let inner = n(Box::new(move |x| f2(x)));
        let f3 = f.clone();
        Box::new(move |x| f3(inner(x)))
    })
}

/// Add: m + n = apply f m times, then n times
pub fn add(m: Church, n: Church) -> Church {
    Box::new(move |f: Box<dyn Fn(i64) -> i64>| {
        use std::rc::Rc;
        let f = Rc::new(f);
        let f2 = f.clone();
        let inner_m = m(Box::new(move |x| f(x)));
        let inner_n = n(Box::new(move |x| f2(x)));
        Box::new(move |x| inner_m(inner_n(x)))
    })
}

/// Convert Church numeral to integer
pub fn to_int(n: Church) -> i64 {
    let f: Box<dyn Fn(i64) -> i64> = Box::new(|x| x + 1);
    n(f)(0)
}

/// A simpler approach using a concrete recursive type instead of closures
#[derive(Clone, Debug)]
pub enum ChurchNum {
    Zero,
    Succ(Box<ChurchNum>),
}

impl ChurchNum {
    pub fn to_int(&self) -> i64 {
        match self {
            ChurchNum::Zero => 0,
            ChurchNum::Succ(n) => 1 + n.to_int(),
        }
    }

    pub fn from_int(n: i64) -> Self {
        if n <= 0 {
            ChurchNum::Zero
        } else {
            ChurchNum::Succ(Box::new(ChurchNum::from_int(n - 1)))
        }
    }

    pub fn add(self, other: Self) -> Self {
        match self {
            ChurchNum::Zero => other,
            ChurchNum::Succ(n) => ChurchNum::Succ(Box::new(n.add(other))),
        }
    }
}

#[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_succ() {
        assert_eq!(to_int(succ(zero())), 1);
        assert_eq!(to_int(succ(one())), 2);
    }

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

    #[test]
    fn test_church_num_adt() {
        let three = ChurchNum::from_int(3);
        let four = ChurchNum::from_int(4);
        assert_eq!(three.add(four).to_int(), 7);
    }

    #[test]
    fn test_church_num_zero() {
        assert_eq!(ChurchNum::Zero.to_int(), 0);
    }
}

(* Church Numerals — Functions as Numbers *)
(* Lambda calculus: a numeral N applies f N times to x *)

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);
  assert (to_int zero = 0);
  assert (to_int three = 3);
  assert (to_int six = 6);
  assert (to_int nine = 9);
  Printf.printf "All Church numeral tests passed!\n"

Key Differences

Type erasure need: Rust requires Box<dyn Fn> because each closure has a unique type; OCaml's uniform heap representation handles any closure as ('a -> 'b).

Sharing with Rc: Rust needs Rc to share f between multiple applications in succ; OCaml closures are implicitly shared.

Rank-2 polymorphism: OCaml can express church = { apply: 'a. ('a -> 'a) -> 'a -> 'a } directly; Rust cannot express rank-2 types without workarounds.

Practical utility: Church numerals are academic in both languages — the takeaway is understanding higher-order functions and type system limits.

OCaml Approach

OCaml's uniform function representation makes Church numerals straightforward: type church = { apply: 'a. ('a -> 'a) -> 'a -> 'a }. let zero = { apply = fun _f x -> x }. let succ n = { apply = fun f x -> f (n.apply f x) }. let to_int n = n.apply (fun x -> x + 1) 0. OCaml's polymorphic 'a. ('a -> 'a) -> 'a -> 'a is a rank-2 polymorphic type — it works for any type 'a. Rust cannot express this without Box<dyn Fn> because closures have unique unnameable types.

Full Source

#![allow(clippy::all)]
/// # Church Numerals — Functions as Numbers
///
/// Lambda calculus encoding of natural numbers using higher-order functions.
/// A Church numeral N is a function that applies `f` N times to `x`.
///
/// In Rust, we use `Box<dyn Fn>` for heap-allocated closures since
/// Rust closures have unique unnameable types (unlike OCaml's uniform representation).

/// Type alias for Church numerals: takes a function and a value, applies f n times.
type Church = Box<dyn Fn(Box<dyn Fn(i64) -> i64>) -> Box<dyn Fn(i64) -> i64>>;

/// Zero: apply f zero times (return x unchanged)
pub fn zero() -> Church {
    Box::new(|_f| Box::new(|x| x))
}

/// One: apply f once
pub fn one() -> Church {
    Box::new(|f| Box::new(move |x| f(x)))
}

/// Successor: given n, apply f one more time
pub fn succ(n: Church) -> Church {
    Box::new(move |f: Box<dyn Fn(i64) -> i64>| {
        // We need to share f between n and the extra application
        // This is tricky in Rust due to ownership — use Rc
        use std::rc::Rc;
        let f = Rc::new(f);
        let f2 = f.clone();
        let inner = n(Box::new(move |x| f2(x)));
        let f3 = f.clone();
        Box::new(move |x| f3(inner(x)))
    })
}

/// Add: m + n = apply f m times, then n times
pub fn add(m: Church, n: Church) -> Church {
    Box::new(move |f: Box<dyn Fn(i64) -> i64>| {
        use std::rc::Rc;
        let f = Rc::new(f);
        let f2 = f.clone();
        let inner_m = m(Box::new(move |x| f(x)));
        let inner_n = n(Box::new(move |x| f2(x)));
        Box::new(move |x| inner_m(inner_n(x)))
    })
}

/// Convert Church numeral to integer
pub fn to_int(n: Church) -> i64 {
    let f: Box<dyn Fn(i64) -> i64> = Box::new(|x| x + 1);
    n(f)(0)
}

/// A simpler approach using a concrete recursive type instead of closures
#[derive(Clone, Debug)]
pub enum ChurchNum {
    Zero,
    Succ(Box<ChurchNum>),
}

impl ChurchNum {
    pub fn to_int(&self) -> i64 {
        match self {
            ChurchNum::Zero => 0,
            ChurchNum::Succ(n) => 1 + n.to_int(),
        }
    }

    pub fn from_int(n: i64) -> Self {
        if n <= 0 {
            ChurchNum::Zero
        } else {
            ChurchNum::Succ(Box::new(ChurchNum::from_int(n - 1)))
        }
    }

    pub fn add(self, other: Self) -> Self {
        match self {
            ChurchNum::Zero => other,
            ChurchNum::Succ(n) => ChurchNum::Succ(Box::new(n.add(other))),
        }
    }
}

#[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_succ() {
        assert_eq!(to_int(succ(zero())), 1);
        assert_eq!(to_int(succ(one())), 2);
    }

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

    #[test]
    fn test_church_num_adt() {
        let three = ChurchNum::from_int(3);
        let four = ChurchNum::from_int(4);
        assert_eq!(three.add(four).to_int(), 7);
    }

    #[test]
    fn test_church_num_zero() {
        assert_eq!(ChurchNum::Zero.to_int(), 0);
    }
}

(* Church Numerals — Functions as Numbers *)
(* Lambda calculus: a numeral N applies f N times to x *)

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);
  assert (to_int zero = 0);
  assert (to_int three = 3);
  assert (to_int six = 6);
  assert (to_int nine = 9);
  Printf.printf "All Church numeral tests passed!\n"

✓ 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_succ() {
        assert_eq!(to_int(succ(zero())), 1);
        assert_eq!(to_int(succ(one())), 2);
    }

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

    #[test]
    fn test_church_num_adt() {
        let three = ChurchNum::from_int(3);
        let four = ChurchNum::from_int(4);
        assert_eq!(three.add(four).to_int(), 7);
    }

    #[test]
    fn test_church_num_zero() {
        assert_eq!(ChurchNum::Zero.to_int(), 0);
    }
}

Deep Comparison

Church Numerals — OCaml vs Rust Comparison

Core Insight

Church numerals are the purest test of first-class function support. OCaml's uniform value representation makes them trivially expressible — let zero _f x = x is all you need. Rust's ownership model creates significant friction: closures capture by move/borrow, have unique types, and can't be easily composed without Box<dyn Fn> and Rc.

OCaml Approach

Elegantly minimal. Functions are first-class values with uniform representation — all the same size on the heap. Composition (mul m n f = m (n f)) is just partial application. Type inference handles everything automatically. This is where ML languages truly shine.

Rust Approach

Two alternatives: (1) Box<dyn Fn> closures with Rc for shared ownership — works but verbose, allocates heavily, and fights the borrow checker. (2) An ADT-based ChurchNum enum (Zero | Succ) — more idiomatic Rust, explicit, and easier to reason about ownership. The ADT approach is essentially Peano numbers.

Comparison Table

Aspect	OCaml	Rust
Memory	GC'd closures (uniform)	`Box<dyn Fn>` + `Rc` (heap alloc each)
Null safety	N/A	N/A
Errors	N/A	Ownership errors at compile time
Iteration	Partial application	Must clone/Rc-share closures
Ergonomics	1-line definitions	10+ lines with type annotations

Things Rust Learners Should Notice

Closure types are unique — you can't name them, must use dyn Fn trait objects

**Rc for shared ownership** — when multiple closures need the same captured value

ADT alternative is more Rusty — Peano Zero | Succ(Box<N>) avoids closure complexity

This is where GC shines — OCaml's garbage collector makes higher-order functions effortless

Trade-off clarity — Rust makes the cost of abstraction visible; OCaml hides it

Exercises

Implement church_mult(m: Church, n: Church) -> Church that applies m times the application of f n times (composition).

Implement church_to_bool using Church booleans: true = λt.λf. t, false = λt.λf. f.

Write church_pred (predecessor function) — note this is significantly harder than successor due to the encoding constraints.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Church Numerals — OCaml vs Rust Comparison

Core Insight

OCaml Approach

Rust Approach

Comparison Table

Things Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos