233 Expert

Curry-Howard Correspondence

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Curry-Howard Correspondence" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. The Curry-Howard correspondence is the profound observation that propositions in logic correspond to types in programming, and proofs correspond to programs. Key difference from OCaml: 1. **Never type**: Rust's `!` is built into the language as "never/bottom"; OCaml uses an empty variant type `type void = |` — both represent the false proposition.

Tutorial

The Problem

The Curry-Howard correspondence is the profound observation that propositions in logic correspond to types in programming, and proofs correspond to programs. A function A -> B is a proof that "if A then B." A pair (A, B) is a proof of "A and B." A sum type Either<A, B> is a proof of "A or B." An impossible type (like fn() -> !) corresponds to a false proposition. Understanding this correspondence connects type system design to formal logic.

🎯 Learning Outcomes

• Understand the correspondence: types are propositions, values are proofs

• Learn how function types correspond to implications, product types to conjunctions, sum types to disjunctions

• See how Rust's ! (never) type corresponds to the proposition "false" (which has no proof)

• Appreciate how type-driven development and theorem proving are the same activity

Code Example

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

(* Curry-Howard: propositions are types, proofs are programs.
   A -> B corresponds to a function a -> b.
   A /\ B corresponds to a pair (a, b).
   A \/ B corresponds to a sum type (Left a | Right b). *)

(* Conjunction = product *)
type ('a, 'b) conj = And of 'a * 'b

let and_intro a b = And (a, b)
let and_elim_left  (And (a, _)) = a
let and_elim_right (And (_, b)) = b

(* Disjunction = sum *)
type ('a, 'b) disj = Left of 'a | Right of 'b

let or_intro_left  a = Left a
let or_intro_right b = Right b
let or_elim f g = function Left a -> f a | Right b -> g b

(* Implication = function *)
let modus_ponens f a = f a  (* A -> B, A |- B *)

(* Negation = A -> False (using unit as False placeholder) *)
type 'a neg = 'a -> unit

(* Double negation intro *)
let dne : 'a -> 'a neg neg = fun a k -> k a

let () =
  (* Proof: A /\ B -> B /\ A (and is commutative) *)
  let and_comm (And (a, b)) = And (b, a) in
  let proof = and_comm (And (1, "hello")) in
  Printf.printf "and_comm: (%s, %d)\n" (and_elim_left proof) (and_elim_right proof);

  (* Proof: A -> A (identity) *)
  let id_proof : 'a -> 'a = modus_ponens (fun x -> x) in
  Printf.printf "identity proof: %d\n" (id_proof 42);

  Printf.printf "Curry-Howard: types are propositions, functions are proofs\n"

Key Differences

Never type: Rust's ! is built into the language as "never/bottom"; OCaml uses an empty variant type type void = | — both represent the false proposition.

Dependent types: The full Curry-Howard correspondence requires dependent types (Coq, Agda, Idris); Rust and OCaml only partially implement it.

Proof relevance: In pure type theory, only whether a proof exists matters; in Rust/OCaml, the specific program matters too — proofs are computations.

Practical use: The correspondence guides API design: a function returning Option<T> is a proof that "maybe T"; Result<T, E> is proof of "T or E".

OCaml Approach

OCaml's type system supports the same correspondence:

let and_intro a b = (a, b)
let or_intro_left a = Either.Left a
let modus_ponens f a = f a
type void = |  (* no constructors — empty type, corresponds to False *)

OCaml's module system makes the correspondence explicit in type theory research tools (Coq, which started as a theorem prover for OCaml-like languages, directly implements this).

Full Source

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

(* Curry-Howard: propositions are types, proofs are programs.
   A -> B corresponds to a function a -> b.
   A /\ B corresponds to a pair (a, b).
   A \/ B corresponds to a sum type (Left a | Right b). *)

(* Conjunction = product *)
type ('a, 'b) conj = And of 'a * 'b

let and_intro a b = And (a, b)
let and_elim_left  (And (a, _)) = a
let and_elim_right (And (_, b)) = b

(* Disjunction = sum *)
type ('a, 'b) disj = Left of 'a | Right of 'b

let or_intro_left  a = Left a
let or_intro_right b = Right b
let or_elim f g = function Left a -> f a | Right b -> g b

(* Implication = function *)
let modus_ponens f a = f a  (* A -> B, A |- B *)

(* Negation = A -> False (using unit as False placeholder) *)
type 'a neg = 'a -> unit

(* Double negation intro *)
let dne : 'a -> 'a neg neg = fun a k -> k a

let () =
  (* Proof: A /\ B -> B /\ A (and is commutative) *)
  let and_comm (And (a, b)) = And (b, a) in
  let proof = and_comm (And (1, "hello")) in
  Printf.printf "and_comm: (%s, %d)\n" (and_elim_left proof) (and_elim_right proof);

  (* Proof: A -> A (identity) *)
  let id_proof : 'a -> 'a = modus_ponens (fun x -> x) in
  Printf.printf "identity proof: %d\n" (id_proof 42);

  Printf.printf "Curry-Howard: types are propositions, functions are proofs\n"

Deep Comparison

OCaml vs Rust: Curry Howard

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 the proof of (A → B) → (B → C) → A → C (function composition) as a Rust function.

Implement contraposition: (A -> B) -> (B -> Void) -> (A -> Void) — the contrapositive as a type-level proof.

Demonstrate that a function fn absurd<T>(n: !) -> T has no body to write — the ! type has no inhabitants.

Open Source Repos

functional-rust

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

Rust