JFLP: Volume 1998, Article 3

The Journal of Functional and Logic Programming

Volume 1998

Article 3

Published by The MIT Press . Copyright 1998 Massachusetts Institute of Technology.

Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.

Beyond Depth-First Strategies:
Improving Tabled Logic Programs through Alternative Scheduling

Juliana Freire , Terrance Swift , and David S. Warren

27 April 1998

Abstract

Tabled evaluation ensures termination for programs with finite models by keeping track of which subgoals have been called. Given several variant subgoals in an evaluation, only the first one encountered will use program-clause resolution; the rest will resolve with the answers generated by the first subgoal. This use of answer resolution prevents infinite looping that sometimes happens in SLD. Because answers that are produced in one path of the computation may be consumed, asynchronously, in others, tabling systems face an important scheduling choice not present in traditional top-down evaluation: when to schedule answer resolution.

This paper investigates alternate scheduling strategies for tabling in a WAM implementation, the SLG-WAM. The original SLG-WAM had a simple mechanism for scheduling answer resolution that was expensive in terms of trailing and choice-point creation. We propose here a more sophisticated scheduling strategy, batched scheduling, which reduces the overheads of these operations and provides dramatic space reduction as well as speedups for many programs. We also propose a second strategy, local scheduling, which has applications to nonmonotonic reasoning, and when combined with answer subsumption, can arbitrarily improve the performance of some programs.

The following versions of the article are available:

• Preformatted versions of the article (compressed with gzip )
  • DVI (gzip'ped 45 kb)
  • PostScript (gzip'ped 217 kb)
  • PDF (gzip'ped 289 kb; uncompressed 423 kb)
• Source materials for custom formatting
  • LaTeX ( JFLP-A98-03.tex , gzip'ped 24 kb)
  • BIBTeX ( JFLP-A98-03.bib , gzip'ped 2 kb)
  • 29 EPS-figures ( j9803f.tar.gz , gzip'ped 13 kb) Note: untar before formatting.
  • Parameter settings for custom formatting ( cjropts.tex , 165 bytes)

You can find this article also on the ftp-server of The MIT Press (access may be faster from some sites).

Self citation

    @article{jflp98-03,
      author={Juliana Freire and Terrance Swift and David S. Warren},
      title={Beyond Depth-First Strategies: Improving Tabled Logic Programs through 
            Alternative Scheduling},
      journal={Journal of Functional and Logic Programming},
      volume={1998},
      number={3},
      publisher={The MIT Press},
      month={April},
      year={1998}
    }

Main page