[Advanced] — Propositions are types; proofs are programs. Not an analogy — an isomorphism, and the basis of every proof assistant.
The correspondence
A type is a proposition. A program of that type is a proof of it.
Discovered independently by Curry (1930s, combinatory logic) and Howard (1969, lambda calculus).
| Logic | Types |
|---|---|
| proposition | type |
| proof | program |
| (and) | (pair/tuple) |
| (or) | (sum/enum/Either) |
| (implies) | (function) |
| (true) | unit |
| (false) | the empty type (Void, !) |
| dependent function | |
| dependent pair | |
| proof simplification | program evaluation |
The reading that makes it click:
” implies ” means: give me evidence of and I’ll produce evidence of . That’s a function .
” and ” means: I have evidence of both. That’s a pair.
” or ” means: I have evidence of one, and I know which. That’s a tagged union.
Modus ponens — from and , conclude — is function application.
This is not a resemblance. The inference rules of natural deduction and the typing rules of the lambda calculus are the same rules. → Lambda Calculus
Proving by programming
To prove a proposition, write a program of that type.
proof :: a -> (b -> a)
proof x = \_ -> x -- constconst is a proof. If you have an , you can produce an from anything.
Distribution:
proof :: (a, b) -> a
proof = fstThe functions in your standard library are proofs of logical tautologies.
fst,snd,const,curry,uncurry,flip— each has a type that is a valid propositional formula, and the implementation is its proof.And the converse: if you cannot implement a total function of some type, that proposition is not provable. Try to write
a -> b. You can’t, because ” implies ” for arbitrary and is false.
Constructive logic
The correspondence is with intuitionistic logic, and the difference matters.
The law of the excluded middle — — is not provable.
Why: proving constructively means producing a tagged value — either Left a or Right b. To prove you’d need to decide, for arbitrary , which one holds. You can’t.
No total program has that type.
Similarly, double-negation elimination () fails. ((a -> Void) -> Void) -> a isn’t implementable.
The practical meaning: a constructive proof carries an algorithm. Prove “there exists an with property ” and you have produced an — the proof is the construction.
A classical proof by contradiction gives you existence with no witness. For mathematics that’s fine; for programming it’s useless, because you cannot run it. → Non-constructive proofs
Classical reasoning is recoverable — via continuations, remarkably. callcc has the type of Peirce’s law, , which is equivalent to the excluded middle. Control operators correspond to classical logic (Griffin, 1990), which is a genuinely startling connection between exception handling and proof theory.
Dependent types
Types depending on values — where the correspondence becomes usable for real mathematics.
Vec : Nat -> Type -> Type
append : Vec n a -> Vec m a -> Vec (n + m) a
head : Vec (S n) a -> a -- CANNOT be called on an empty vectorhead on an empty vector is a type error, not a runtime exception. The length is in the type.
And the quantifiers appear:
(dependent function) — . The return type depends on the argument’s value.
(dependent pair) — . A value together with a proof about it.
sorted : (xs : List Nat) -> (ys : List Nat ** (IsSorted ys, Permutation xs ys))That signature says: given a list, return a list together with proofs that it’s sorted and is a permutation of the input.
A function with that type cannot be wrong. Returning the empty list wouldn’t type-check. The specification is the type, and the compiler verifies it.
The costs are real: type checking becomes theorem proving (so inference is impossible and you write proofs by hand), proofs are often far longer than the code, and the ergonomics remain poor — which is why dependent types haven’t reached mainstream languages despite forty years.
Proof assistants
Where this is used in practice.
| System | Basis | Known for |
|---|---|---|
| Coq / Rocq | Calculus of Inductive Constructions | CompCert, four colour theorem |
| Lean 4 | dependent type theory | mathlib — and it’s also a real programming language |
| Agda | Martin-Löf type theory | dependently-typed programming |
| Idris | dependent types, pragmatic | practical DT programming |
| Isabelle/HOL | higher-order logic | seL4 |
Landmark results:
The four colour theorem — proved with computer assistance in 1976, and fully verified in Coq in 2005 by Gonthier, settling the doubts about the original.
The Feit–Thompson theorem — a 255-page group theory proof, verified in Coq (2012).
CompCert — a C compiler proven to preserve source semantics. Used in avionics, and a Csmith study found bugs in every mainstream compiler tested and none in CompCert’s verified core. → Semantics
seL4 — a microkernel with a machine-checked proof of functional correctness, plus proofs of confidentiality and integrity.
Lean’s mathlib is the notable current development: a community-built library of formalised mathematics, now over a million lines, with Fields Medallists actively involved. Terence Tao has formalised recent results in it. Formal verification is moving from “a curiosity” to “a tool working mathematicians use”, which was not true a decade ago.
What you can take from this
Being honest — you will probably never write a Coq proof. What transfers:
Types as specifications. Make illegal states unrepresentable — the design principle that comes straight from this correspondence.
enum State {
Disconnected,
Connecting { started: Instant },
Connected { session: SessionId },
}Versus three booleans and an optional session ID, where most combinations are invalid and every function must handle them. The enum makes the invalid states not exist, and the compiler enforces it.
Sum types are underused. Option/Result/Either are the logical disjunction, and languages without them force you to encode “or” as null, exceptions or sentinel values — all of which the type system can’t check. → Option and Result
The empty type has uses. Rust’s ! (never) types a function that doesn’t return; a Result<T, Infallible> says the error case is impossible. Void in a type means “this cannot happen”, checked.
Parametricity constrains behaviour. A more polymorphic signature is a stronger statement about what the function can do. → Theorems for free
Total functions are proofs; partial ones aren’t. A function that can throw, loop forever, or return null is not a proof of its type — which is precisely why proof assistants require totality.
The honest limits
Formal verification is expensive. seL4 took roughly 20 person-years for ~10,000 lines of C. That ratio is only justified where failure is catastrophic — kernels, crypto, avionics, medical devices.
A proof is only as good as its specification. Proving code matches a wrong spec proves nothing useful, and specifications are where the real thinking is.
The trusted computing base remains. You trust the proof checker, the axioms, and the hardware. Small, but not zero.
Extraction gaps. Coq extracts to OCaml, and the extraction itself is generally unverified.
Which is why the interesting direction isn’t full verification — it’s lightweight methods that get some of the benefit cheaply: refinement types checked by SMT (Liquid Haskell, F*), property-based testing, model checking, and richer type systems in ordinary languages. Rust’s borrow checker is the best current example: a substructural type system, from this lineage, that mainstream programmers use without knowing the theory. → Substructural Types
Related
- Type Systems Formally — soundness
- Logic — the other half of the correspondence
- Proof Techniques — constructive vs classical
- PL theory map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering