Betaredexes

Betaredexes are beta-redexes, or reducible expressions, in the lambda calculus. They are subterms that can be simplified by beta-reduction, replacing bound variables with their arguments. A typical beta-redex has the form (λx. M) N, which reduces to M[x := N].

The term betaredexes is a variant spelling; the standard term is beta-redexes. Both refer to the same concept: a subexpression that can be reduced by applying a function to an argument.

Examples illustrate the concept. The term ((λx. x) y) is a beta-redex; reducing yields y. In a more complex term, ((λx. λy. x y) a) b reduces first to (λy. a y) b, then to a b.

Evaluation strategies address how beta-redexes are chosen during reduction. Normal-order reduction reduces the leftmost outermost redex first; applicative-order reduces the leftmost innermost redex first. A lambda-term may contain many beta-redexes, and a term is in beta-normal form when it contains no beta-redexes. Not all terms have a normal form; evaluation may not terminate for some expressions.

Significance and context: beta-reduction is the fundamental computation step in untyped lambda calculus and underpins the interpretation of function application in functional programming languages. Related concepts include the redex, beta-normal form, and various reduction strategies such as normal-order and applicative-order.