partial evaluation

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)