Efficient goal directed bottom-up evaluation of logic programs

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 strate gy is specialized for the application to Magic-set programs which are chara cterized by clause bodies with a high degree of overlapping. The approach i s similar to other techniques which avoid re-computation by maintaining and reusing partial solutions to clause bodies. However, the overhead is consi derably reduced as these are maintained implicitly by the underlying Prolog implementation. The technique is presented as a simple meta-interpreter fo r goal directed bottom-up evaluation. No Magic-set transformation is involv ed as the dependencies between calls and answers are expressed directly wit hin 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. (C) 1999 Elsevier Science Inc. All rights reserved.