Type theory studies systems that sort values into types so that meaningless programs are rejected before they run. It began as a foundation for mathematics and became the theory behind typed languages and proof assistants. Its central idea is that a program and a proof are the same kind of object.
Key concepts
- Simply typed lambda calculus: the smallest typed language, where every well-typed term terminates.
- Polymorphism: one definition that works for many types, through parametric generics or type classes.
- Algebraic data types: sums and products that build structured data and make pattern matching checkable.
- Curry-Howard correspondence: types are propositions, programs are proofs, and running a program simplifies a proof.
- Dependent types: types that mention values, such as vectors of length n, so more properties are checked statically.
Vocabulary
- Type judgement: a statement that a term has a type in a context, written with a turnstile.
- Type safety: well-typed programs do not get stuck, proved by progress and preservation.
- Type inference: the compiler works out the types you left out.
- Subtyping: a type can stand in where another is expected, as a more specific one.
What to study, in order
- The untyped lambda calculus: write reduction and Church numerals by hand.
- Implement a type checker for the simply typed lambda calculus in a few dozen lines.
- Add polymorphism and type inference, and read how Hindley-Milner unification works.
- Prove progress and preservation for a tiny language on paper.
- Use a proof assistant with dependent types to prove a list function correct.
Related tags
#logic #functional-programming #haskell #formal-methods #language-design