partial evaluation


Also found in: Acronyms, Wikipedia.

partial evaluation

(compiler, algorithm)
(Or "specialisation") An optimisation technique where the compiler evaluates some subexpressions at compile-time. For example,

pow x 0 = 1 pow x n = if even n then pxn2 * pxn2 else x * pow x (n-1) where pxn2 = pow x (n/2) f x = pow x 5

Since n is known we can specialise pow in its second argument and unfold the recursive calls:

pow5 x = x * x4 where x4 = x2 * x2 x2 = x * x f x = pow5 x

pow5 is known as the residual. We could now also unfold pow5 giving:

f x = x * x4 where x4 = x2 * x2 x2 = x * x

It is important that the partial evaluation algorithm should terminate. This is not guaranteed in the presence of recursive function definitions. For example, if partial evaluation were applied to the right hand side of the second clause for pow above, it would never terminate because the value of n is not known.

Partial evaluation might change the termination properties of the program if, for example, the expression (x * 0) was reduced to 0 it would terminate even if x (and thus x * 0) did not.

It may be necessary to reorder an expression to partially evaluate it, e.g.

f x y = (x + y) + 1 g z = f 3 z

If we rewrite f:

f x y = (x + 1) + y

then the expression x+1 becomes a constant for the function g and we can say

g z = f 3 z = (3 + 1) + z = 4 + z

Partial evaluation of built-in functions applied to constant arguments is known as constant folding.

See also full laziness.
References in periodicals archive ?
for section 6 (mobile ultrasounds) prefers to sponsor an extended warranty period, a maximum of 60 months, the length of the extended warranty period for part 6 is the subject of a tender and partial evaluation criterion for this part of the subject contract.
Today's public accounts committee report said the DfT ``only has a partial evaluation of what light rail has deliveredThe committee said that although light rail and tram systems had improved the quality and choice of public transport, they had not delivered all of their anticipated benefits.
2) Use partial evaluation, an automatic program transformation, to turn the general parser into a generator of efficient parsers.
alpha]], we define the crossover partial evaluation function cff([C.
Such a specialization is what partial evaluation is all about.
For the student of criminology it only offers a snapshot of policies and programmes; for the practitioner it only offers a partial evaluation of `what works'; for the researcher there is insufficient detail of evaluation methodologies to be of much assistance.
For the ultimate goal of an intelligent programming system, we tried to develop component technologies such as partial evaluation, program transformation, program verification, and algorithmic debugging.
For each agent, the subgroup on cancer in humans proposes a partial evaluation of the human evidence, and the subgroup on cancer in experimental animals proposes a partial evaluation of the animal evidence (Figure 2).
In this article, we present a partial evaluation scheme for functional logic languages based on an automatic unfolding algorithm which builds narrowing trees.
Workshops on Partial Evaluation and Semantics-Based Program Manipulation, Programming Language ML and its Applications, and Continuations follow the main conference.

Full browser ?