What are the two types of type theory?

The two influential types of type theory, which have been proposed as foundations, are the Typed λ-calculus and Intuitionistic type theory.

Types of Type Theories

Type theory is a branch of mathematical logic that provides a framework for reasoning about types and their associated values. It is used extensively in computer science, particularly in programming languages, to ensure that programs are well-behaved and to prevent errors. Two foundational type theories are detailed below:

Typed λ-calculus

The Typed λ-calculus, developed by Alonzo Church, is a formal system that extends the untyped λ-calculus by introducing types. It provides a way to classify terms into categories based on their usage. The key idea is that every term has a type, and the rules of the system prevent terms from being used incorrectly with incompatible types. Here are some of its features:

• Basic Types: Typically includes base types like integers or booleans.
• Function Types: Uses a notation like τ → σ, where τ and σ are types, to denote functions that take an argument of type τ and return a value of type σ.
• Type Checking: A system of rules for ensuring that terms are used consistently.
• Strong Normalization: In the simply typed lambda calculus, all computations will eventually halt.

The Typed λ-calculus forms the basis for functional programming languages. For example, a function that adds two integers might be expressed as plus : int → int → int, indicating it takes an integer and another integer, and returns an integer.

Intuitionistic Type Theory

The Intuitionistic type theory developed by Per Martin-Löf is a more powerful and expressive type theory than the Typed λ-calculus. It's based on intuitionistic logic, which is a variant of logic where only constructive proofs are accepted. In this framework, proving the existence of an object requires one to provide a method for its construction.

Key Features of Intuitionistic Type Theory includes:

• Propositions as Types: Intuitionistic Type Theory uses the Curry-Howard correspondence, which equates propositions with types. Specifically, a proof of proposition P is identified with a term of type P.
• Dependent Types: Types can depend on values. For instance, a type for arrays can depend on the length of the array.
• Universes: Uses hierarchies of types (or universes) to avoid paradoxes, and type of type.
• Constructive Reasoning: Proofs are explicit constructions, making it ideal for representing programs and specifications in a rigorous way.

Martin-Löf's theory is widely used in proof assistants and formal verification. For example, a dependent type Vec n T might represent a vector of length n containing elements of type T.

Summary Table

Type Theory	Developer	Core Concept	Key Feature	Primary Use Case
Typed λ-calculus	Alonzo Church	Typing of terms to prevent misapplication	Function types, type checking, strong normalization	Foundation for functional programming languages
Intuitionistic Type Theory	Per Martin-Löf	Propositions as types, proofs as terms	Dependent types, universes, constructive reasoning	Formal verification, proof assistants