lambdacalculus

Lambdacalculus, commonly called lambda calculus, is a formal system developed in the 1930s by Alonzo Church to study computation based on function abstraction and application. It uses three basic constructs: variables, abstractions written as λx. M, and applications written as (M N). Functions are treated as first-class citizens, and computation proceeds entirely through the manipulation of these lambda terms.

Evaluation in lambda calculus relies on beta reduction: applying a function to an argument, (λx. M) N, reduces to M with x substituted by N, written M[x := N]. A term is in beta-normal form when it contains no beta redexes, i.e., no subterms of the form (λx. M) N. Alpha-conversion allows renaming bound variables to avoid name clashes, and eta-conversion expresses functional extensionality by turning λx. (f x) into f when x does not occur freely in f. Together, these rules define when two lambda terms are considered equivalent.

Lambda calculus is expressive enough to encode data and control structures. Church numerals represent natural numbers as λf. λx. f^n x; booleans are encoded as true = λa. λb. a and false = λa. λb. b. Recursion and iteration are achieved through fixed-point combinators like the Y combinator, enabling general computation. The untyped version of lambda calculus is Turing complete, illustrating the Church-Turing thesis that it captures the notion of effective computation.

Typed variants introduce type systems that restrict terms, with the simply typed lambda calculus corresponding to constructive logic via the Curry-Howard correspondence. The calculus profoundly influenced the design of functional programming languages such as Lisp, Scheme, and Haskell, and remains a foundational model in logic and computer science.