Types and Programming Languages | The Curry-Howard Correspondence (propositions as types analogy)
The type constructor comes with typing rules of two kinds:
-
- an "introduction rule (T-ABS)" describing how elements of the type can be created
-
- an "elimination rule (T-APP)" describes how elements of the type can be used
The introduction/elimination terminology arises from a connection between type theory and logic known as the Curry-Howard Correspondence. The idea is that, in constructive logics, a proof of a proposition consists of concrete evidence for P.
- For example, a proof of a proposition can be viewed as a mechanical procedure that, given a proof of , constructs a proof of - or, if you like, a proof of abstracted on a proof of