Abstract
Tabled evaluations ensure termination of logic 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 uses answer resolution. This use of answer resolution prevents infinite looping which happens in SLD. Given the asynchronicity of answer generation and answer return, tabling systems face an important scheduling choice not present in traditional top-down evaluation: How does the order of returning answers to consuming subgoals affect program efficiency.
This paper investigates alternate scheduling strategies for tabling in a WAM implementation, the SLG-WAM. The original SLG-WAM had a simple mechanism of scheduling answers to be returned to callers which 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 non-monotonic reasoning and when combined with answer subsumption can improve the performance of some programs by arbitrary amounts.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Aït-Kaci. WAM: A Tutorial Reconstruction. MIT Press, 1991.
C. Beeri and R. Ramakrishnan. On the Power of Magic. Journal of Logic Programming, 10(3):255–299, 1991.
W. Chen and D.S. Warren. Tabled Evaluation with Delaying for General Logic Programs. JACM, 43(1):20–74, January 1996.
S. Dawson, C.R. Ramakrishnan, and D.S. Warren. Practical Program Analysis Using General Purpose Logic Programming Systems — A Case Study. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), pages 117–125. ACM, 1996.
C. Fan and S. Dietrich. Extension Table Built-ins for Prolo. Software-Practice and Experience, 22(7):573–597, July 1992.
J. Freire, R. Hu, T. Swift, and D.S. Warren. Exploiting Parallelism in Tabled Evaluations. In 7th International Symposium, PLILP 95 — LNCS Vol. 982. Springer-Verlag, 1995.
J. Freire, T. Swift, and D.S. Warren. Batched answers: An alternative strategy for tabled evaluations. Technical Report 96/2, Department of Computer Science, State University of New York at Stony Brook, 1996.
J. Freire, T. Swift, and D.S. Warren. Taking I/O seriously: Resolution reconsidered for disk. Technical Report 96/4, Department of Computer Science, State University of New York at Stony Brook, 1996.
J. Jaffar and J.-L. Lassez. Constraint logic programming. In Proceedings of the 14th Annual ACM Symposium on Principles of Programming Languages (POPL), pages 111–119, 1987.
G. Janssens, M. Bruynooghe, and V. Dumortier. A Blueprint for an Abstract Machine for Abstract Interpretation of (Constraint) Logic Programs. In Proceedings of the International Symposium on Logic Programming (ILPS), 1995.
D. E. Knuth. The Stanford GraphBase: A Platform for Combinatorial Computing. Addison Wesley, 1993.
G. Köstler, W. Kiessling, H. Thöne, and U. Güntzer. Fixpoint iteration with subsumption in deductive databases. Journal of Intelligent Information Systems (JIIS), 4(2):123–148, March 1995.
T.C. Przymusinski. Every logic program has a natural stratification and an iterated least fixed point model. In Proceedings of the ACM Symposium on Principle of Database Systems (PODS), pages 11–21, 1989.
T. Swift. Efficient Evaluation of Normal Logic Programs. PhD thesis, Department of Computer Science, State University of New York at Stony Brook, 1994.
T. Swift and D. S. Warren. An Abstract Machine for SLG Resolution: Definite Programs. In Proceedings of the International Symposium on Logic Programming (ILPS), pages 633–654, 1994.
T. Swift and D. S. Warren. Analysis of sequential SLG evaluation. In Proceedings of the International Symposium on Logic Programming (ILPS), pages 219–238, 1994.
A. van Gelder. Foundations of Aggregation in Deductive Databases. In Proceedings of the International Conference on Deductive and Object-Oriented Databases (DOOD), pages 13–34, 1993.
A. van Gelder, K.A. Ross, and J.S. Schlipf. Unfounded sets and well-founded semantics for general logic programs. JACM, 38(3):620–650, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Freire, J., Swift, T., Warren, D.S. (1996). Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. In: Kuchen, H., Doaitse Swierstra, S. (eds) Programming Languages: Implementations, Logics, and Programs. PLILP 1996. Lecture Notes in Computer Science, vol 1140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61756-6_89
Download citation
DOI: https://doi.org/10.1007/3-540-61756-6_89
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61756-3
Online ISBN: 978-3-540-70654-0
eBook Packages: Springer Book Archive