Skip to the content ForoHackers
Log inJoin

Type theory: start here

Type theory
#3407 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply