|
The performance of logic programs can be significantly improved by reducing
nondeterminism in their evaluation using techniques for early pruning of computation paths
that would eventually fail. Using static information gleaned from the program, we can
identify (simple) conditions that must hold for certain computation paths to succeed, and
test them before searching along those paths. However, naive introduction of such tests
can actually lead to performance degradation since tests may be repeated along a branch,
and also be cause the tests themselves may create additional choice points. We therefore
develop a program transformation algorithm that enables us to introduce only those tests
that facilitate early pruning of failure branches, while providing formal guarantees
against any performance degradation. Our transformation is based on a novel polyvariant
program specialization technique that can reason about the relative execution times of the
original and transformed programs. We present results of a prototype implementation that
shows the effectiveness of our approach.
|