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
 |
(1)
|
This program calculates 
for positive integers. If 
, then partial evaluation reduces this program to the following:
 |
(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.
