Typed lambda calculus

In mathematics and computer science, a typed lambda calculus is a typed formalism that uses the lambda symbol (

λ

{\displaystyle \lambda }

) to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered (see kinds below). From a certain point of view, typed lambda calculi can be seen as refinements of the untyped lambda calculus, but from another point of view, they can also be considered the more fundamental theory and untyped lambda calculus a special case with only one type.

Typed lambda calculi are foundational programming languages and are the base of typed functional programming languages such as ML and Haskell and, more indirectly, typed imperative programming languages. Typed lambda calculi play an important role in the design of type systems for programming languages; here, typability usually captures desirable properties of the program (e.g., the program will not cause a memory access violation).

Typed lambda calculi are closely related to mathematical logic and proof theory via the Curry–Howard isomorphism and they can be considered as the internal language of certain classes of categories. For example, the simply typed lambda calculus is the language of Cartesian closed categories (CCCs).

Kinds of typed lambda calculi

Various typed lambda calculi have been studied. The simply typed lambda calculus has only one type constructor, the arrow

→

{\displaystyle \to }

, and its only types are basic types and function types

σ

→

τ

{\displaystyle \sigma \to \tau }

. System T extends the simply typed lambda calculus with a type of natural numbers and higher-order primitive recursion; in this system all functions provably computable in Peano arithmetic are definable.