198 Expert

Church Encoding

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Church Encoding" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Church encoding represents data and operations as pure functions (lambdas). Key difference from OCaml: 1. **Type verbosity**: OCaml infers Church numeral types; Rust requires explicit `Box<dyn Fn(...)>` types that are hard to write.

Tutorial

The Problem

Church encoding represents data and operations as pure functions (lambdas). Church numerals encode natural numbers: zero is λf.λx.x, one is λf.λx.f x, two is λf.λx.f (f x). Booleans, pairs, and lists can all be encoded as functions. This demonstrates that the lambda calculus is computationally complete — data and control flow are the same thing. Understanding Church encoding illuminates the foundation of functional programming and type theory.

🎯 Learning Outcomes

• Understand Church encoding: representing data as higher-order functions

• Learn Church numerals, booleans, and pairs as function-based encodings

• See how arithmetic (successor, add, multiply) works on Church numerals

• Appreciate the theoretical foundation: types and proofs correspond (Curry-Howard, example 233)

Code Example

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

(* 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))

Key Differences

Type verbosity: OCaml infers Church numeral types; Rust requires explicit Box<dyn Fn(...)> types that are hard to write.

Performance: Church encoding is purely theoretical — computing 10 + 10 requires O(n) function applications; no practical use in performance-sensitive code.

Rank-2 types: Full Church encoding requires rank-2 types for polymorphic church numerals; both Rust and OCaml have limited rank-2 support (OCaml via record polymorphism, Rust via trait bounds).

Educational value: Church encoding demonstrates lambda calculus completeness; it is taught in CS theory courses regardless of practical utility.

OCaml Approach

OCaml's Church encoding is more concise:

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

OCaml's type inference handles the complex function types automatically. The encoding is idiomatic OCaml and is used in courses on the lambda calculus and type theory.

Full Source

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

(* 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))

Deep Comparison

OCaml vs Rust: Church Encoding

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

Implement Church pairs: pair = |x| |y| |f| f(x)(y), fst = |p| p(|x| |_| x), snd = |p| p(|_| |y| y).

Implement predecessor for Church numerals (this is famously tricky) using the pair encoding.

Open Source Repos

functional-rust

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

Rust