Evaluation strategy

From Freepedia

(Redirected from Call-by-value)

An evaluation strategy (or reduction strategy) for a programming language is a set of (usually deterministic) rules for defining the evaluation of expressions under β-reduction. Emphasis is typically placed on functions or operators -- an evaluation strategy defines when and in what order the arguments to a function are evaluated, when they are substituted into the function, and what form that substitution takes. A language may combine several evaluation strategies; for example, C++ combines call-by-value with call-by-reference. Most languages that are predominantly strict use some form of non-strict evaluation for boolean expressions and if-statements.

Contents

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 (and, correspondingly, eager evaluation for mathematical operators).

Applicative order

See applicative-order evaluation.

Image:Mergefrom.gif
It has been suggested that Applicative-order evaluation be merged into this article or section. (Discuss)


Call by value

Call-by-value evaluation is the most common evaluation strategy, used in languages as far-ranging 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 (usually by capture-avoiding substitution or by copying the value into a new memory region). If the function or procedure is able to assign values to its parameters, only the local copy is assigned -- that is, anything passed into a function call is unchanged in the caller's scope when the function returns.

Note that call-by-value does not necessarily mean left-to-right evaluation. While most programming languages that use call-by-value do evaluate function arguments left-to-right, some (such as O'Caml) evaluate functions and their arguments right-to-left.

Call by reference

Call-by-reference evaluation is a form of evaluation used in some languages (for example C++) where variables and certain other values, called l-values, must always refer to some memory location. In these languages, some functions accept only l-values as function arguments. The l-value's address is treated as a reference and passed to the function by value; the function body may then manipulate the contents of the reference cell, changing the value to which the l-value is bound in the caller's scope.

For more information on call-by-reference in C++, see reference (C Plus Plus).

In languages that contain unrestricted pointers instead of or in addition to references, call-by-address is a variant of call-by-reference where the reference is an unrestricted pointer.

Some languages contain a notion of references or pointers as values. ML, for example, has the "ref" constructor; C relies heavily on pointers. In these languages, "call-by-reference" or "call-by-address" may be used to mean passing a reference value or pointer value as an argument to a function.

Call by copy-restore

Call-by-copy-restore or call-by-value-result is a special case of call-by-reference where the provided reference is unique to the caller. If a parameter to a function call is a reference that might be accessible by another thread of execution, its contents are 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").

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. In the presence of side-effects, complete partial evaluation may produce unintended results; for this reason, systems that support partial evaluation tend to do so only for "pure" expressions (expressions without side-effects) 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 sometimes referred to as "lazy". Boolean expressions in many languages use lazy evaluation; in this context it is often called short circuiting. Conditional statements almost always use lazy evaluation -- programmers would be quite surprised if both branches of an "if" were evaluated before one was selected.

Normal order

Normal-order evaluation is the evaluation strategy where the outermost function application (redex) is always reduced (by capture-avoiding substitution), without evaluating the function's argument. It differs from call-by-name in that call-by-name does not evaluate inside the body of an unapplied function.

See normal-order evaluation.

Image:Mergefrom.gif
It has been suggested that Normal-order evaluation be merged into this article or section. (Discuss)


Call by name

Call-by-name evaluation is rarely implemented directly, but frequently used in considering theoretical properties of programs and programming languages. In call-by-name evaluation, the arguments to functions are not evaluated at all -- rather, function arguments are substituted directly into the function body using capture-avoiding substitution. If the argument is not used in the evaluation of the function, it is never evaluated; if the argument is used several times, it is re-evaluated each time. For this reason, real-world languages with call-by-name semantics tend to be implemented using call-by-need.

Proponents of call-by-name and equivalent strategies tend to favor it because call-by-name evaluation always yields a value when a value exists, whereas call-by-value may not terminate if the function's argument is a non-terminating computation that is not needed to evaluate the function. Opponents of call-by-name claim that it is significantly slower when the function argument is used, and that in practice this is almost always the case.

Note that because evaluation of expressions may happen arbitrarily far into a computation, languages using call-by-need generally do not support computational effects (such as mutation) except through the use of monads. This eliminates any unexpected behavior from variables whose values change prior to their delayed evaluation.

Call by need

Call-by-need is a memoized version of call-by-name where, if the function argument is evaluated, that value is stored for subsequent uses. In a "pure" (effect-free) setting, this produces the same results as call-by-name; when the function argument is used two or more times, call-by-need is almost always faster.

Haskell is perhaps the most well-known language that uses call-by-need evaluation.

Call by macro expansion

Call-by-macro-expansion is similar to call-by-name, but uses textual substitution rather than capture-avoiding substitution. Macros are generally best used for very small tasks where this difference can be easily taken into account by the programmer. With uncautious use, however, macro substitution may result in variable capture; this effect is put to appropriate use in the writing of obfuscated code, but generally leads to undesired behavior elsewhere.

Nondeterministic strategies

Full β-reduction

Under full β-reduction, any function application may be reduced (substituting the function's argument into the function using capture-avoiding substitution) at any time. This may be done even within the body of an unapplied function.

Call by future

Call-by-future (or parallel call-by-name) is like call-by-need, except that the function's argument may be evaluated in parallel with the function body (rather than only if used). The two threads of execution synchronize when the argument is needed in the evaluation of the function body; if the argument is never used, the argument thread may be killed.

Optimistic evaluation

Optimistic evaluation is another variant of call-by-need in which the function's argument is partially evaluated for some amount of time (which may be adjusted at runtime), after which evaluation is aborted and the function is applied using call-by-need. This approach avoids some of the runtime expense of call-by-need, while still retaining the desired termination characteristics.

References

Retrieved from "http://en.freepedia.org/Evaluation_strategy.html"


Views
Personal tools
Similar Links