lambdaterms

Lambdaterms, or lambda terms, are formal objects used in the lambda calculus and related areas of logic and computer science. They are expressions that denote functions and their applications. A lambdaterm is built from three constructs: variables, lambda abstractions, and applications. The standard inductive definition is: a variable x is a term; if M is a term, then λx. M is a term; if M and N are terms, then (M N) is a term. This framework allows the representation of anonymous functions and higher-order functions.

Key notions include free and bound variables and alpha-equivalence. In λx. M, x is bound by the abstraction, while variables that are not bound are free. Two terms that differ only by the names of their bound variables are considered alpha-equivalent, such as λx. x and λy. y. Reduction rules govern how terms evaluate. The primary rule is beta-reduction: (λx. M) N reduces to M[x := N], meaning N is substituted for x in M. A term with no beta-redexes (no subterms of the form (λx. M) N) is in beta-normal form. Eta-conversion (λx. F x) to F is a related but optional simplification, under certain conditions.

Examples illustrate the idea. The identity function I = λx. x, when applied to y, yields y. A function such as λx. λy. x y represents a higher-order operation that takes two arguments in sequence.

In programming language theory, lambdaterms underpin the representation of functions in functional languages and enable formal reasoning about function application, evaluation order, and termination. Untyped lambda calculus can express general recursion, while typed variants impose restrictions to ensure certain properties like termination.