Language:
Free Online Dictionary|3Dict

partial evaluation

Source : Free On-Line Dictionary of Computing

partial evaluation
     
         (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)
Sort by alphabet : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z