About This Item

Ask the MINDS@UW Librarian

A Unified Approach to Logic Program Evaluation

Show full item record

File(s):

Author(s)
Naughton, Jeffrey F; Ramakrishnan, Raghu
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Date
Mar 15, 2012
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.
Permanent link
http://digital.library.wisc.edu/1793/59208 
Export
Export to RefWorks 
‚Äč

Part of

Show full item record

Search and browse




About MINDS@UW

Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.