partial evaluation
<compiler, algorithm> (Or "specialisation") An optimisation technique
where the compiler evaluates some subexpressions at compiletime. For example,
pow x 0 = 1
pow x n = if even n
then pxn2 * pxn2
else x * pow x (n1)
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 builtin functions applied to constant arguments is
known as constant folding.
See also full laziness.
(19990525)
Nearby terms:
Parsley « Partial Differential Equation LANguage «
partial equivalence relation « partial evaluation
» partial function » partial key » partially ordered
set
