Skip to main content
Definition Website Computer and Technology

Lambda Calculus

Subject: Computer and Technology noun /ˈlæm.də ˌkæl.kjə.ləs/ 1 definition

  1. Definition (noun)

    Entry #261 · Updated

    Lambda 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) 21 into its typed lambda-calculus intermediate representation (GHC Core), applying β-reduction to substitute 21 for x before folding the result to 42. When simplifying (λx. λy. x + y) y, the optimizer first applies α-conversion to rename the inner bound parameter y to z—producing (λx. λz. x + z) y—so β-reduction yields λz. y + z without capturing the free argument y.