CurryHowardsambandet

The Curry-Howard correspondence, also known as the Curry-Howard isomorphism or the Curry-Howard-Lambek correspondence, is a foundational concept in logic and computer science that reveals a deep link between proofs and computer programs. It states that propositions correspond to types and proofs correspond to programs: a constructive proof of a proposition can be viewed as a program of the corresponding type, and the process of applying a proof to derive a result matches running a program.

Origin and scope: The relation was observed in the 1960s by Haskell Curry and independently by William Alvin Howard, who formulated the precise isomorphism between intuitionistic logic and the simply typed lambda calculus. The broader picture, tying logic, computation, and category theory, was developed with contributions from other researchers, including Joachim Lambek, leading to the Curry-Howard-Lambek perspective. The correspondence extends to richer type systems and logics, including polymorphism and dependent types, and it is a central idea in modern type theory.

Core mappings: In this framework, implication corresponds to function types, conjunction to product types, and disjunction to sum types. Propositions behave as types, and proofs as programs that inhabit those types. Normalization of proofs aligns with evaluation or execution of programs (beta-reduction in lambda calculus), establishing a tight link between logical correctness and computational behavior.

Applications: The correspondence informs the design of typed functional programming languages and proof assistants. It underpins language features in Haskell, ML, Coq, and Agda, enabling the extraction of executable code from constructive proofs and guiding the development of robust type systems and formal verification methods.