A Unified Approach to Logic Program Evaluation

Abstract

The Prolog evaluation algorithm has become the standard for logic program evaluation, and bottom-up methods have long been considered impractical because they compute irrelevant facts. Recently, however, bottom-up evaluation algorithms that retain the focusing property of top-down evaluation have been proposed, and in view of these algorithms the choice between top-down and bottom-up methods needs to be re-examined. In order to motivate a closer look at bottom-up methods, we identify certain classes of logic programs for which bottom-up evaluation provides polynomial time evaluation algorithms where Prolog takes exponential time. We also demonstrate that techniques such as predicate factoring can provide further O(n) improvement, when they are applicable. We argue that no one evaluation method is uniformly preferable, and suggest that a choice of the appropriate method must be made by the compiler based on the given program. We present several results that shed light on this choice. The bottom-up approach can be refined in a number of ways, and we show how various results in the literature can be combined to provide a coherent evaluation framework. Further, we indicate how ideas in the tabulation literature for functional programs can be adapted to improve the memory utilization of bottom-up methods. We also consider the program transformation techniques pioneered by Burstall and Darlington, and study their relationship to deductive database program transformations such as Magic Templates. The comparison indicates that the bottom-up approach, with the refinements discussed in the paper, often achieves the same gains as these sophisticated transformation systems, and thus illustrates the power of the approach. To keep this paper self-contained, we have included brief surveys of all the techniques that we discuss. We have not attempted to be comprehensive in our survey; it is our hope that the reader will be motivated to pursue these ideas in greater detail by following up on the references.