Evaluation strategy

Summary

An evaluation strategy is a rule that decides which part of an expression to compute next. In the lambda calculus it chooses which redex to contract in each beta reduction step. The main strategies are normal order, which reduces the leftmost outermost redex, and applicative order, which reduces the leftmost innermost one. Programming languages use the weak versions call-by-name, call-by-need and call-by-value, and the choice affects termination and efficiency.