Evaluation strategy

From Wikipedia for FEVERv2
(Redirected from Call-by-name)
Jump to navigation Jump to search

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. Evaluation strategy_sentence_0

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. Evaluation strategy_sentence_1

The notion of reduction strategy in lambda calculus is similar but distinct. Evaluation strategy_sentence_2

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. Evaluation strategy_sentence_3

Some languages, especially lower-level languages such as C++, combine several notions of parameter passing. Evaluation strategy_sentence_4

Historically, call by value and call by name date back to ALGOL 60, which was designed in the late 1950s. Evaluation strategy_sentence_5

Call by reference is used by PL/I and some Fortran systems. Evaluation strategy_sentence_6

Purely functional languages like Haskell, as well as non-purely functional languages like R, use call by need. Evaluation strategy_sentence_7

Evaluation strategy is specified by the programming language definition, and is not a function of any specific implementation. Evaluation strategy_sentence_8

Strict evaluation Evaluation strategy_section_0

Main article: Eager evaluation Evaluation strategy_sentence_9

In strict evaluation, the arguments to a function are always evaluated completely before the function is applied. Evaluation strategy_sentence_10

Under Church encoding, eager evaluation of operators maps to strict evaluation of functions; for this reason, strict evaluation is sometimes called "eager". Evaluation strategy_sentence_11

Most existing programming languages use strict evaluation for functions. Evaluation strategy_sentence_12

Applicative order Evaluation strategy_section_1

Applicative order evaluation is an evaluation strategy in which an expression is evaluated by repeatedly evaluating its leftmost innermost reducible expression. Evaluation strategy_sentence_13

This means that a function's arguments are evaluated before the function is applied. Evaluation strategy_sentence_14

Call by value Evaluation strategy_section_2

Call by value (also known as pass by value) is the most common evaluation strategy, used in languages as different as C and Scheme. Evaluation strategy_sentence_15

In call by value, the argument expression is evaluated, and the resulting value is bound to the corresponding variable in the function (frequently by copying the value into a new memory region). Evaluation strategy_sentence_16

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. Evaluation strategy_sentence_17

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. Evaluation strategy_sentence_18

While many programming languages (such as Common Lisp, Eiffel and Java) that use call by value evaluate function arguments left-to-right, some evaluate functions and their arguments right-to-left, and others (such as Scheme, OCaml and C) do not specify order. Evaluation strategy_sentence_19

Implicit limitations Evaluation strategy_section_3

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. Evaluation strategy_sentence_20

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. Evaluation strategy_sentence_21

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. Evaluation strategy_sentence_22

Exactly where the boundary is drawn between proper values and data structures masquerading as such is often hard to predict. Evaluation strategy_sentence_23

In C, an array (of which strings are special cases) is a data structure but the name of an array is treated as (has as value) 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. Evaluation strategy_sentence_24

In Maple, a vector is a special case of a table and therefore a data structure, but a list (which gets rendered and can be indexed in exactly the same way) is a value. Evaluation strategy_sentence_25

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. Evaluation strategy_sentence_26

Modifications made via the data structure are reflected back to the value representation and vice versa. Evaluation strategy_sentence_27

The description "call by value where the value is a reference" is common (but should not be understood as being call by reference); another term is call by sharing. Evaluation strategy_sentence_28

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 (except if it's actually a reference to a structure), potentially causing serious performance degradation, and mutations to the structure are invisible to the caller. Evaluation strategy_sentence_29

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. Evaluation strategy_sentence_30

Call by reference Evaluation strategy_section_4

Call by reference (or pass 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. Evaluation strategy_sentence_31

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. Evaluation strategy_sentence_32

Call by reference can therefore be used to provide an additional channel of communication between the called function and the calling function. Evaluation strategy_sentence_33

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. Evaluation strategy_sentence_34

A simple litmus test for whether a language supports call-by-reference semantics is if it's possible to write a traditional swap(a, b) function in the language. Evaluation strategy_sentence_35

Many languages support call by reference in some form, but few use it by default. Evaluation strategy_sentence_36

FORTRAN II is an early example of a call-by-reference language. Evaluation strategy_sentence_37

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. Evaluation strategy_sentence_38

C++ additionally offers call by reference to const. Evaluation strategy_sentence_39

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 (objects that refer to other objects), such as pointers (objects representing the memory addresses of other objects). Evaluation strategy_sentence_40

Languages such as C, ML and Rust use this technique. Evaluation strategy_sentence_41

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". Evaluation strategy_sentence_42

In ML, references are type- and memory-safe, similar to Rust. Evaluation strategy_sentence_43

A similar effect is achieved by call by sharing (passing an object, which can then be mutated), used in languages like Java, Python, and Ruby. Evaluation strategy_sentence_44

In purely functional languages there is typically no semantic difference between the two strategies (since their data structures are immutable, so there is no possibility for a function to modify any of its arguments), so they are typically described as call by value even though implementations frequently use call by reference internally for the efficiency benefits. Evaluation strategy_sentence_45

Following is an example that demonstrates call by reference in the E programming language: Evaluation strategy_sentence_46

Following is an example of call by address that simulates call by reference in C: Evaluation strategy_sentence_47

Call by sharing Evaluation strategy_section_5

Call by sharing (also known as "call by object" or "call by object-sharing") is an evaluation strategy first noted by Barbara Liskov in 1974 for the CLU language. Evaluation strategy_sentence_48

It is used by languages such as Python, Java (for object references), Ruby, JavaScript, Scheme, OCaml, AppleScript, and many others. Evaluation strategy_sentence_49

However, the term "call by sharing" is not in common use; the terminology is inconsistent across different sources. Evaluation strategy_sentence_50

For example, in the Java community, they say that Java is call by value. Evaluation strategy_sentence_51

Call by sharing implies that values in the language are based on objects rather than primitive types, i.e., that all values are "boxed". Evaluation strategy_sentence_52

Because they are boxed they can be said to pass by copy of reference (where primitives are boxed before passing and unboxed at called function). Evaluation strategy_sentence_53

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. Evaluation strategy_sentence_54

And it is not call by reference because access is not given to the variables of the caller, but merely to certain objects". Evaluation strategy_sentence_55

So, for example, if a variable was passed, it is not possible to simulate an assignment on that variable in the callee's scope. Evaluation strategy_sentence_56

However, since the function has access to the same object as the caller (no copy is made), 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. Evaluation strategy_sentence_57

Mutations of a mutable object within the function are visible to the caller because the object is not copied or cloned—it is shared. Evaluation strategy_sentence_58

For example, in Python, lists are mutable, so: Evaluation strategy_sentence_59

outputs because the append method modifies the object on which it is called. Evaluation strategy_sentence_60

Assignments within a function are not noticeable to the caller, because, in these languages, passing the variable only means passing (access to) the actual object referred to by the variable, not access to the original (caller's) variable. Evaluation strategy_sentence_61

Since the rebound variable only exists within the scope of the function, the counterpart in the caller retains its original binding. Evaluation strategy_sentence_62

Compare the Python mutation above with the code below, which binds the formal argument to a new object: Evaluation strategy_sentence_63

outputs [], because the statement list = reassigns a new list to the variable rather than to the location it references. Evaluation strategy_sentence_64

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. Evaluation strategy_sentence_65

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. Evaluation strategy_sentence_66

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. Evaluation strategy_sentence_67

Call by copy-restore Evaluation strategy_section_6

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 special case of call by reference where the provided reference is unique to the caller. Evaluation strategy_sentence_68

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 ("restored"). Evaluation strategy_sentence_69

The semantics of call by copy-restore also differ from those of call by reference, where two or more function arguments alias one another (i.e., point to the same variable in the caller's environment). Evaluation strategy_sentence_70

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? Evaluation strategy_sentence_71

When the reference is passed to the callee uninitialized, this evaluation strategy may be called "call by result". Evaluation strategy_sentence_72

Partial evaluation Evaluation strategy_section_7

Main article: Partial evaluation Evaluation strategy_sentence_73

In partial evaluation, evaluation may continue into the body of a function that has not been applied. Evaluation strategy_sentence_74

Any sub-expressions that do not contain unbound variables are evaluated, and function applications whose argument values are known may be reduced. Evaluation strategy_sentence_75

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 (i.e., those without side effects) within functions. Evaluation strategy_sentence_76

Non-strict evaluation Evaluation strategy_section_8

Nondeterministic strategies Evaluation strategy_section_9

Full β-reduction Evaluation strategy_section_10

Under "full β-reduction", any function application may be reduced (substituting the function's argument into the function using capture-avoiding substitution) at any time. Evaluation strategy_sentence_77

This may be done even within the body of an unapplied function. Evaluation strategy_sentence_78

Call by future Evaluation strategy_section_11

See also: Futures and promises Evaluation strategy_sentence_79

"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. Evaluation strategy_sentence_80

When the promise's value is needed, the main program blocks until the promise has a value (the promise or one of the promises finishes computing, if it has not already completed by then). Evaluation strategy_sentence_81

This 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. Evaluation strategy_sentence_82

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. Evaluation strategy_sentence_83

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. Evaluation strategy_sentence_84

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. Evaluation strategy_sentence_85

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. Evaluation strategy_sentence_86

Optimistic evaluation Evaluation strategy_section_12

Optimistic evaluation is another call-by-need variant where the function's argument is partially evaluated for some amount of time (which may be adjusted at runtime). Evaluation strategy_sentence_87

After that time has passed, evaluation is aborted and the function is applied using call by need. Evaluation strategy_sentence_88

This approach avoids some the call-by-need strategy's runtime expenses while retaining desired termination characteristics. Evaluation strategy_sentence_89

See also Evaluation strategy_section_13

Evaluation strategy_unordered_list_0


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Evaluation strategy.