596 Expert

Church encoding rust

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Church encoding rust" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. This example explores advanced type theory concepts applied to Rust. Key difference from OCaml: 1. **HKT gap**: Haskell and partly OCaml have higher

Tutorial

The Problem

This example explores advanced type theory concepts applied to Rust. Church encoding, Scott encoding, finally tagless, free monads, and effect systems are all techniques from the typed lambda calculus and category theory research community. They demonstrate how to encode data and control as pure functions, how to build extensible DSLs without committing to a representation, and how to model effects as values rather than side effects. These patterns originate in Haskell and OCaml research and require adapting to Rust's ownership model.

🎯 Learning Outcomes

• The theoretical foundation of this encoding/pattern from type theory

• How it maps to Rust's type system using traits, generics, and higher-kinded type emulation

• The practical limitations and verbosity compared to Haskell/OCaml implementations

• When this pattern provides genuine value vs when simpler alternatives suffice

• Real systems that use these ideas: compilers, effect libraries, DSL frameworks

Code Example

fn church_true<T>() -> impl Fn(T, T) -> T { |a, _| a }
fn church_false<T>() -> impl Fn(T, T) -> T { |_, b| b }
fn to_bool(b: impl Fn(bool, bool) -> bool) -> bool { b(true, false) }

let church_true  a b = a
let church_false a b = b
let to_bool b = b true false

Key Differences

HKT gap: Haskell and partly OCaml have higher-kinded types; Rust uses GATs and trait tricks as approximations — significantly more verbose.

Type inference: OCaml's HM inference handles these patterns cleanly; Rust often requires explicit type annotations throughout.

Practical value: In Haskell, these patterns are common in production code; in Rust, simpler alternatives (enums + match) usually suffice.

Research to practice: These patterns showcase Rust's expressiveness limits and inspire ongoing language design work (GATs, async traits, HKT proposals).

OCaml Approach

OCaml is the natural home for these patterns — they originate in the ML/Haskell research community:

(* OCaml's polymorphism and first-class modules make these patterns
   more elegant than in Rust. Higher-kinded types are emulated in OCaml
   using functors and first-class modules rather than GATs. *)

Full Source

#![allow(clippy::all)]
//! # Church Encoding
//!
//! Represent data using only functions (lambda calculus style).

/// Church numeral type - a number is how many times you apply f.
pub type ChurchNum<T> = Box<dyn Fn(Box<dyn Fn(T) -> T>) -> Box<dyn Fn(T) -> T>>;

/// Church zero - apply f zero times.
pub fn zero<T: 'static>() -> impl Fn(Box<dyn Fn(T) -> T>) -> Box<dyn Fn(T) -> T> {
    |_f| Box::new(|x| x)
}

/// Church successor - apply f one more time.
pub fn succ<T: Clone + 'static>(
    n: impl Fn(Box<dyn Fn(T) -> T>) -> Box<dyn Fn(T) -> T> + 'static,
) -> impl Fn(Box<dyn Fn(T) -> T>) -> Box<dyn Fn(T) -> T> {
    move |f: Box<dyn Fn(T) -> T>| {
        let nf = n(Box::new(move |x| f(x)));
        Box::new(move |x| {
            let inner = nf(x);
            inner
        })
    }
}

/// Convert Church numeral to integer.
pub fn to_int(n: impl Fn(Box<dyn Fn(i32) -> i32>) -> Box<dyn Fn(i32) -> i32>) -> i32 {
    n(Box::new(|x| x + 1))(0)
}

/// Church boolean - true.
pub fn church_true<T>() -> impl Fn(T, T) -> T {
    |a, _b| a
}

/// Church boolean - false.
pub fn church_false<T>() -> impl Fn(T, T) -> T {
    |_a, b| b
}

/// Church boolean to Rust bool.
pub fn to_bool(b: impl Fn(bool, bool) -> bool) -> bool {
    b(true, false)
}

/// Church pair constructor.
pub fn pair<A: Clone + 'static, B: Clone + 'static>(
    a: A,
    b: B,
) -> impl Fn(Box<dyn Fn(A, B) -> A>) -> A + Clone {
    move |f| f(a.clone(), b.clone())
}

/// Church pair first.
pub fn fst<A: Clone, B>(p: impl Fn(Box<dyn Fn(A, B) -> A>) -> A) -> A {
    p(Box::new(|a, _b| a))
}

/// Simple demonstration with closures.
pub fn demo_church_bool() -> (bool, bool) {
    let t = church_true();
    let f = church_false();
    (to_bool(t), to_bool(f))
}

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

    #[test]
    fn test_church_bool() {
        assert!(to_bool(church_true()));
        assert!(!to_bool(church_false()));
    }

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

    #[test]
    fn test_demo() {
        let (t, f) = demo_church_bool();
        assert!(t);
        assert!(!f);
    }
}

(* Church encoding in OCaml *)

(* Church Booleans *)
let church_true  t _ = t
let church_false _ f = f
let church_not b = b church_false church_true
let church_and p q = p q church_false
let church_or  p q = p church_true q
let church_if c t f = c t f

(* Church Numerals *)
let zero f x = x
let succ n f x = f (n f x)
let church_add m n f x = m f (n f x)
let church_mul m n f = m (n f)
let to_int n = n (fun x -> x+1) 0

let one   = succ zero
let two   = succ one
let three = succ two

(* Church Pairs *)
let church_pair a b f = f a b
let church_fst p = p (fun a _ -> a)
let church_snd p = p (fun _ b -> b)

let () =
  Printf.printf "2+3 = %d\n" (to_int (church_add two three));
  Printf.printf "2*3 = %d\n" (to_int (church_mul two three));
  Printf.printf "T and F = %b\n" (church_if (church_and church_true church_false) true false);
  let p = church_pair 42 "hello" in
  Printf.printf "fst=%d snd=%s\n" (church_fst p) (church_snd p)

✓ Tests Rust test suite

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

    #[test]
    fn test_church_bool() {
        assert!(to_bool(church_true()));
        assert!(!to_bool(church_false()));
    }

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

    #[test]
    fn test_demo() {
        let (t, f) = demo_church_bool();
        assert!(t);
        assert!(!f);
    }
}

Deep Comparison

OCaml vs Rust: Church Encoding

Church encoding represents data purely with functions.

Church Booleans

OCaml

let church_true  a b = a
let church_false a b = b
let to_bool b = b true false

Rust

fn church_true<T>() -> impl Fn(T, T) -> T { |a, _| a }
fn church_false<T>() -> impl Fn(T, T) -> T { |_, b| b }
fn to_bool(b: impl Fn(bool, bool) -> bool) -> bool { b(true, false) }

Church Numerals

A number N is represented as "apply f N times":

• 0 = λf.λx.x

• 1 = λf.λx.f x

• 2 = λf.λx.f (f x)

Key Differences

Aspect	OCaml	Rust
Closures	Lightweight	Require explicit types
Higher-rank	Easy	Requires `impl Fn` or `dyn`
Boxing	GC handles	Manual `Box<dyn Fn>`

Exercises

Minimal implementation: Implement the simplest possible version of this pattern for a two-case example (e.g., for Church encoding, for finally tagless).

Add an interpreter: If the pattern supports multiple interpretations (like finally tagless), add a second interpreter (e.g., a pretty-printer in addition to an evaluator).

Comparison: Implement the same functionality using a plain enum + match — compare the code size, type safety, and extensibility of both approaches.

Open Source Repos

functional-rust

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

Rust