Evaluation strategy

Programming language evaluation rules

In a programming language, an evaluation strategy is a set of rules for evaluating expressions. The term is often used to refer to the more specific notion of a parameter passing strategy that defines the kind of value that is passed to the function for each parameter (the binding strategy) and whether to evaluate the parameters of a function call, and if so in what order (the evaluation order). The notion of reduction strategy is distinct, although some authors conflate the two terms and the definition of each term is not widely agreed upon. To illustrate, executing a function call f(a,b) may first evaluate the arguments a and b, store the results in references or memory locations ref a and ref b, then evaluate the function's body with those references passed in. This gives the function the ability to look up the argument values, to modify them via assignment as if they were local variables, and to return values via the references. This is the call by reference evaluation strategy. Evaluation strategy is part of the semantics of the programming language definition. Some languages, such as PureScript, have variants with different evaluation strategies. Some declarative languages, such as Datalog, support multiple evaluation strategies. Some languages define a calling convention.

Applicative order is a family of evaluation orders in which a function's arguments are evaluated completely before the function is applied. This has the effect of making the function strict, i. e. the function's result is undefined if any of the arguments are undefined, so applicative order evaluation is more commonly called strict evaluation. Furthermore, a function call is performed as soon as it is encountered in a procedure, so it is also called eager evaluation or greedy evaluation. Some authors refer to strict evaluation as "call by value" due to the call by value binding strategy requiring strict evaluation. Scheme requires the execution order to be the sequential execution of an unspecified permutation of the arguments. OCaml similarly leaves the order unspecified, but in practice evaluates arguments right to left due to the design of its abstract machine. All of these are strict evaluation.

A non strict evaluation order is an evaluation order that is not strict, that is, a function may return a result before all of its arguments are fully evaluated. The prototypical example is normal order evaluation, which does not evaluate any of the arguments until they are needed in the body of the function. Normal order evaluation has the property that it terminates without error whenever any other evaluation order would have terminated without error. The name "normal order" comes from the lambda calculus, where normal order reduction will find a normal form if there is one (it is a "normalizing" reduction strategy). Lazy evaluation is classified in this article as a binding technique rather than an evaluation order. But this distinction is not always followed and some authors define lazy evaluation as normal order evaluation or vice versa, or confuse non strictness with lazy evaluation. Normal order evaluation has historically had a lack of usable debugging tools due to its complexity.

In logic programming, the evaluation of an expression may simply correspond to the unification of the terms involved combined with the application of some form of resolution. Unification must be classified as a strict binding strategy because it is fully performed. However, unification can also be performed on unbounded variables, so calls may not necessarily commit to final values for all its variables.

Call by name is an evaluation strategy where the arguments to a function are not evaluated before the function is called—rather, they are substituted directly into the function body (using capture avoiding substitution) and then left to be evaluated whenever they appear in the function. If an argument is not used in the function body, the argument is never evaluated; if it is used several times, it is re evaluated each time it appears. (See Jensen's device for a programming technique that exploits this.) Call by name evaluation is occasionally preferable to call by value evaluation. If a function's argument is not used in the function, call by name will save time by not evaluating the argument, whereas call by value will evaluate it regardless. If the argument is a non terminating computation, the advantage is enormous. However, when the function argument is used, call by name is often slower, requiring a mechanism such as a thunk. NET languages can simulate call by name using delegates or Expression<T> parameters. The latter results in an abstract syntax tree being given to the function. Eiffel provides agents, which represent an operation to be evaluated when needed. Seed7 provides call by name with function parameters. Java programs can accomplish similar lazy evaluation using lambda expressions and the java. util. function. Supplier<T> interface.

Call by need is a memoized variant of call by name, where, if the function argument is evaluated, that value is stored for subsequent use. If the argument is pure (i. e., free of side effects), this produces the same results as call by name, saving the cost of recomputing the argument. Haskell is a well known language that uses call by need evaluation. Because evaluation of expressions may happen arbitrarily far into a computation, Haskell supports only side effects (such as mutation) via the use of monads. This eliminates any unexpected behavior from variables whose values change prior to their delayed evaluation. In R's implementation of call by need, all arguments are passed, meaning that R allows arbitrary side effects. Lazy evaluation is the most common implementation of call by need semantics, but variations like optimistic evaluation exist. NET languages implement call by need using the type Lazy<T>. Graph reduction is an efficient implementation of lazy evaluation.

Call by macro expansion is similar to call by name, but uses textual substitution rather than capture avoiding substitution. Macro substitution may therefore result in variable capture, leading to mistakes and undesired behavior. Hygienic macros avoid this problem by checking for and replacing shadowed variables that are not parameters.