dict.org

The DICT Development Group


Search for:
Search type:
Database:

Database copyright information
Server information


1 definition found
 for partial evaluation
From The Free On-line Dictionary of Computing (30 December 2018) :

  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)
  

Contact=webmaster@dict.org Specification=RFC 2229