Efficient Goal Directed Bottom-up Evaluation of Logic Programs

The Journal of Logic Programming; 38 (3): 354-370, 1999

Abstract:

This paper introduces a new strategy for the efficient goal directed bottom-up evaluation of logic programs. Instead of combining a standard bottom-up evaluation strategy with a Magic-set transformation, the evaluation strategy is specialized for the application to Magic-set programs which are characterized by clause bodies with a high degree of overlapping. The approach is similar to other techniques which avoid re-computation by maintaining and reusing partial solutions to clause bodies. However, the overhead is considerably reduced as these are maintained implicitly by the underlying Prolog implementation. The technique is presented as a simple meta-interpreter for goal directed bottom-up evaluation. No Magic-set transformation is involved as the dependencies between calls and answers are expressed directly within the interpreter. The proposed technique has been implemented and shown to provide substantial speed-ups in applications of semantic based program analysis based on bottom-up evaluation.

Available: bibtex entry compressed postscript

Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel
mcodish@cs.bgu.ac.il