Since the beginning of the 80's numerous non-incremental applications (e.g. optimisation, reformulation and transformation) of the partial evaluation of logic programs, which is now called partial deduction, there have been found . An incremental application has not yet been fully investigated since there has been a lack of partial deduction mechanisms.
This work describes a new incremental variant of partial deduction. The goal was to have a method which does not merely allow for adding clauses but also dleting clauses from the partially evaluated program.
Starting from this aim we analyse the expansion and contraction operators being necessary for processing definite, non-recursive logic. We derive the corresponding operators, discuss their implementation in PROLOG as well as the possible extension to recursive and normal logic programs.
The usage of "predicate dependency graphs" has turned out to be crucial for an efficient implementation of incremental partial deduction. These graphs allow in an efficient way to identify the clauses effected by a change. To achieve this we incrementalised an highly efficient algorithm to compute the transitive closure.
We not only showed that IPD is sound and complete w.r.t. the results of partial deduction for definite logic programs, but also analysed the complexity of this approach and the incremental computation of transitive closure. We argued for their efficiency empirically.
This work does not only show that incremental methods for partial deduction can be developed, but also that we can relate their theoretical foundation to the theory of partial deduction. We further show which circumstances favour an incremental computation to a non-incremental one.