applicativeorder

Applicative order is a reduction strategy used in the lambda calculus and in the operational semantics of programming languages. It reduces the arguments of a function application before applying the function to them. In practice this corresponds to eager evaluation or call-by-value in many languages: evaluate all function arguments to values, then perform the application.

In contrast, normal order evaluation reduces the outermost part of an expression first. In lambda-calculus terms, applicative order tends to reduce the leftmost innermost redex, while normal order reduces the leftmost outermost redex. The difference matters for termination and side effects: normal order is more likely to terminate when a normal form exists, because it avoids evaluating arguments that are not needed. Applicative order can diverge if an argument itself diverges, even if the overall result would not require evaluating that argument.

A classic illustration uses the term (λx. 0) Ω, where Ω = (λy. y y) (λy. y y). Under applicative order, evaluating the argument Ω diverges, so the whole term diverges. Under normal order, the outer function is applied first, yielding 0 without evaluating Ω.

In programming languages, applicative order aligns with call-by-value or strict evaluation. Languages like Scheme (with eager evaluation), OCaml, and JavaScript implement this approach. Some languages provide lazy or mixed evaluation mechanisms, allowing deviations from pure applicative order for efficiency or control.

History and context: the terms applicative order and normal order originate in discussions of reduction strategies for the lambda calculus, distinguishing different orders of evaluating function applications.