Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Partial Evaluation

Aliases: Partial Deduction

Categories: Automatic Programming

Author(s): Frank van Harmelen

The main goal of partial evaluation is to perform as much of the computation in a program as possible by using a partial specification of the input values of the program. The theoretical foundation for partial evaluation is Kleene's S-M-N theorem from Recursive Function Theory. The partial evaluation algorithm takes as its input a function (program) definition, together with a partial specification of the input of the program, and produces a new version of the program that is specialised for the particular input values. The new version of the program will then be less general but more efficient then the original version. The partial evaluation algorithm works by symbolically evaluating the input program while in the mean-time trying to: (i) propagate constant values through the program code, (ii) unfold procedure calls, and (iii) branch out conditional parts of the code. If the input program is logical, then the symbolic evaluation of the program becomes the construction of the proof tree corresponding to the execution of the program. In recent years partial evaluation in Logic Programming has attracted particular attention in connection with meta-programming as an optimisation technique. See also Program Transformation.



Add Comment

No comments.