# 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)

Tagged: p

Read Also:

- Partial-fraction
noun, Algebra. 1. one of the fractions into which a given fraction can be resolved, the sum of such simpler fractions being equal to the given fraction: Partial fractions of 5/(x2−x) are 5/(x−1) and −5/x. noun 1. (maths) one of a set of fractions into which a more complicated fraction can be resolved

- Partial function
A function which is not defined for all arguments of its input type. E.g. f(x) = 1/x if x /= 0. The opposite of a total function. In denotational semantics, a partial function f : D -> C may be represented as a total function ft : D’ -> lift(C) where D’ is a superset […]

- Partialize
[pahr-shuh-lahyz] /ˈpɑr ʃəˌlaɪz/ verb (used with object), partialized, partializing. 1. to bias.

- Partiality
[pahr-shee-al-i-tee, pahr-shal-] /ˌpɑr ʃiˈæl ɪ ti, pɑrˈʃæl-/ noun, plural partialities. 1. the state or character of being . 2. a favorable bias or prejudice: the partiality of parents for their own children. 3. a special fondness, preference, or liking (usually followed by to or for): a partiality for country living. /ˌpɑːʃɪˈælɪtɪ/ noun (pl) -ties 1. […]