Evaluation strategy

In a programming language, an evaluation strategy is a set of rules for evaluating expressions.^[1] The term is often used to refer to the more specific notion of a parameter-passing strategy^[2] that defines the kind of value that is passed to the function for each parameter (the binding strategy)^[3] and whether to evaluate the parameters of a function call, and if so in what order (the evaluation order).^[4] The notion of reduction strategy is distinct,^[5] although some authors conflate the two terms and the definition of each term is not widely agreed upon.^[6] 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.^[7]^[8]

The calling convention consists of the low-level platform-specific details of parameter passing.

Example

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 original argument values passed in through dereferencing the parameters (some languages use specific operators to perform this), 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.^[9]

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(s) that introduced the strategy and followed by prominent languages that use the strategy.^[10]^: 434

Evaluation strategy	Representative languages	Year first introduced
Call by reference	Fortran II, PL/I	1958
Call by value	ALGOL, C,^[11] Scheme, MATLAB^[12]	1960
Call by name	ALGOL 60, Simula	1960
Call by copy-restore	Fortran IV, Ada^[13]	1962
Call by unification	Prolog	1965^[14]^[15]
Call by need	SASL,^[16] Haskell, R^[17]	1971^[18]
Call by sharing	CLU, Java, Python, Ruby, Julia	1974^[19]
Call by reference parameters	C++, PHP,^[20] C#,^[21] Visual Basic .NET^[22]	1985^[23]
Call by reference to const	C++, C	1985^[23]

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(x):
    print(x, end="")
    return x

print(f(1) + f(2))

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 (f 1 + f 2)

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^[10]^{: 240–241} and the C++17 standard has added constraints on the evaluation order.^[24]

Strict evaluation

Applicative order is a family of evaluation orders in which a function's arguments are evaluated completely before the function is applied. ^[25] 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.^[26]^[27] Some authors refer to strict evaluation as "call by value" due to the call-by-value binding strategy requiring strict evaluation.^[4]

Common Lisp, Eiffel and Java evaluate function arguments left-to-right. C leaves the order undefined.^[28] Scheme requires the execution order to be the sequential execution of an unspecified permutation of the arguments.^[29] OCaml similarly leaves the order unspecified, but in practice evaluates arguments right-to-left due to the design of its abstract machine.^[30] 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.^[31]^: 46–47 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.^[32] Normal order evaluation has the property that it terminates without error whenever any other evaluation order would have terminated without error.^[33] 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).^[34] 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,^[25]^[35] or confuse non-strictness with lazy evaluation.^[31]^: 43–44

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 (OR) where true is encountered, or in a conjunctive expression (AND) where false is encountered, and so forth.^[35] Conditional expressions similarly use non-strict evaluation - only one of the branches is evaluated.^[31]

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,^[4] 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.^[36] Normal order evaluation has historically had a lack of usable debugging tools due to its complexity.^[37]

Strict binding strategies

Call by value

In call by value (or pass by value), the evaluated value of the argument expression is bound to the corresponding variable in the function (frequently by copying the value into a new memory region). 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:^[38]

program Main;
uses crt;

procedure PrintArray(a: Array of integer);
var
  i: Integer;
begin
  for i := Low(a) to High(a) do
    Write(a[i]);
  WriteLn();
end;

Procedure Modify(Row : Array of integer);  
begin  
  PrintArray(Row); // 123
  Row[1] := 4;
  PrintArray(Row); // 143
end;

Var
  A : Array of integer; 
begin
  A := [1,2,3];
  PrintArray(A); // 123
  Modify(A);
  PrintArray(A); // 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.^[19] 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.^[39] 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.^[19]

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 (or pass 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 (i.e., assign to) 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 (which is generally a machine word and only a few bytes). 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 (where the reference type is implicit) and call by sharing (where the reference type is explicit) is often unclear on first glance. A simple litmus test is if it's possible to write a traditional swap(a, b) function in the language.^[39] For example in Fortran:

program Main
    implicit none
    integer :: a = 1
    integer :: b = 2
    call Swap(a, b)
    print *, a, b ! 2 1
contains
    subroutine Swap(a, b)
        integer, intent(inout) :: 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:

class Main {
    static class Box {
        int value;
        public Box(int value) {
            this.value = value;
        }
    }

    static void swap(Box a, Box b) {
        int temp = a.value;
        a.value = b.value;
        b.value = temp;
    }

    public static void main(String[] args) {
        Box a = new Box(1);
        Box b = new Box(2);
        swap(a, b);
        System.out.printf("a = %d, b = %d%n", a.value, b.value);
        // output: a = 2, b = 1
    }
}

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

Call by copy-restore

Call by copy-restore—also known as "copy-in copy-out", "call by value result", "call by value return" (as termed in the Fortran community)—is a variation of call by reference. With call by copy-restore, the contents of the argument are copied to a new variable local to the call invocation. The function may then modify this variable, similarly to call by reference, but as the variable is local, the modifications are not visible outside of the call invocation during the call. When the function call returns, the updated contents of this variable are copied back to overwrite the original argument ("restored").^[40]

The semantics of call by copy-restore is similar in many cases to call by reference, but differs when two or more function arguments alias one another (i.e., point to the same variable in the caller's environment). Under call by reference, writing to one argument will affect the other during the function's execution. Under call by copy-restore, writing to one argument will not affect the other during the function's execution, but at the end of the call, the values of the two arguments may differ, and it is unclear which argument is copied back first and therefore what value the caller's variable receives.^[41] For example, Ada specifies that the copy-out assignment for each in out or out parameter occurs in an arbitrary order.^[42] From the following program (illegal in Ada 2012)^[43] it can be seen that the behavior of GNAT is to copy in left-to-right order on return:

with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Copy_Restore is
  procedure Modify (A, B : in out Integer) is
  begin
      A := A + 1;
      B := B + 2;
  end Modify;
  X : Integer := 0;
begin
  Modify(X, X);
  Put_Line("X = " & Integer'Image(X));
end Test_Copy_Restore;
-- $ gnatmake -gnatd.E test_copy_restore.adb; ./test_copy_restore
-- test_copy_restore.adb:12:10: warning: writable actual for "A" overlaps with actual for "B" [-gnatw.i]
-- X = 2

If the program returned 1 it would be copying right-to-left, and under call by reference semantics the program would return 3.

When the reference is passed to the caller uninitialized (for example an out parameter in Ada as opposed to an in out parameter), this evaluation strategy may be called "call by result".

This strategy has gained attention in multiprocessing and remote procedure calls,^[44] as unlike call-by-reference it does not require frequent communication between threads of execution for variable access.

Call by sharing

Call by sharing (also known as "pass by sharing", "call by object", or "call by object-sharing") is an evaluation strategy that is intermediate between call by value and call by reference. Rather than every variable being exposed as a reference, only a specific class of values, termed "references", "boxed types", or "objects", have reference semantics, and it is the addresses of these pointers that are passed into the function. Like call by value, the value of the address passed is a copy, and direct assignment to the parameter of the function overwrites the copy and is not visible to the calling function. Like call by reference, mutating the target of the pointer is visible to the calling function. Mutations of a mutable object within the function are visible to the caller because the object is not copied or cloned—it is shared, hence the name "call by sharing".^[19]

The technique was first noted by Barbara Liskov in 1974 for the CLU language.^[19] It is used by many modern languages such as Python (the shared values being called "objects"),^[45] Java (objects), Ruby (objects), JavaScript (objects), Scheme (data structures such as vectors),^[46] AppleScript (lists, records, dates, and script objects), OCaml and ML (references, records, arrays, objects, and other compound data types), Maple (rtables and tables), and Tcl (objects).^[47] The term "call by sharing" as used in this article 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.^[39]

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 (the argument is not overwritten and object identity is not changed), but the object (argument) is mutated.^[48]

For example, in Python, lists are mutable and passed with call by sharing, so:

def f(a_list):
    a_list.append(1)

m = []
f(m)
print(m)

outputs [1] because the append method modifies the object on which it is called.

In contrast, assignments within a function are not noticeable to the caller. For example, this code binds the formal argument to a new object, but it is not visible to the caller because it does not mutate a_list:

def f(a_list):
    a_list = a_list + [1]
    print(a_list)  # [1]

m = []
f(m)
print(m)  # []

Call by address

Call by address, pass by address, or call/pass by pointer is a parameter passing method where the address of the argument is passed as the formal parameter. Inside the function, the address (pointer) may be used to access or modify the value of the argument. For example, the swap operation can be implemented as follows in C:^[49]

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int a = 1;
    int b = 2;
    swap(&a, &b);
    printf("%d %d\n", a, b); // 2 1
    return 0;
}

Some authors treat & as part of the syntax of calling swap. Under this view, C supports the call-by-reference parameter passing strategy.^[50] Other authors take a differing view that the presented implementation of swap in C is only a simulation of call-by-reference using pointers.^[51] Under this "simulation" view, mutable variables in C are not first-class (that is, l-values are not expressions), rather pointer types are. In this view, the presented swap program is syntactic sugar for a program that uses pointers throughout,^[52] for example this program (read and assign have been added to highlight the similarities to the Java Box call-by-sharing program above):

#include <stdio.h>

int read(int* p) {
    return *p;
}

void assign(int* p, int v) {
    *p = v;
}

void swap(int* a, int* b) {
    int temp_storage; 
    int* temp = &temp_storage;
    assign(temp, read(a));
    assign(a, read(b));
    assign(b, read(temp));
}

int main() {
    int a_storage; 
    int* a = &a_storage;
    int b_storage; 
    int* b = &b_storage;
    assign(a, 1);
    assign(b, 2);
    swap(a, b);
    printf("%d %d\n", read(a), read(b)); // 2 1
    return 0;
}

Because in this program, swap operates on pointers and cannot change the pointers themselves, but only the values the pointers point to, this view holds that C's main evaluation strategy is more similar to call-by-sharing.

C++ confuses the issue further by allowing swap to be declared and used with a very lightweight "reference" syntax:^[53]

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

int main() {
    int a = 1;
    int b = 2;
    swap(a, b);
    std::println("{} {}", a, b); // 2 1
    return 0;
}

Semantically, this is equivalent to the C examples. As such, many authors consider call-by-address to be a unique parameter passing strategy distinct from call-by-value, call-by-reference, and call-by-sharing.

Call by unification

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.

Non-strict binding strategies

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 (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. Java programs can accomplish similar lazy evaluation using lambda expressions and the java.util.function.Supplier<T> 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 (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

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.

Call by future

"Call by future", also known as "parallel call by name" or "lenient evaluation",^[54] is a concurrent evaluation strategy combining non-strict semantics with eager evaluation. The method requires fine-grained dynamic scheduling and synchronization but is suitable for massively parallel machines.

The strategy creates a future (promise) for the function's body and each of its arguments. These futures are computed concurrently with the flow of the rest of the program. When a future A requires the value of another future B that has not yet been computed, future A blocks until future B finishes computing and has a value. If future B has already finished computing the value is returned immediately. Conditionals block until their condition is evaluated, and lambdas do not create futures until they are fully applied.^[55]

If implemented with processes or threads, creating a future will spawn one or more new processes or threads (for the promises), 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 (an async function), which may yield to the caller, and in turn be yielded back to when the value is used, cooperatively multitasking.

The strategy is non-deterministic, as the evaluation can occur at any time between creation of the future (i.e., when the expression is given) and use of the future's value. The strategy is non-strict because the function body may return a value before the arguments are evaluated. However, in most implementations, execution may still get stuck evaluating an unneeded argument. For example, the program

f x = 1/x
g y = 1
main = print (g (f 0))

may either have g finish before f, and output 1, or may result in an error due to evaluating 1/0.^[31]

Call-by-future is similar to call by need in that values are computed only once. With careful handling of errors and nontermination, in particular terminating futures partway through if it is determined they will not be needed, call-by-future also has the same termination properties as call-by-need evaluation.^[55] However, call-by-future may perform unnecessary speculative work compared to call-by-need, such as deeply evaluating a lazy data structure.^[31] This can be avoided by using lazy futures that do not start computation until it is certain the value is needed.

Optimistic evaluation

Optimistic evaluation is a call-by-need variant where the function's argument is partly evaluated in a call-by-value style for some amount of time (which may be adjusted at runtime). After that time has passed, evaluation is aborted and the function is applied using call by need.^[56] This approach avoids some of call-by-need's runtime expenses while retaining desired termination characteristics.

References

^ Araki, Shota; Nishizaki, Shin-ya (November 2014). "Call-by-name evaluation of RPC and RMI calculi". Theory and Practice of Computation. p. 1. doi:10.1142/9789814612883_0001. ISBN 978-981-4612-87-6. Retrieved 21 August 2021.
^ Turbak, Franklyn; Gifford, David (18 July 2008). Design Concepts in Programming Languages. MIT Press. p. 309. ISBN 978-0-262-30315-6.
^ Crank, Erik; Felleisen, Matthias (1991). "Parameter-passing and the lambda calculus". Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '91. p. 2. CiteSeerX 10.1.1.23.4385. doi:10.1145/99583.99616. ISBN 0897914198. S2CID 5782416.
^ ^a ^b ^c Wilhelm, Reinhard; Seidl, Helmut (10 November 2010). Compiler Design: Virtual Machines. Springer Science & Business Media. p. 61. ISBN 978-3-642-14909-2.
^ Nita, Stefania Loredana; Mihailescu, Marius (2017). "Introduction". Practical Concurrent Haskell. p. 3. doi:10.1007/978-1-4842-2781-7_1. ISBN 978-1-4842-2780-0.
^ Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. p. 56. ISBN 0-262-16209-1.
^ "Evaluate (v.), sense a". Oxford English Dictionary. 2023. doi:10.1093/OED/3423541985. Mathematics. To work out the 'value' of (a quantitative expression); to find a numerical expression for (any quantitative fact or relation).
^ "Simplify (v.), sense 4.a". Oxford English Dictionary. 2023. doi:10.1093/OED/1018661347. To express (an equation or other mathematical expression) in a form that is easier to understand, analyse, or work with, e.g. by collecting like terms or substituting variables.
^ Daniel P. Friedman; Mitchell Wand (2008). Essentials of Programming Languages (third ed.). Cambridge, MA: The MIT Press. ISBN 978-0262062794.
^ ^a ^b Scott, Michael Lee (2016). Programming language pragmatics (Fourth ed.). Waltham, MA: Elsevier. ISBN 9780124104778.
^ Kernighan, Brian W.; Ritchie, Dennis M. (1988). The C programming language (2nd ed.). Englewood Cliffs, N.J: Prentice Hall. p. 28. ISBN 978-0131103627.
^ "Avoid Unnecessary Copies of Data - MATLAB & Simulink". www.mathworks.com. Retrieved 2023-01-28.
^ Hasti, Rebecca. "Parameter Passing". CS 536: Introduction to Programming Languages and Compilers. University of Wisconsin. Retrieved 22 August 2021.
^ J.A. Robinson (Jan 1965). "A Machine-Oriented Logic Based on the Resolution Principle". Journal of the ACM. 12 (1): 23–41. doi:10.1145/321250.321253. S2CID 14389185.; Here: sect.5.8, p.32
^ J.A. Robinson (1971). "Computational logic: The unification computation". Machine Intelligence. 6: 63–72.
^ Bundy, Alan; Wallen, Lincoln (1984). "SASL". Catalogue of Artificial Intelligence Tools. p. 117. doi:10.1007/978-3-642-96868-6_222. ISBN 978-3-540-13938-6. Was probably the first language to systematically exploit the power of lazy evaluation.
^ Fay, Colin (30 July 2018). "About lazy evaluation". R-bloggers. Retrieved 21 August 2021.
^ Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus (PhD). Oxford University.
^ ^a ^b ^c ^d ^e Liskov, Barbara; Atkinson, Russ; Bloom, Toby; Moss, Eliot; Schaffert, Craig; Scheifler, Craig; Snyder, Alan (October 1979). "CLU Reference Manual" (PDF). Laboratory for Computer Science. Massachusetts Institute of Technology. pp. 14–15. Archived (PDF) from the original on 2006-09-22. Retrieved 2011-05-19.
^ "PHP: Passing by Reference - Manual". www.php.net. Retrieved 2021-07-04.
^ Wagner, Bill (12 April 2023). "Passing Parameters - C# Programming Guide". Microsoft Docs. Retrieved 2023-09-10.
^ Dollard, Kathleen (15 September 2021). "Passing Arguments by Value and by Reference - Visual Basic". Microsoft Docs. Retrieved 2023-09-10.
^ ^a ^b "History of C++". en.cppreference.com. Retrieved 11 June 2022.
^ Filipek, Bartlomiej (16 August 2021). "Stricter Expression Evaluation Order in C++17". C++ Stories. Retrieved 24 August 2021.
^ ^a ^b Abelson, Harold; Sussman, Gerald Jay (1996). "Normal Order and Applicative Order". Structure and interpretation of computer programs (2nd ed.). Cambridge, Massachusetts: MIT Press. ISBN 0-262-01153-0. Archived from the original on 2005-03-02. Retrieved 2006-03-06. See also footnote Temp 576.
^ Reese, Richard M. (14 October 2015). Learning Java Functional Programming. Packt Publishing Ltd. p. 106. ISBN 978-1-78528-935-4.
^ Antani, Ved; Timms, Simon; Mantyla, Dan (31 August 2016). JavaScript: Functional Programming for JavaScript Developers. Packt Publishing Ltd. p. 614. ISBN 978-1-78712-557-5.
^ Seacord, Robert C. "EXP30-C. Do not depend on the order of evaluation for side effects". SEI CERT C Coding Standard. Carnegie Mellon University. Retrieved 23 August 2021.
^ Anglade, S.; Lacrampe, J. J.; Queinnec, C. (October 1994). "Semantics of combinations in scheme" (PDF). ACM SIGPLAN Lisp Pointers. VII (4): 15–20. doi:10.1145/382109.382669. S2CID 2987427.
^ "Why are OCaml function arguments evaluated right-to-left?". OCaml. 30 November 2017.
^ ^a ^b ^c ^d ^e Tremblay, G. (April 2000). "Lenient evaluation is neither strict nor lazy". Computer Languages. 26 (1): 43–66. CiteSeerX 10.1.1.137.9885. doi:10.1016/S0096-0551(01)00006-6.
^ George, Lai (March 1987). Efficient evaluation of normal order through strictness information (MSc). University of Utah. p. 10.
^ Borning, Alan (Autumn 1999). "Applicative vs Normal Order Evaluation in Functional Languages" (PDF). CSE 505: Concepts of Programming Languages. University of Washington. Retrieved 23 August 2021.
^ Mazzola, Guerino; Milmeister, Gérard; Weissmann, Jody (21 October 2004). Comprehensive Mathematics for Computer Scientists 2. Springer Science & Business Media. p. 323. ISBN 978-3-540-20861-7.
^ ^a ^b Sturm, Oliver (11 April 2011). Functional Programming in C#: Classic Programming Techniques for Modern Projects. John Wiley and Sons. p. 91. ISBN 978-0-470-74458-1.
^ Marlow, Simon. "Why can't I get a stack trace?". Haskell Implementors Workshop 2012. Retrieved 25 August 2021.
^ Nilsson, Henrik (1999). "Tracing piece by piece: Affordable debugging for lazy functional languages". Proceedings of the fourth ACM SIGPLAN international conference on Functional programming. pp. 36–47. CiteSeerX 10.1.1.451.6513. doi:10.1145/317636.317782. ISBN 1581131119. S2CID 13954359.
^ "Open array parameters". www.freepascal.org. Retrieved 20 January 2024.
^ ^a ^b ^c ^d "Java is Pass-by-Value, Dammit!". 16 May 2001. Retrieved 2016-12-24.
^ Coenen, Frans. "PARAMETER PASSING". cgi.csc.liv.ac.uk. Retrieved 22 January 2024.
^ "Call by Reference, Aliasing Issues" (PDF). MPRI Course 2-36-1: Proof of Program (Lecture notes). p. 53. Archived from the original (PDF) on 25 June 2024.
^ Ada 2022 Language Reference Manual (PDF). 13 October 2023. p. 215.
^ Barnes, John (2013). Ada 2012 rationale: the language, the standard libraries (PDF). Heidelberg: Springer. pp. 15–16, 87–88. ISBN 978-3-642-45210-9.
^ Thurlow, Robert (May 2009). "RPC: Remote Procedure Call Protocol Specification Version 2". tools.ietf.org. IETF. Retrieved 7 April 2018.
^ Lundh, Fredrik. "Call by Object". Effbot.org. Archived from the original on 2011-05-19. Retrieved 2011-05-19.
^ Jones, Rhys Price (2010). "Is Scheme call-by-value?". CS 145 Programming Languages Lab 9: Parameter Passing. George Washington University. Archived from the original on 16 October 2014. Retrieved 20 January 2024.
^ "Tcl Library Procedures - Tcl_Obj manual page". www.tcl.tk.
^ "CA1021: Avoid out parameters". Microsoft. 15 November 2016.
^ Leo, Ray (November 1996). Little C++ (Made Easy). LeoSudo Inc. pp. 79–80. ISBN 978-0-9654634-1-6.
^ Dandamudi, Sivarama P. (15 July 2005). Guide to Assembly Language Programming in Linux. Springer Science & Business Media. p. 232. ISBN 978-0-387-25897-3.
^ Srivastava, S. K.; Srivastava, Deepali (6 June 2018). C in Depth. BPB Publications. p. 206. ISBN 978-93-87284-94-4.
^ "Mutable Variables and Reference Types". okmij.org. Retrieved 20 January 2024.
^ Vermeir, Dirk (28 June 2011). Multi-Paradigm Programming using C++. Springer Science & Business Media. pp. 10–11. ISBN 978-1-4471-0311-0.
^ McCollin, Thomas Gwynfryn; Morell, Tobias. "A Game of Paradigms: A Usability Study of Functional Idioms in Gameplay Programming" (PDF). Aalborg University. p. 6. Retrieved 11 January 2022.
^ ^a ^b Schauser, Klaus E.; Goldstein, Seth C. (1995). "How much non-strictness do lenient programs require?" (PDF). Proceedings of the seventh international conference on Functional programming languages and computer architecture - FPCA '95. pp. 216–225. doi:10.1145/224164.224208. ISBN 0897917197. S2CID 2045943. Retrieved 7 January 2022.
^ Ennals, Robert; Peyton Jones, Simon (August 2003). Optimistic Evaluation: a fast evaluation strategy for non-strict programs. International Conference on Functional Programming. ACM Press. Archived from the original on 22 August 2025.

External links

The interactive on-line Geometry of Interaction visualiser, implementing a graph-based machine for several common evaluation strategies.

[1] Araki, Shota; Nishizaki, Shin-ya (November 2014). "Call-by-name evaluation of RPC and RMI calculi". Theory and Practice of Computation. p. 1. doi:10.1142/9789814612883_0001. ISBN 978-981-4612-87-6. Retrieved 21 August 2021.

[2] Turbak, Franklyn; Gifford, David (18 July 2008). Design Concepts in Programming Languages. MIT Press. p. 309. ISBN 978-0-262-30315-6.

[3] Crank, Erik; Felleisen, Matthias (1991). "Parameter-passing and the lambda calculus". Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '91. p. 2. CiteSeerX 10.1.1.23.4385. doi:10.1145/99583.99616. ISBN 0897914198. S2CID 5782416.

[Wilhelm-4] Wilhelm, Reinhard; Seidl, Helmut (10 November 2010). Compiler Design: Virtual Machines. Springer Science & Business Media. p. 61. ISBN 978-3-642-14909-2.

[5] Nita, Stefania Loredana; Mihailescu, Marius (2017). "Introduction". Practical Concurrent Haskell. p. 3. doi:10.1007/978-1-4842-2781-7_1. ISBN 978-1-4842-2780-0.

[Pierce-6] Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. p. 56. ISBN 0-262-16209-1.

[7] "Evaluate (v.), sense a". Oxford English Dictionary. 2023. doi:10.1093/OED/3423541985. Mathematics. To work out the 'value' of (a quantitative expression); to find a numerical expression for (any quantitative fact or relation).

[8] "Simplify (v.), sense 4.a". Oxford English Dictionary. 2023. doi:10.1093/OED/1018661347. To express (an equation or other mathematical expression) in a form that is easier to understand, analyse, or work with, e.g. by collecting like terms or substituting variables.

[9] Daniel P. Friedman; Mitchell Wand (2008). Essentials of Programming Languages (third ed.). Cambridge, MA: The MIT Press. ISBN 978-0262062794.

[Pragmatics-10] Scott, Michael Lee (2016). Programming language pragmatics (Fourth ed.). Waltham, MA: Elsevier. ISBN 9780124104778.

[11] Kernighan, Brian W.; Ritchie, Dennis M. (1988). The C programming language (2nd ed.). Englewood Cliffs, N.J: Prentice Hall. p. 28. ISBN 978-0131103627.

[12] "Avoid Unnecessary Copies of Data - MATLAB & Simulink". www.mathworks.com. Retrieved 2023-01-28.

[13] Hasti, Rebecca. "Parameter Passing". CS 536: Introduction to Programming Languages and Compilers. University of Wisconsin. Retrieved 22 August 2021.

[Robinson.1965-14] J.A. Robinson (Jan 1965). "A Machine-Oriented Logic Based on the Resolution Principle". Journal of the ACM. 12 (1): 23–41. doi:10.1145/321250.321253. S2CID 14389185.; Here: sect.5.8, p.32

[15] J.A. Robinson (1971). "Computational logic: The unification computation". Machine Intelligence. 6: 63–72.

[16] Bundy, Alan; Wallen, Lincoln (1984). "SASL". Catalogue of Artificial Intelligence Tools. p. 117. doi:10.1007/978-3-642-96868-6_222. ISBN 978-3-540-13938-6. Was probably the first language to systematically exploit the power of lazy evaluation.

[17] Fay, Colin (30 July 2018). "About lazy evaluation". R-bloggers. Retrieved 21 August 2021.

[18] Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus (PhD). Oxford University.

[CLU_Reference_Manual-19] Liskov, Barbara; Atkinson, Russ; Bloom, Toby; Moss, Eliot; Schaffert, Craig; Scheifler, Craig; Snyder, Alan (October 1979). "CLU Reference Manual" (PDF). Laboratory for Computer Science. Massachusetts Institute of Technology. pp. 14–15. Archived (PDF) from the original on 2006-09-22. Retrieved 2011-05-19.

[20] "PHP: Passing by Reference - Manual". www.php.net. Retrieved 2021-07-04.

[21] Wagner, Bill (12 April 2023). "Passing Parameters - C# Programming Guide". Microsoft Docs. Retrieved 2023-09-10.

[22] Dollard, Kathleen (15 September 2021). "Passing Arguments by Value and by Reference - Visual Basic". Microsoft Docs. Retrieved 2023-09-10.

[CPPHist-23] "History of C++". en.cppreference.com. Retrieved 11 June 2022.

[24] Filipek, Bartlomiej (16 August 2021). "Stricter Expression Evaluation Order in C++17". C++ Stories. Retrieved 24 August 2021.

[SICP-25] Abelson, Harold; Sussman, Gerald Jay (1996). "Normal Order and Applicative Order". Structure and interpretation of computer programs (2nd ed.). Cambridge, Massachusetts: MIT Press. ISBN 0-262-01153-0. Archived from the original on 2005-03-02. Retrieved 2006-03-06. See also footnote Temp 576.

[26] Reese, Richard M. (14 October 2015). Learning Java Functional Programming. Packt Publishing Ltd. p. 106. ISBN 978-1-78528-935-4.

[27] Antani, Ved; Timms, Simon; Mantyla, Dan (31 August 2016). JavaScript: Functional Programming for JavaScript Developers. Packt Publishing Ltd. p. 614. ISBN 978-1-78712-557-5.

[28] Seacord, Robert C. "EXP30-C. Do not depend on the order of evaluation for side effects". SEI CERT C Coding Standard. Carnegie Mellon University. Retrieved 23 August 2021.

[29] Anglade, S.; Lacrampe, J. J.; Queinnec, C. (October 1994). "Semantics of combinations in scheme" (PDF). ACM SIGPLAN Lisp Pointers. VII (4): 15–20. doi:10.1145/382109.382669. S2CID 2987427.

[30] "Why are OCaml function arguments evaluated right-to-left?". OCaml. 30 November 2017.

[Tremblay-31] Tremblay, G. (April 2000). "Lenient evaluation is neither strict nor lazy". Computer Languages. 26 (1): 43–66. CiteSeerX 10.1.1.137.9885. doi:10.1016/S0096-0551(01)00006-6.

[32] George, Lai (March 1987). Efficient evaluation of normal order through strictness information (MSc). University of Utah. p. 10.

[33] Borning, Alan (Autumn 1999). "Applicative vs Normal Order Evaluation in Functional Languages" (PDF). CSE 505: Concepts of Programming Languages. University of Washington. Retrieved 23 August 2021.

[Mazzola-34] Mazzola, Guerino; Milmeister, Gérard; Weissmann, Jody (21 October 2004). Comprehensive Mathematics for Computer Scientists 2. Springer Science & Business Media. p. 323. ISBN 978-3-540-20861-7.

[Sturm-35] Sturm, Oliver (11 April 2011). Functional Programming in C#: Classic Programming Techniques for Modern Projects. John Wiley and Sons. p. 91. ISBN 978-0-470-74458-1.

[36] Marlow, Simon. "Why can't I get a stack trace?". Haskell Implementors Workshop 2012. Retrieved 25 August 2021.

[37] Nilsson, Henrik (1999). "Tracing piece by piece: Affordable debugging for lazy functional languages". Proceedings of the fourth ACM SIGPLAN international conference on Functional programming. pp. 36–47. CiteSeerX 10.1.1.451.6513. doi:10.1145/317636.317782. ISBN 1581131119. S2CID 13954359.

[38] "Open array parameters". www.freepascal.org. Retrieved 20 January 2024.

[Java_is_Pass-by-Value,_Dammit!-39] "Java is Pass-by-Value, Dammit!". 16 May 2001. Retrieved 2016-12-24.

[40] Coenen, Frans. "PARAMETER PASSING". cgi.csc.liv.ac.uk. Retrieved 22 January 2024.

[41] "Call by Reference, Aliasing Issues" (PDF). MPRI Course 2-36-1: Proof of Program (Lecture notes). p. 53. Archived from the original (PDF) on 25 June 2024.

[42] Ada 2022 Language Reference Manual (PDF). 13 October 2023. p. 215.

[43] Barnes, John (2013). Ada 2012 rationale: the language, the standard libraries (PDF). Heidelberg: Springer. pp. 15–16, 87–88. ISBN 978-3-642-45210-9.

[rfc5531-44] Thurlow, Robert (May 2009). "RPC: Remote Procedure Call Protocol Specification Version 2". tools.ietf.org. IETF. Retrieved 7 April 2018.

[Lundh_Call_Object-45] Lundh, Fredrik. "Call by Object". Effbot.org. Archived from the original on 2011-05-19. Retrieved 2011-05-19.

[46] Jones, Rhys Price (2010). "Is Scheme call-by-value?". CS 145 Programming Languages Lab 9: Parameter Passing. George Washington University. Archived from the original on 16 October 2014. Retrieved 20 January 2024.

[47] "Tcl Library Procedures - Tcl_Obj manual page". www.tcl.tk.

[CA1021-48] "CA1021: Avoid out parameters". Microsoft. 15 November 2016.

[49] Leo, Ray (November 1996). Little C++ (Made Easy). LeoSudo Inc. pp. 79–80. ISBN 978-0-9654634-1-6.

[50] Dandamudi, Sivarama P. (15 July 2005). Guide to Assembly Language Programming in Linux. Springer Science & Business Media. p. 232. ISBN 978-0-387-25897-3.

[51] Srivastava, S. K.; Srivastava, Deepali (6 June 2018). C in Depth. BPB Publications. p. 206. ISBN 978-93-87284-94-4.

[52] "Mutable Variables and Reference Types". okmij.org. Retrieved 20 January 2024.

[53] Vermeir, Dirk (28 June 2011). Multi-Paradigm Programming using C++. Springer Science & Business Media. pp. 10–11. ISBN 978-1-4471-0311-0.

[54] McCollin, Thomas Gwynfryn; Morell, Tobias. "A Game of Paradigms: A Usability Study of Functional Idioms in Gameplay Programming" (PDF). Aalborg University. p. 6. Retrieved 11 January 2022.

[Schauser-55] Schauser, Klaus E.; Goldstein, Seth C. (1995). "How much non-strictness do lenient programs require?" (PDF). Proceedings of the seventh international conference on Functional programming languages and computer architecture - FPCA '95. pp. 216–225. doi:10.1145/224164.224208. ISBN 0897917197. S2CID 2045943. Retrieved 7 January 2022.

[Optimistic_Evaluation-56] Ennals, Robert; Peyton Jones, Simon (August 2003). Optimistic Evaluation: a fast evaluation strategy for non-strict programs. International Conference on Functional Programming. ACM Press. Archived from the original on 22 August 2025.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

Strategy	Evaluation Timing	Memory Usage	Side-Effect Handling	Termination Guarantees	Example Languages
Call by Value	Eager evaluation of arguments before function call.	Copies the value, requiring additional space for the local copy.	No side effects on actual parameters; modifications affect only the local copy.	Strict: May fail to terminate if an argument expression diverges, even if the result would terminate without it.	C, Java (primitives) ^[15] ^[16]
Call by Reference	Arguments evaluated before call; passes location.	Shares memory location; no extra copy.	Allows modification of actual parameters through aliases.	Strict: Similar to call by value; evaluates arguments eagerly.	Fortran, C++ (references), Ada (in out) ^[15] ^[17]
Call by Copy-Restore	Copy in before call; copy out on return.	Temporary local copy during execution.	Updates actual on return; potential issues with aliases.	Strict: Evaluates arguments eagerly.	Ada (for some modes) ^[15] ^[17]
Call by Sharing	Passes reference to the object at call time.	Shares the reference; no deep copy for structures.	Modifications affect the shared object.	Strict: Evaluates arguments before passing reference.	Java (objects), Lisp ^[17] ^[18]
Call by Name	Lazy: reevaluates argument expression each use.	Thunk storage for delayed evaluation; potential multiple computations.	Side effects occur each reevaluation; can affect actuals.	Non-strict: Terminates whenever a terminating reduction strategy does; avoids evaluating unused args.	Algol 60 ^[15] ^[16] ^[17]
Call by Need	Lazy: evaluates argument once on first use, memos result.	Stores thunk and result after first evaluation; avoids recomputation.	Typically read-only after evaluation; no multiple side effects.	Non-strict: Like call by name, but more efficient; terminates if possible.	Haskell ^[15] ^[16]

History

Evaluation strategy

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Evaluation strategy

Example

Table

Evaluation orders

Strict evaluation

Non-strict evaluation

Comparison of applicative order and normal order evaluation

Strict binding strategies

Call by value

Semantic drift

Call by reference

Call by copy-restore

Call by sharing

Call by address

Call by unification

Non-strict binding strategies

Call by name

Call by need

Call by macro expansion

Call by future

Optimistic evaluation

See also

References

Further reading

External links