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.

(1999-05-25)