Evaluation strategy
Encyclopedia : E : EV : EVA : Evaluation strategy
| Programming evaluation |
|---|
|
Eager Function Lazy Minimal Partial Remote Strategy |
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
Applicative order (or leftmost innermost) evaluation refers to an evaluation strategy in which the arguments of a function are evaluated from left to right in a post-order traversal of reducible expressions ([redex]es). Unlike call-by-value, applicative order evaluation reduces terms within a function body as much as possible before the function is applied.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.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 (such as O'Caml) evaluate functions and their arguments right-to-left.
Call by reference
In call-by-reference evaluation, a function is passed an implicit reference to its argument rather than the argument value itself. If the function is able to modify such a parameter, then any changes it makes will be visible to the caller as well. If the argument expression is an L-value, its address is used. Otherwise, a temporary object is constructed by the caller and a reference to this object is passed; the object is then discarded when the function returns.Some languages contain a notion of references as first-class values. ML, for example, has the "ref" constructor; references in C++ may also be created explicitly. In these languages, "call-by-reference" may be used to mean passing a reference value as an argument to a function.
In languages (such as C) 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.
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 (or leftmost outermost) evaluation is the evaluation strategy where the outermost redex is always reduced, applying functions before evaluating function arguments. It differs from call-by-name in that call-by-name does not evaluate inside the body of an unapplied function.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 may lead 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.See also
References
- Harold Abelson and Gerald Jay Sussman. [Structure and Interpretation of Computer Programs], Second Edition. MIT Press, 1996. ISBN 0-262-01153-0.
- Henry G. Baker, Jr. "[The Incremental Garbage Collection of Processes]", with Carl Hewitt, ACM Sigplan Notices 12. August 8, 1977. Pages 55-59.
- Clem Baker-Finch, Clem, David King, Jon Hall, and Phil Trinder. "[An Operational Semantics for Parallel Call-by-Need]", Research report 99/1. Faculty of Mathematics & Computing, The Open University, 1999.
- Robert Ennals and Simon Peyton Jones. "[Optimistic Evaluation: a fast evaluation strategy for non-strict programs]", in ICFP'03. ACM Press, 2003.
- Jocelyn Frechot. "[Partial Evaluation]", documentation for the Compose project. Online, Sept. 25, 2003.
- Bertram Ludäscher. [CSE 130 lecture notes]. January 24, 2001.
- Benjamin C. Pierce. [Types and Programming Languages]. MIT Press, 2002. ISBN 0-262-16209-1.
- P. Sestoft. "[Demonstrating Lambda Calculus Reduction]", in T. Mogensen, D. Schmidt, I. H. Sudburough (editors): The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones. Lecture Notes in Computer Science 2566. Springer-Verlag, 2002. Pages 420-435. ISBN 3540003266
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.