partial evaluation

(compiler, algorithm)(Or "specialisation") An optimisationtechnique where the compiler evaluates some subexpressionsat compile-time. For example,

pow x 0 = 1pow x n = if even nthen pxn2 * pxn2else 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 argumentand unfold the recursive calls:

pow5 x = x * x4 where x4 = x2 * x2x2 = x * xf x = pow5 x

pow5 is known as the residual. We could now also unfold pow5giving:

f x = x * x4 where x4 = x2 * x2x2 = x * x

It is important that the partial evaluation algorithm shouldterminate. This is not guaranteed in the presence ofrecursive function definitions. For example, if partialevaluation were applied to the right hand side of the secondclause for pow above, it would never terminate because thevalue of n is not known.

Partial evaluation might change the termination properties ofthe program if, for example, the expression (x * 0) wasreduced to 0 it would terminate even if x (and thus x * 0) didnot.

It may be necessary to reorder an expression to partiallyevaluate it, e.g.

f x y = (x + y) + 1g 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 gand we can say

g z = f 3 z = (3 + 1) + z = 4 + z

Partial evaluation of built-in functions applied to constantarguments is known as constant folding.

See also full laziness.

单词	partial evaluation
释义	partial evaluation partial evaluation (compiler, algorithm)(Or "specialisation") An optimisationtechnique where the compiler evaluates some subexpressionsat compile-time. For example, pow x 0 = 1pow x n = if even nthen pxn2 * pxn2else 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 argumentand unfold the recursive calls: pow5 x = x * x4 where x4 = x2 * x2x2 = x * xf x = pow5 x pow5 is known as the residual. We could now also unfold pow5giving: f x = x * x4 where x4 = x2 * x2x2 = x * x It is important that the partial evaluation algorithm shouldterminate. This is not guaranteed in the presence ofrecursive function definitions. For example, if partialevaluation were applied to the right hand side of the secondclause for pow above, it would never terminate because thevalue of n is not known. Partial evaluation might change the termination properties ofthe program if, for example, the expression (x * 0) wasreduced to 0 it would terminate even if x (and thus x * 0) didnot. It may be necessary to reorder an expression to partiallyevaluate it, e.g. f x y = (x + y) + 1g 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 gand we can say g z = f 3 z = (3 + 1) + z = 4 + z Partial evaluation of built-in functions applied to constantarguments is known as constant folding. See also full laziness. AcronymsSeePE
随便看	advisory council on social security advisory council on tennessee indian affairs advisory council on the environment advisory council on the misuse of drug advisory council on the misuse of drugs advisory council on the status of women advisory council on unemployment compensation advisory council report advisory counsil advisory experts group on inherent safety advisory fee advisory file advisory group for aerospace research & development advisory group for network issues advisory group for people with disabilities advisory group for rail research and innovation advisory group of applied research advisory group of experts advisory group of experts on decentralization advisory group on alternatives to animal testing in immunobiologicals advisory group on electron devices advisory group on electronic parts advisory group on environmental emergencies advisory group on experimental entertainment advisory group on greenhouse gases