Lambda Calculus
Subject: Computer and Technology noun /ˈlæm.də ˌkæl.kjə.ləs/ 1 definition
- computer-science
- programming-languages
- functional-programming
- computability-theory
-
Definition (noun)
Entry #261 · UpdatedLambda Calculus (also written λ-calculus) is a formal system in mathematical logic and computer science, introduced by Alonzo Church in the 1930s, that models computation entirely through functions. Every expression in the language is constructed from just three syntactic primitives: variables, function abstractions (
λx. M) that bind a parameter within a body, and function applications (M N) that pass an argument to a function. Evaluation proceeds through term-rewriting rules—primarily α-conversion for collision-free variable renaming and β-reduction for substituting arguments into function bodies—until an irreducible normal form is reached or evaluation fails to terminate. Despite lacking built-in primitives for numbers, loops, or mutable state, untyped lambda calculus is Turing-complete and serves as the theoretical foundation for functional programming languages, compiler intermediate representations, and formal type systems.Common Forms
Untyped Lambda Calculus: The original Turing-complete formulation with no type constraints, permitting self-application and fixed-point combinators such as the Y combinator to express arbitrary recursion.
Simply Typed Lambda Calculus (STLC): Annotates parameters with static types (such as
A -> B) so every well-typed term is strongly normalizing and guaranteed to terminate, trading Turing completeness for type safety and decidable type checking.Polymorphic Lambda Calculus (System F): Extends the typed calculus with universal type quantification (
∀α. T), enabling generic functions that operate uniformly across arbitrary types and underpinning parametric polymorphism in ML, OCaml, and Haskell.Calculus of Constructions (CoC): Combines polymorphism with dependent types whose definitions can depend on terms and values, serving as the logical core of interactive proof assistants and theorem provers such as Rocq (formerly Coq) and Lean.
Example
During compilation, the Glasgow Haskell Compiler (
ghc) lowers source expressions such as(\x -> x * 2) 21into its typed lambda-calculus intermediate representation (GHC Core), applying β-reduction to substitute21forxbefore folding the result to42. When simplifying(λx. λy. x + y) y, the optimizer first applies α-conversion to rename the inner bound parameterytoz—producing(λx. λz. x + z) y—so β-reduction yieldsλz. y + zwithout capturing the free argumenty.