TOPICS
Search

Partial Evaluation


Partial evaluation is a branch of computer science studying program transformation via specialization. Any function can be specialized by fixing one or more of its inputs to a particular values. The number of inputs to the program resulting from specialization is the initial number of inputs minus the number of inputs whose values are constants. These specialized programs are also called residual programs.

Kleene's s-m-n theorem established a theoretical possibility of function specialization. Partial evaluation applies this idea to computer programs. Note that Kleene's theorem does not address the efficiency of specialized functions whereas the goal of partial evaluation is program optimization.

Partial evaluation is accomplished by detecting code fragments depending exclusively on specialized variables whose values are fixed and by symbolically precomputing these fragments. The residual program will run faster because it lacks the aforementioned fragments.

As an example, consider the program

 f(x,n)={1   if n=0; square(f(x,1/2n))   if n is even; xf(x,n-1)   otherwise.
(1)

This program calculates x^n for positive integers. If n=5, then partial evaluation reduces this program to the following:

 f(x)=xsquare(square(x))
(2)

(Jones et al. 1993).

Symbolic computations implementing partial evaluation apply to both expressions and program control structures. These symbolic computations involve function call and loop unfolding.


See also

Kleene's s-m-n Theorem

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

References

Jones, N. D.; Gomard, C. K.; and Sestoft, P. Partial Evaluation and Automatic Program Generation. Englewood Cliffs, NJ: Prentice Hall, 1993.

Referenced on Wolfram|Alpha

Partial Evaluation

Cite this as:

Sakharov, Alex. "Partial Evaluation." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/PartialEvaluation.html

Subject classifications