Evaluation strategy
Evaluation strategies are used by programming languages to determine two things—when to evaluate the arguments of a function call and what kind of value to pass to the function.
To illustrate, a function application may evaluate the argument before evaluating the function's body and pass the ability to look up the argument's current value and modify it via assignment. The notion of reduction strategy in lambda calculus is similar but distinct.
In practical terms, many modern programming languages like C# and Java have converged on a call-by-value/call-by-reference evaluation strategy for function calls. Some languages, especially lower-level languages such as C++, combine several notions of parameter passing. Historically, call by value and call by name date back to ALGOL 60, which was designed in the late 1950s. Call by reference is used by PL/I and some Fortran systems. Purely functional languages like Haskell, as well as non-purely functional languages like R, use call by need.
Evaluation strategy is specified by the programming language definition, and is not a function of any specific implementation.
Strict evaluation
In strict evaluation, the arguments to a function are always evaluated completely before the function is applied.Under Church encoding, eager evaluation of operators maps to strict evaluation of functions; for this reason, strict evaluation is sometimes called "eager". Most existing programming languages use strict evaluation for functions.
Applicative order
Applicative order evaluation is an evaluation strategy in which an expression is evaluated by repeatedly evaluating its leftmost innermost reducible expression. This means that a function's arguments are evaluated before the function is applied.Call by value
Call by value is the most common evaluation strategy, used in languages as different as C and Scheme. In call by value, the argument expression is evaluated, and the resulting value 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.Call by value is not a single evaluation strategy, but rather the family of evaluation strategies in which a function's argument is evaluated before being passed to the function. While many programming languages that use call by value evaluate function arguments left-to-right, some evaluate functions and their arguments right-to-left, and others do not specify order.
Implicit limitations
In some cases, the term "call by value" is problematic, as the value which is passed is not the value of the variable as understood by the ordinary meaning of value, but an implementation-specific reference to the value. The effect is that what syntactically looks like call by value may end up rather behaving like call by reference or call by sharing, often depending on very subtle aspects of the language semantics.The reason for passing a reference is often that the language technically does not provide a value representation of complicated data, but instead represents them as a data structure while preserving some semblance of value appearance in the source code. Exactly where the boundary is drawn between proper values and data structures masquerading as such is often hard to predict. In C, an array is a data structure but the name of an array is treated as the reference to the first element of the array, while a struct variable's name refers to a value even if it has fields that are vectors. In Maple, a vector is a special case of a table and therefore a data structure, but a list is a value. In Tcl, values are "dual-ported" such that the value representation is used at the script level, and the language itself manages the corresponding data structure, if one is required. Modifications made via the data structure are reflected back to the value representation and vice versa.
The description "call by value where the value is a reference" is common ; another term is call by sharing. Thus the behaviour of call by value Java or Visual Basic and call by value C or Pascal are significantly different: in C or Pascal, calling a function with a large structure as an argument will cause the entire structure to be copied, potentially causing serious performance degradation, and mutations to the structure are invisible to the caller. However, in Java or Visual Basic only the reference to the structure is copied, which is fast, and mutations to the structure are visible to the caller.
Call by reference
Call by reference is an evaluation strategy where a function receives an implicit reference to a 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. 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. A simple litmus test for whether a language supports call-by-reference semantics is if it's possible to write a traditional
swap function in the language.Many languages support call by reference in some form, but few use it by default. FORTRAN II is an early example of a call-by-reference language. A few languages, such as C++, PHP, Visual Basic.NET, C# and REALbasic, default to call by value, but offer a special syntax for call-by-reference parameters. C++ additionally offers call by reference to const.
Call by reference can be simulated in languages that use call by value and don't exactly support call by reference, by making use of references, such as pointers. Languages such as C, ML and Rust use this technique. It is not a separate evaluation strategy—the language calls by value—but sometimes it is referred to as "call by address" or "pass by address". In ML, references are type- and memory-safe, similar to Rust.
A similar effect is achieved by call by sharing, used in languages like Java, Python, and Ruby.
In purely functional languages there is typically no semantic difference between the two strategies, so they are typically described as call by value even though implementations frequently use call by reference internally for the efficiency benefits.
Following is an example that demonstrates call by reference in the E programming language:
def modify
? var a := 1? var b := 2
- value: 1
? modify
- value: 2
? a? b
- value: 1
- value: 27
Following is an example of call by address that simulates call by reference in C:
void modify
int main
Call by sharing
Call by sharing is an evaluation strategy first noted by Barbara Liskov in 1974 for the CLU language. It is used by languages such as Python, Java, Ruby, JavaScript, Scheme, OCaml, AppleScript, and many others. However, the term "call by sharing" is not in common use; the terminology is inconsistent across different sources. For example, in the Java community, they say that Java is call by value. Call by sharing implies that values in the language are based on objects rather than primitive types, i.e., that all values are "boxed". Because they are boxed they can be said to pass by copy of reference.The semantics of call by sharing differ from call by reference: "In particular it is not call by value because mutations of arguments performed by the called routine will be visible to the caller. And it is not call by reference because access is not given to the variables of the caller, but merely to certain objects". So, for example, if a variable was passed, it is not possible to simulate an assignment on that variable in the callee's scope. However, since the function has access to the same object as the caller, mutations to those objects, if the objects are mutable, within the function are visible to the caller, which may appear to differ from call by value semantics. Mutations of a mutable object within the function are visible to the caller because the object is not copied or cloned—it is shared.
For example, in Python, lists are mutable, so:
def f:
list.append
m =
f
outputs
append method modifies the object on which it is called.Assignments within a function are not noticeable to the caller, because, in these languages, passing the variable only means passing the actual object referred to by the variable, not access to the original variable. Since the rebound variable only exists within the scope of the function, the counterpart in the caller retains its original binding.
Compare the Python mutation above with the code below, which binds the formal argument to a new object:
def f:
list =
m =
f
outputs
list = reassigns a new list to the variable rather than to the location it references.For immutable objects, there is no real difference between call by sharing and call by value, except if object identity is visible in the language. The use of call by sharing with mutable objects is an alternative to input/output parameters: the parameter is not assigned to, but the object is mutated.
Although this term has widespread usage in the Python community, identical semantics in other languages such as Java and Visual Basic are often described as call by value, where the value is implied to be a reference to the object.
Call by copy-restore
Call by copy-restore—also known as "copy-in copy-out", "call by value result", "call by value return" —is a special case of call by reference where the provided reference is unique to the caller. This variant has gained attention in multiprocessing contexts and Remote procedure call: if a parameter to a function call is a reference that might be accessible by another thread of execution, its contents may be copied to a new reference that is not; when the function call returns, the updated contents of this new reference are copied back to the original reference.The semantics of call by copy-restore also differ from those of call by reference, where two or more function arguments alias one another. Under call by reference, writing to one will affect the other; call by copy-restore avoids this by giving the function distinct copies, but leaves the result in the caller's environment undefined depending on which of the aliased arguments is copied back first—will the copies be made in left-to-right order both on entry and on return?
When the reference is passed to the callee uninitialized, this evaluation strategy may be called "call by result".
Partial evaluation
In partial evaluation, evaluation may continue into the body of a function that has not been applied. Any sub-expressions that do not contain unbound variables are evaluated, and function applications whose argument values are known may be reduced. If there are side effects, complete partial evaluation may produce unintended results, which is why systems that support partial evaluation tend to do so only for "pure" expressions within functions.Non-strict evaluation
In non-strict evaluation, arguments to a function are not evaluated unless they are actually used in the evaluation of the function body.Under Church encoding, lazy evaluation of operators maps to non-strict evaluation of functions; for this reason, non-strict evaluation is often referred to as "lazy". Boolean expressions in many languages use a form of non-strict evaluation called short-circuit evaluation, where evaluation returns as soon as it can be determined that an unambiguous Boolean will result—for example, in a disjunctive expression where
true is encountered, or in a conjunctive expression where false is encountered, and so forth. Conditional expressions also usually use lazy evaluation, where evaluation returns as soon as an unambiguous branch will result.Normal order
Normal order evaluation is an evaluation strategy in which an expression is evaluated by repeatedly evaluating its leftmost outermost reducible expression. This means that a function's arguments are not evaluated before the function is applied.Call by name
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 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.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.
An early use was ALGOL 60. Today's.NET languages can simulate call by name using delegates or
Expression 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 interface.Call by need
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, 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 only supports side effects 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.Call by macro expansion
Call by macro expansion is similar to call by name, but uses textual substitution rather than capture, thereby avoiding substitution. But macro substitution may cause mistakes, resulting in variable capture, leading to undesired behavior. Hygienic macros avoid this problem by checking for and replacing shadowed variables that are not parameters.Nondeterministic strategies
Full β-reduction
Under "full β-reduction", any function application may be reduced at any time. This may be done even within the body of an unapplied function.Call by future
"Call by future", also known as "parallel call by name", is a concurrent evaluation strategy in which the value of a future expression is computed concurrently with the flow of the rest of the program with promises, also known as futures. When the promise's value is needed, the main program blocks until the promise has a value.This strategy is non-deterministic, as the evaluation can occur at any time between creation of the future and use of the future's value. It is similar to call by need in that the value is only computed once, and computation may be deferred until the value is needed, but it may be started before. Further, if the value of a future is not needed, such as if it is a local variable in a function that returns, the computation may be terminated partway through.
If implemented with processes or threads, creating a future will spawn one or more new processes or threads, accessing the value will synchronize these with the main thread, and terminating the computation of the future corresponds to killing the promises computing its value.
If implemented with a coroutine, as in.NET async/await, creating a future calls a coroutine, which may yield to the caller, and in turn be yielded back to when the value is used, cooperatively multitasking.