Saltar al contenido ForoHackers

Type theory: start here

Teoría de tipos
#3407 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder