Evaluation strategy


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 and whether to evaluate the parameters of a function call, and if so in what 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. A programming language's evaluation strategy is part of its high-level semantics. Some languages, such as PureScript, have variants with different evaluation strategies. Some declarative languages, such as Datalog, support multiple evaluation strategies.
Just like in mathematics, evaluation is the process of finding the value corresponding to an expression.
The calling convention consists of the low-level platform-specific details of parameter passing.

Example

To illustrate, executing a function call f 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 original argument values passed in through dereferencing the parameters, 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.

Table

This is a table of evaluation strategies and representative languages by year introduced. The representative languages are listed in chronological order, starting with the language that introduced the strategy and followed by prominent languages that use the strategy.
Evaluation strategyRepresentative languagesYear first introduced
Call by referenceFortran II, PL/I1958
Call by valueALGOL, C, Scheme, MATLAB1960
Call by nameALGOL 60, Simula1960
Call by copy-restoreFortran IV, Ada1962
Call by unificationProlog1965
Call by needSASL, Haskell, R1971
Call by sharingCLU, Java, Python, Ruby, Julia1974
Call by reference parametersC++, PHP, C#, Visual Basic.NET1985
Call by reference to constC++, C1985

Evaluation orders

While the order of operations defines the abstract syntax tree of the expression, the evaluation order defines the order in which expressions are evaluated. For example, the Python program

def f:
print
return x
print + f)

outputs 123 due to Python's left-to-right evaluation order, but a similar program in OCaml:

let f x = print_int x; x ;;
print_int

outputs 213 due to OCaml's right-to-left evaluation order.
The evaluation order is mainly visible in code with side effects, but it also affects the performance of the code because a rigid order inhibits instruction scheduling. For this reason language standards such as C++ traditionally left the order unspecified, although languages such as Java and C# define the evaluation order as left-to-right and the C++17 standard has added constraints on the evaluation order.

Strict evaluation

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.
Common Lisp, Eiffel and Java evaluate function arguments left-to-right. C leaves the order undefined. 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.

Non-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. 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.
Boolean expressions in many languages use a form of non-strict evaluation called short-circuit evaluation, where evaluation evaluates the left expression but may skip the right expression if the result can be determined—for example, in a disjunctive expression where true is encountered, or in a conjunctive expression where false is encountered, and so forth. Conditional expressions similarly use non-strict evaluation - only one of the branches is evaluated.

Comparison of applicative order and normal order evaluation

With normal order evaluation, expressions containing an expensive computation, an error, or an infinite loop will be ignored if not needed, allowing the specification of user-defined control flow constructs, a facility not available with applicative order evaluation. Normal order evaluation uses complex structures such as thunks for unevaluated expressions, compared to the call stack used in applicative order evaluation. Normal order evaluation has historically had a lack of usable debugging tools due to its complexity.

Strict binding strategies

Call by value

In call by value, the evaluated value of the argument expression is bound to the corresponding variable in the function. If the function or procedure is able to assign values to its parameters, only its local variable is assigned—that is, anything passed into a function call is unchanged in the caller's scope when the function returns. For example, in Pascal, passing an array by value will cause the entire array to be copied, and any mutations to this array will be invisible to the caller:

program Main;
uses crt;
procedure PrintArray;
var
i: Integer;
begin
for i := Low to High do
Write;
WriteLn;
end;
Procedure Modify;
begin
PrintArray; // 123
Row := 4;
PrintArray; // 143
end;
Var
A : Array of integer;
begin
A := ;
PrintArray; // 123
Modify;
PrintArray; // 123
end.

Semantic drift

Strictly speaking, under call by value, no operations performed by the called routine can be visible to the caller, other than as part of the return value. This implies a form of purely functional programming in the implementation semantics. However, the circumlocution "call by value where the value is a reference" has become common in some languages, for example, the Java community. Compared to traditional pass by value, the value which is passed is not a value as understood by the ordinary meaning of value, such as an integer that can be written as a literal, but an implementation-internal reference handle. Mutations to this reference handle are visible in the caller. Due to the visible mutation, this form of "call by value" is more properly referred to as call by sharing.
In purely functional languages, values and data structures are immutable, so there is no possibility for a function to modify any of its arguments. As such, there is typically no semantic difference between passing by value and passing by reference or a pointer to the data structure, and implementations frequently use call by reference internally for the efficiency benefits. Nonetheless, these languages are typically described as call by value languages.

Call by reference

Call by reference is an evaluation strategy where a parameter is bound to an implicit reference to the variable used as argument, rather than a copy of its value. This typically means that the function can modify the variable used as argument—something that will be seen by its caller. Call by reference can therefore be used to provide an additional channel of communication between the called function and the calling function. Pass by reference can significantly improve performance: calling a function with a many-megabyte structure as an argument does not have to copy the large structure, only the reference to the structure. However, a call-by-reference language makes it more difficult for a programmer to track the effects of a function call, and may introduce subtle bugs.
Due to variation in syntax, the difference between call by reference and call by sharing is often unclear on first glance. A simple litmus test is if it's possible to write a traditional swap function in the language. For example in Fortran:

program Main
implicit none
integer :: a = 1
integer :: b = 2
call Swap
print *, a, b ! 2 1
contains
subroutine Swap
integer, intent :: a, b
integer :: temp
temp = a
a = b
b = temp
end subroutine Swap
end program Main

Therefore, Fortran's inout intent implements call-by-reference; any variable can be implicitly converted to a reference handle. In contrast the closest one can get in Java is:

public class Main

where an explicit Box type must be used to introduce a handle. Java is call-by-sharing but not call-by-reference.