CurryHoward

Curry-Howard, or the Curry-Howard correspondence, is a fundamental insight in logic and computer science that identifies a deep correspondence between constructive logic and type theory, and hence between proofs and computer programs. Propositions correspond to types, and proofs correspond to programs. A constructive proof of a proposition A is interpreted as a program of type A; conversely a program of type A can be viewed as a proof of A. The normalization or evaluation of a program corresponds to simplification of a proof (cut-elimination).

The correspondence originated independently in the work around the late 1960s by Haskell Curry and by Robert F. Howard. The name Curry-Howard-Lambek reflects later generalizations by Joachim Lambek linking it to category theory.

In its simplest form, the correspondence matches the simply typed lambda calculus with intuitionistic propositional logic. Function types A -> B correspond to implications A => B in logic; product types A × B correspond to conjunction A ∧ B; unit type corresponds to truth; empty type corresponds to false. Extensions to include sums, polymorphism (System F), or dependent types yield correspondences with richer logics: intuitionistic higher-order logic, and the Calculus of Constructions. The Curry-Howard isomorphism also underpins the connections to category theory: cartesian closed categories capture simply typed lambda calculus, and the internal logic of a topos corresponds to a higher-level logic of types.

Applications include proof assistants and programming languages with strong static guarantees, such as Coq, Agda, and Haskell-inspired type systems, where proofs can be extracted as executable programs.