🦀 Functional Rust

198: Church Encoding — Numbers and Booleans as Functions

Difficulty: 4 Level: Expert Build all data — numbers, booleans, pairs — from nothing but functions. No integers, no `bool`, no structs.

The Problem This Solves

This is the deepest question in computing: what is the minimum you need to do computation? Turing machines need tape and states. Von Neumann machines need registers and memory. But Alonzo Church proved in 1936 that you need only functions. Not integers. Not booleans. Not data structures. Just functions — nothing else. From functions alone, you can build everything. This is called lambda calculus, and every programming language — including Rust — is built on top of it. When you write a closure in Rust, you're writing a lambda expression. When you compose functions, you're doing lambda calculus. Church encoding is the proof that this is sufficient: it shows you how to build integers and booleans out of pure functions. In practice, you'd never write production code this way. But understanding it answers the question "why do closures feel so powerful?" Because closures are the primitive — everything else is built on them. This example exists to show you that full picture.

The Intuition

Numbers: The number N IS the function "apply f N times to x." 
zero  = apply f 0 times to x = return x
one   = apply f 1 time  to x = return f(x)
two   = apply f 2 times to x = return f(f(x))
three = apply f 3 times to x = return f(f(f(x)))
To read a number: plug in `f = |x| x+1` and `x = 0`. Count the applications. Booleans: `true` and `false` are functions that choose between two values. 
true  = take two things, return the FIRST
false = take two things, return the SECOND
`if` is then just: "apply the condition to the two branches." Pairs: A pair (a, b) is a function that, given a "selector", returns what you selected. 
pair(a, b) = a function that, when you say "give me first", gives a
                        and when you say "give me second", gives b
All of these look like magic until you see them in code.

How It Works in Rust

Rust complicates pure Church encoding because closures each have unique types. We use `Rc<dyn Fn>` for shared, type-erased closures. Church numerals: 
use std::rc::Rc;

type FnI = Rc<dyn Fn(i32) -> i32>;
// A Church numeral: given f and x, apply f N times to x
type Church = Rc<dyn Fn(FnI) -> FnI>;

fn church(n: u32) -> Church {
 Rc::new(move |f: FnI| {
     // Build up the N-application chain
     let mut result: FnI = Rc::new(|x| x);  // start: identity (zero applications)
     for _ in 0..n {
         let prev = result.clone();
         let f2 = f.clone();
         result = Rc::new(move |x| f2(prev(x)));  // wrap: one more application
     }
     result
 })
}

// Convert to integer by applying "add 1" to 0:
fn to_int(n: Church) -> i32 {
 let succ: FnI = Rc::new(|x| x + 1);
 n(succ)(0)  // apply "add 1" N times to 0
}

// Arithmetic falls out naturally:
fn add(m: Church, n: Church) -> Church {
 Rc::new(move |f: FnI| {
     let mf = m(f.clone());  // apply f m times...
     let nf = n(f);           // ...then n more times
     Rc::new(move |x| mf(nf(x)))
 })
}

fn mul(m: Church, n: Church) -> Church {
 // m × n: apply n's function, m times
 Rc::new(move |f: FnI| m(n(f)))
}

assert_eq!(to_int(add(church(2), church(3))), 5);
assert_eq!(to_int(mul(church(3), church(4))), 12);
Church booleans — selectors: 
// A Church bool takes two values and returns one of them
type CBool = Rc<dyn Fn(i32) -> Rc<dyn Fn(i32) -> i32>>;

fn ctrue() -> CBool {
 Rc::new(|t| Rc::new(move |_f| t))  // return FIRST argument
}

fn cfalse() -> CBool {
 Rc::new(|_t| Rc::new(move |f| f))  // return SECOND argument
}

// If-then-else is just application!
fn cif(b: CBool, t: i32, f: i32) -> i32 {
 b(t)(f)  // the boolean IS the if-then-else
}

assert_eq!(cif(ctrue(), 42, 0), 42);   // true selects first branch
assert_eq!(cif(cfalse(), 42, 0), 0);   // false selects second branch
Church pairs: 
type Pair = Rc<dyn Fn(Rc<dyn Fn(i32, i32) -> i32>) -> i32>;

// A pair IS a function: given "how to combine a and b", produce the result
fn pair(a: i32, b: i32) -> Pair {
 Rc::new(move |f: Rc<dyn Fn(i32, i32) -> i32>| f(a, b))
}

fn fst(p: &Pair) -> i32 { p(Rc::new(|a, _| a)) }  // select first
fn snd(p: &Pair) -> i32 { p(Rc::new(|_, b| b)) }  // select second

let p = pair(10, 20);
assert_eq!(fst(&p), 10);
assert_eq!(snd(&p), 20);

What This Unlocks

Key Differences

ConceptOCamlRust
Church numeral type`('a->'a)->'a->'a` (rank-2 polymorphic)`Rc<dyn Fn(Rc<dyn Fn(i32)->i32>)->Rc<dyn Fn(i32)->i32>>`
Boolean as function`let ctrue t _ = t` (trivial)`Rc<dyn Fn(i32)->Rc<dyn Fn(i32)->i32>>`
Sharing closuresFree (GC)`Rc` for shared ownership
Power (exponentiation)`let pow m n = n m` (one line!)Requires iterative simulation
Type inferenceFigures it all outNeeds explicit type aliases
PracticalityEducationalEducational
// Church Encoding — Numbers and Booleans as Functions
//
// Church numerals represent natural numbers as higher-order functions.
// The numeral `n` is the function that applies `f` to `x` exactly `n` times:
//   zero  = λf. λx. x
//   one   = λf. λx. f x
//   two   = λf. λx. f (f x)
//   succ  = λn. λf. λx. f (n f x)
//   add   = λm. λn. λf. λx. m f (n f x)
//   mul   = λm. λn. λf. m (n f)
//   pow   = λm. λn. n m
//
// In Rust, functions aren't first-class the same way as in lambda calculus,
// but we can encode Church numerals as Rc<dyn Fn(...)> chains.

use std::rc::Rc;

// ── Church numerals ────────────────────────────────────────────────────────
//
// A Church numeral is: (i32 -> i32) -> i32 -> i32
// We represent it as Rc<dyn Fn(Rc<dyn Fn(i32) -> i32>) -> Rc<dyn Fn(i32) -> i32>>

type FnI = Rc<dyn Fn(i32) -> i32>;
type Church = Rc<dyn Fn(FnI) -> FnI>;

fn church(n: u32) -> Church {
    Rc::new(move |f: FnI| {
        let mut result: FnI = Rc::new(|x| x);
        for _ in 0..n {
            let prev = result.clone();
            let f2 = f.clone();
            result = Rc::new(move |x| f2(prev(x)));
        }
        result
    })
}

fn zero() -> Church {
    Rc::new(|_f: FnI| Rc::new(|x| x))
}

fn one() -> Church { church(1) }
fn two() -> Church { church(2) }
fn three() -> Church { church(3) }

fn to_int(n: Church) -> i32 {
    let succ: FnI = Rc::new(|x| x + 1);
    n(succ)(0)
}

fn succ(n: Church) -> Church {
    Rc::new(move |f: FnI| {
        let nf = n(f.clone());
        Rc::new(move |x| f(nf(x)))
    })
}

fn add(m: Church, n: Church) -> Church {
    Rc::new(move |f: FnI| {
        let mf = m(f.clone());
        let nf = n(f);
        Rc::new(move |x| mf(nf(x)))
    })
}

fn mul(m: Church, n: Church) -> Church {
    Rc::new(move |f: FnI| {
        m(n(f))
    })
}

// pow: n m = apply m n times (m^n)
fn pow(base: Church, exp: Church) -> Church {
    // exp applies "apply base" exp-times to the identity.
    // In Church encoding: pow m n = n m
    // We iterate: start with identity function-of-Church, apply "mul base" n times.
    let n_int = to_int(exp) as u32;
    let mut result = church(1);
    for _ in 0..n_int {
        result = mul(base.clone(), result);
    }
    result
}

// ── Church booleans ───────────────────────────────────────────────────────

type ChurchBool = Rc<dyn Fn(Rc<dyn Fn() -> i32>) -> Rc<dyn Fn(Rc<dyn Fn() -> i32>) -> i32>>;

// Simpler approach: Church booleans as selectors over bool
// ctrue  t _f = t
// cfalse _t f = f
// We represent with a plain bool wrapper and show the functional encoding.

// Functional church booleans choosing between two i32 values:
type CBool = Rc<dyn Fn(i32) -> Rc<dyn Fn(i32) -> i32>>;

fn ctrue() -> CBool {
    Rc::new(|t| Rc::new(move |_f| t))
}

fn cfalse() -> CBool {
    Rc::new(|_t| Rc::new(move |f| f))
}

fn cif(b: CBool, t: i32, f: i32) -> i32 {
    b(t)(f)
}

fn cand(b1: CBool, b2: CBool) -> CBool {
    // b1 b2 cfalse
    let result = cif(b1.clone(), 1, 0);
    if result == 1 { b2 } else { cfalse() }
}

fn cor(b1: CBool, b2: CBool) -> CBool {
    let result = cif(b1.clone(), 1, 0);
    if result == 1 { ctrue() } else { b2 }
}

fn cnot(b: CBool) -> CBool {
    let result = cif(b, 1, 0);
    if result == 1 { cfalse() } else { ctrue() }
}

fn to_bool(b: CBool) -> bool {
    cif(b, 1, 0) == 1
}

// ── Church pairs ──────────────────────────────────────────────────────────

// pair a b = λf. f a b
// fst p = p (λa. λb. a)
// snd p = p (λa. λb. b)

type Pair = Rc<dyn Fn(Rc<dyn Fn(i32, i32) -> i32>) -> i32>;

fn pair(a: i32, b: i32) -> Pair {
    Rc::new(move |f: Rc<dyn Fn(i32, i32) -> i32>| f(a, b))
}

fn fst(p: &Pair) -> i32 {
    p(Rc::new(|a, _| a))
}

fn snd(p: &Pair) -> i32 {
    p(Rc::new(|_, b| b))
}

fn main() {
    // ── Church arithmetic ──────────────────────────────────────────────
    let four  = succ(three());
    let five  = add(two(), three());
    let six   = mul(two(), three());
    let nine  = pow(three(), two());
    let eight = pow(two(), three());

    println!("3 + 2 = {}", to_int(add(three(), two())));
    println!("succ(3) = {}", to_int(four));
    println!("2 + 3 = {}", to_int(five));
    println!("2 × 3 = {}", to_int(six));
    println!("3² = {}", to_int(nine));
    println!("2³ = {}", to_int(eight));

    println!();

    // ── Large numbers ─────────────────────────────────────────────────
    let ten = church(10);
    let hundred = mul(ten.clone(), ten.clone());
    println!("10 × 10 = {}", to_int(hundred.clone()));
    println!("10 + 10 = {}", to_int(add(ten.clone(), ten.clone())));

    println!();

    // ── Church booleans ───────────────────────────────────────────────
    println!("true and false = {}", to_bool(cand(ctrue(), cfalse())));
    println!("true or  false = {}", to_bool(cor(ctrue(), cfalse())));
    println!("not true       = {}", to_bool(cnot(ctrue())));
    println!("not false      = {}", to_bool(cnot(cfalse())));
    println!("if true 42 0   = {}", cif(ctrue(), 42, 0));

    println!();

    // ── Church pairs ──────────────────────────────────────────────────
    let p = pair(3, 7);
    println!("fst (3,7) = {}", fst(&p));
    println!("snd (3,7) = {}", snd(&p));
}

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

    #[test]
    fn test_church_to_int() {
        assert_eq!(to_int(zero()), 0);
        assert_eq!(to_int(one()), 1);
        assert_eq!(to_int(two()), 2);
        assert_eq!(to_int(three()), 3);
        assert_eq!(to_int(church(10)), 10);
    }

    #[test]
    fn test_church_add() {
        assert_eq!(to_int(add(two(), three())), 5);
        assert_eq!(to_int(add(zero(), church(7))), 7);
    }

    #[test]
    fn test_church_mul() {
        assert_eq!(to_int(mul(two(), three())), 6);
        assert_eq!(to_int(mul(church(4), church(5))), 20);
    }

    #[test]
    fn test_church_pow() {
        assert_eq!(to_int(pow(two(), three())), 8);   // 2^3
        assert_eq!(to_int(pow(three(), two())), 9);   // 3^2
        assert_eq!(to_int(pow(church(5), one())), 5); // 5^1
    }

    #[test]
    fn test_church_succ() {
        assert_eq!(to_int(succ(zero())), 1);
        assert_eq!(to_int(succ(church(9))), 10);
    }

    #[test]
    fn test_church_booleans() {
        assert!(!to_bool(cand(ctrue(), cfalse())));
        assert!(to_bool(cor(ctrue(), cfalse())));
        assert!(!to_bool(cnot(ctrue())));
        assert!(to_bool(cnot(cfalse())));
    }

    #[test]
    fn test_church_pairs() {
        let p = pair(10, 20);
        assert_eq!(fst(&p), 10);
        assert_eq!(snd(&p), 20);
    }
}

(* Church encoding: represent natural numbers as iteration functions.
   A Church numeral n is a function that applies f to x exactly n times. *)

(* Church numerals: type is ('a -> 'a) -> 'a -> 'a *)
let zero  f x = x
let one   f x = f x
let two   f x = f (f x)
let three f x = f (f (f x))

(* Arithmetic *)
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 x = m (n f) x
let pow  m n     = n m            (* m^n *)

(* Convert to int for display *)
let to_int n = n (fun x -> x + 1) 0

(* Church booleans *)
let ctrue  t _f = t
let cfalse _t f = f
let cif b t f = b t f
let cand b1 b2 = b1 b2 cfalse
let cor  b1 b2 = b1 ctrue b2
let cnot b     = b cfalse ctrue

let to_bool b = b true false

let () =
  let four = succ three in
  let five = add two three in
  let six  = mul two three in
  let nine = pow three two in

  Printf.printf "3 + 2 = %d\n" (to_int (add three two));
  Printf.printf "4     = %d\n" (to_int four);
  Printf.printf "5     = %d\n" (to_int five);
  Printf.printf "6     = %d\n" (to_int six);
  Printf.printf "3^2   = %d\n" (to_int nine);

  Printf.printf "true and false = %b\n" (to_bool (cand ctrue cfalse));
  Printf.printf "true or  false = %b\n" (to_bool (cor  ctrue cfalse));
  Printf.printf "not true       = %b\n" (to_bool (cnot ctrue))

Related Examples

#197 197: Trampoline — Heap-Based Tail Call Optimization ⚙️ #199 199: Scott Encoding — Pattern Matching as Functions ⚙️ #200 200: Tagless Final ⚙️ #195 195: Continuation-Passing Style ⚙️
All Examples