redexes

A redex, short for reducible expression, is a subexpression of a term that can be reduced in one evaluation step according to a given rewriting or evaluation rule. In the lambda calculus, the most common redex is the beta-redex, an application of a lambda abstraction to an argument, written (λx. M) N, which reduces in one step to M[x := N], i.e., M with x replaced by N while avoiding variable capture. Other redexes include eta-redexes, such as λx. f x, which can be simplified to f under eta-conversion when x is not free in f. In term-rewriting systems, any subterm that matches the left-hand side of a rewrite rule is a redex.

Reduction strategies determine which redex to contract first. A term that contains no redexes is in normal form. If reduction occurs only at the outermost redex, the term is in weak head normal form. Different strategies, such as normal order (head-first) and applicative order (argument-first), can affect termination behavior in non-terminating languages, though they agree on the final result for strongly normalizing systems.

Redexes are central to the semantics of functional programming languages and to formal reasoning about programs. They underpin evaluation, optimization, and proofs of properties like confluence (the Church-Rosser property) and termination. The term originated in lambda-calculus literature and is widely used to refer to any subexpression eligible for a single rewrite step, reflecting the practice of marking reducible parts of a term for reduction.