Saltar al contenido ForoHackers

Type theory: start here

Teoría de tipos
#901 · Ophuscado · · Denunciar

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

  1. The untyped lambda calculus: write reduction and Church numerals by hand.
  2. Implement a type checker for the simply typed lambda calculus in a few dozen lines.
  3. Add polymorphism and type inference, and read how Hindley-Milner unification works.
  4. Prove progress and preservation for a tiny language on paper.
  5. Use a proof assistant with dependent types to prove a list function correct.

Related tags

#logic #functional-programming #haskell #formal-methods #language-design

Inicia sesión o únete para responder.