Lambda calculus

Lambda calculus is a formal system that expresses computation through function abstraction and application. Its simple rules provide a foundation for mathematical logic and programming-language theory.

Lambda abstraction: A lambda-calculus expression that defines a function by binding a variable in a body. Abstraction creates the functions that lambda calculus applies and evaluates.
Function (mathematics): A relation that assigns each input in a domain exactly one output. Lambda abstraction represents functions directly, without requiring named function symbols.
Alonzo Church: An American logician who developed lambda calculus and proved the undecidability of first-order logic. Church introduced the calculus in the 1930s as a formal account of functions and computation.
Functional programming: A programming paradigm that builds programs primarily from function application and composition. Its central operations and reasoning style draw directly on lambda-calculus ideas.
Untyped lambda calculus: Lambda calculus without a type discipline restricting which expressions may be formed or applied. It is the unrestricted setting in which self-application and nonterminating terms are possible.
Beta reduction: The computation rule that applies a function by substituting its argument for a bound variable. It is the central rule for reducing function applications to results.
Variable (mathematics): A symbol that stands for an element or value whose identity may depend on context. Variables are the symbols abstracted, applied, and substituted in lambda expressions.
Bertrand Russell: A British philosopher and logician who coauthored Principia Mathematica and helped develop modern logic. Church’s foundational work emerged from the logical tradition shaped by Russell and his contemporaries.
Lambda calculus in programming languages: The use of lambda-calculus abstractions and evaluation rules to describe programming-language features. It provides a compact model for functions, scope, and evaluation in language design.
Simply typed lambda calculus: A lambda calculus in which variables and expressions carry types formed from base types and function types. Unlike the untyped calculus, it restricts applications through explicit type rules.

Linked from 23 pages