234 Expert

Propositions as Types

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Propositions as Types" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Extending the Curry-Howard correspondence, this example makes the type-as-proposition correspondence concrete with examples: conjunction (product types), disjunction (sum types), implication (function types), negation (function to `!`), and the universal and existential quantifiers (generic types and existential types). Key difference from OCaml: 1. **Existentials**: Rust's `Box<dyn Trait>` is a runtime existential; OCaml's first

Tutorial

The Problem

Extending the Curry-Howard correspondence, this example makes the type-as-proposition correspondence concrete with examples: conjunction (product types), disjunction (sum types), implication (function types), negation (function to !), and the universal and existential quantifiers (generic types and existential types). Seeing familiar type operations through the logical lens reveals why type system design and formal logic are the same discipline.

🎯 Learning Outcomes

• See conjunction, disjunction, implication, and negation as concrete Rust types

• Understand universal quantification as generic type parameters: ∀T. P(T) = fn<T>(...)

• Understand existential quantification as Box<dyn Trait> or impl Trait

• Connect these to everyday programming: Option = "maybe A", Result = "A or E"

Code Example

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

(* Propositions as types (PAT), also called BHK interpretation:
   - Proposition = Type
   - Proof = inhabitant (value)
   - Implication A -> B = function type
   - Conjunction A and B = product type A * B
   - Disjunction A or B = sum type A + B
   - True = unit, False = empty type *)

(* True: always provable — unit *)
let proof_of_true : unit = ()

(* Implication: A -> B — a function *)
let impl_proof : int -> string = string_of_int

(* Conjunction: A and B — a pair *)
let conj_proof : int * string = (42, "hello")
let elim_left  (a, _) = a
let elim_right (_, b) = b

(* Disjunction: A or B — Either *)
type ('a, 'b) either = Left of 'a | Right of 'b
let disj_left  a = Left  a
let disj_right b = Right b
let case f g = function Left a -> f a | Right b -> g b

(* Universal: forall a. P a — polymorphic function *)
let id_proof : 'a -> 'a = fun x -> x

(* De Morgan: not (A or B) -> not A and not B *)
let de_morgan f =
  (fun a -> f (Left a), fun b -> f (Right b))

let () =
  Printf.printf "True proved: %s\n" (if proof_of_true = () then "yes" else "no");
  Printf.printf "impl: %s\n" (impl_proof 42);
  Printf.printf "conj left: %d\n" (elim_left conj_proof);
  Printf.printf "disj case: %s\n" (case string_of_int (fun s -> s) (Left 42));
  Printf.printf "PAT: proofs are programs, propositions are types\n"

Key Differences

Existentials: Rust's Box<dyn Trait> is a runtime existential; OCaml's first-class modules and GADTs provide more expressive existentials.

Universal quantification: Rust's generics are explicit (fn<T>); OCaml's polymorphism is implicit (inferred by type inference) — both express ∀T.

Negation: Both use a function to an uninhabited type; Rust's ! is built-in, OCaml uses type void = |.

Proof relevance: Rust and OCaml are "proof-relevant" (the computation matters); systems like Coq are proof-irrelevant (only inhabitation matters).

OCaml Approach

OCaml's type algebra mirrors this directly. The type nonrec keyword and abstract types provide the tools. Coq (the proof assistant) was originally designed with OCaml-like syntax specifically because of the Curry-Howard correspondence — proof terms in Coq are OCaml-like programs.

Full Source

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

(* Propositions as types (PAT), also called BHK interpretation:
   - Proposition = Type
   - Proof = inhabitant (value)
   - Implication A -> B = function type
   - Conjunction A and B = product type A * B
   - Disjunction A or B = sum type A + B
   - True = unit, False = empty type *)

(* True: always provable — unit *)
let proof_of_true : unit = ()

(* Implication: A -> B — a function *)
let impl_proof : int -> string = string_of_int

(* Conjunction: A and B — a pair *)
let conj_proof : int * string = (42, "hello")
let elim_left  (a, _) = a
let elim_right (_, b) = b

(* Disjunction: A or B — Either *)
type ('a, 'b) either = Left of 'a | Right of 'b
let disj_left  a = Left  a
let disj_right b = Right b
let case f g = function Left a -> f a | Right b -> g b

(* Universal: forall a. P a — polymorphic function *)
let id_proof : 'a -> 'a = fun x -> x

(* De Morgan: not (A or B) -> not A and not B *)
let de_morgan f =
  (fun a -> f (Left a), fun b -> f (Right b))

let () =
  Printf.printf "True proved: %s\n" (if proof_of_true = () then "yes" else "no");
  Printf.printf "impl: %s\n" (impl_proof 42);
  Printf.printf "conj left: %d\n" (elim_left conj_proof);
  Printf.printf "disj case: %s\n" (case string_of_int (fun s -> s) (Left 42));
  Printf.printf "PAT: proofs are programs, propositions are types\n"

Deep Comparison

OCaml vs Rust: Propositions Types

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

Write double_negation_intro<A>(a: A) -> impl Fn(impl Fn(A) -> !) -> ! as a type-level proof.

Implement De Morgan: (A -> !) -> (B -> !) -> Either<A, B> -> ! — De Morgan's law as a Rust function.

Show why fn<A>(f: impl Fn(A) -> A) -> A is uninhabitable (no value of any type can be returned without an A to start with).

Open Source Repos

functional-rust

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

Rust