Catalogue of Artificial Intelligence Techniques
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.
- Lakhotia, A. and Sterling, L. , ProMix: a Prolog Partial Evaluator System, The Practice of Prolog (Sterling, L.
, ed.), MIT Press, 1990, pp.137--179.