The Curry Howard Correspondence, also known as the proofs-as-programs correspondence, reveals a profound equivalence: programs are proofs, and types are propositions. It elegantly bridges the worlds of Logic and Computation, demonstrating how formal proofs directly correspond to functional programs. This deep insight underpins much of modern Type Theory.
In this correspondence, if a type T can be interpreted as a logical proposition, then a program of type T acts as a constructive proof for that proposition. For instance, a function that accepts an argument of type A and returns a value of type B can be seen as a proof of the implication A -> B. This mapping extends to connect various logical connectives (like conjunction, disjunction, implication) with type constructors (like product types, sum types, function types).
Originating from independent observations by Haskell Curry and William Alvin Howard, this principle is particularly strong in the context of Intuitionistic Logic, where proofs must be constructive. It has profoundly influenced the design of Programming Languages with strong Type Systems, such as those supporting Dependent Types, enabling the verification of program correctness directly through the type system.
