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,
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.
| 1958 |
| 1960 |
| 1960 |
| 1962 |
| 1965; Here: sect.5.8, p.32 |
| 1971 |
| 1974 |
| 1985 |
| 1985 |
print(x, end="")
return x
print(f(1) + f(2))
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.
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.
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. Conditional expressions similarly use non-strict evaluation - only one of the branches is evaluated.
procedure PrintArray(a: Array of integer);
var
Procedure Modify(Row : Array of integer);
begin
Var
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.
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. For example in Fortran:
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:
where an explicit Box type must be used to introduce a handle. Java is call-by-sharing but not call-by-reference.
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. For example, Ada specifies that the copy-out assignment for each or parameter occurs in an arbitrary order. From the following program (illegal in Ada 2012) it can be seen that the behavior of GNAT is to copy in left-to-right order on return:
procedure Test_Copy_Restore is
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 parameter in Ada as opposed to an parameter), this evaluation strategy may be called "call by result".
This strategy has gained attention in multiprocessing and remote procedure calls, as unlike call-by-reference it does not require frequent communication between threads of execution for variable access.
The technique was first noted by Barbara Liskov in 1974 for the CLU language. It is used by many modern languages such as Python (the shared values being called "objects"), Java (objects), Ruby (objects), JavaScript (objects), Scheme (data structures such as vectors), 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). 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.
For , 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 output parameter: the parameter is not assigned to (the argument is not overwritten and object identity is not changed), but the object (argument) is mutated.
For example, in Python, lists are mutable and passed with call by sharing, so:
m: listint =
f(m)
print(m)
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 :
m: listint =
f(m)
print(m) #
void swap(int* a, int* b) {
int main() {
Some authors treat & as part of the syntax of calling . Under this view, C supports the call-by-reference parameter passing strategy. Other authors take a differing view that the presented implementation of in C is only a simulation of call-by-reference using pointers. 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, for example this program ( and have been added to highlight the similarities to the Java call-by-sharing program above):
int read(int* p) {
void assign(int* p, int v) {
void swap(int* a, int* b) {
int main() {
Because in this program, 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 to be declared and used with a very lightweight "reference" syntax:
int main() {
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-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.
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 Mutable object) 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.
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.
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
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. However, call-by-future may perform unnecessary speculative work compared to call-by-need, such as deeply evaluating a lazy data structure. This can be avoided by using lazy futures that do not start computation until it is certain the value is needed.
Comparison of applicative order and normal order evaluation
Strict binding strategies
Call by value
i: Integer;
begin
for i := Low(a) to High(a) do
Write(a[i]);
WriteLn();
end;
PrintArray(Row); // 123
Row[1] := 4;
PrintArray(Row); // 143
end;
A : Array of integer;
begin
A := [1,2,3];
PrintArray(A); // 123
Modify(A);
PrintArray(A); // 123
end.
Semantic drift
Call by reference
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
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
}
}
Call by copy-restore
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
Call by sharing
l.append(1)
l = l + [1]
print(l) # [1]
Call by address
int temp = *a;
*a = *b;
*b = temp;
}
int a = 1;
int b = 2;
swap(&a, &b);
printf("%d %d\n", a, b); // 2 1
return 0;
}
return *p;
}
*p = v;
}
int temp_storage;
int* temp = &temp_storage;
assign(temp, read(a));
assign(a, read(b));
assign(b, read(temp));
}
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;
}
int temp = a;
a = b;
b = temp;
}
int a = 1;
int b = 2;
swap(a, b);
std::println("{} {}", a, b); // 2 1
return 0;
}
Call by unification
Non-strict binding strategies
Call by name
Call by need
Call by macro expansion
Call by future
Optimistic evaluation
See also
Further reading
External links
|
|