Type theory

Type theory is a formal system that classifies expressions by type and specifies how they can be formed, combined, and used. Its systems underpin constructive mathematics and many programming languages.

Type: A classification that determines which expressions are well-formed and how they may be used in a formal system. Types classify expressions and constrain the operations permitted on them.
Type inference: The process of determining the types of expressions from a program or formal derivation. It automates finding types that satisfy a type theory's rules.
Bertrand Russell: A British philosopher and logician who developed a theory of types to address paradoxes in set theory. His hierarchy of types shaped early logical type theory.
Curry–Howard–Lambek correspondence: A correspondence linking type theory, intuitionistic logic, and category theory. It connects type-theoretic proofs and programs to categorical structure.
Set theory: The mathematical study of sets and the formal systems used to describe their properties and relations. Set theory builds foundations from membership, whereas type theory organizes objects by types.
Term: A syntactic expression that denotes an object or computation in a formal language. Terms are the expressions that receive types in a type theory.
Type checking: The process of deciding whether an expression has a specified type under a set of rules. It verifies that expressions obey a type theory's typing judgments.
Alonzo Church: An American logician who developed the lambda calculus and influential systems of typed formal logic. His work established foundational typed calculi for logic and computation.
Coq: An interactive proof assistant based on the calculus of inductive constructions. Coq uses dependent type theory to check programs and mathematical proofs.
Untyped lambda calculus: A formal system of computation in which expressions have no assigned types. It permits applications that typed calculi rule out as ill-typed.

Linked from 35 pages