Article

Efficient fixpoint computation in linear tabling

Authors:

Taisuke SatoAuthors Info & Claims

PPDP '03: Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming

Pages 275 - 283

https://doi.org/10.1145/888251.888277

Published: 27 August 2003 Publication History

Abstract

Early resolution mechanisms proposed for tabling such as OLDT rely on suspension and resumption of subgoals to compute fixpoints. Recently, a new resolution framework called linear tabling has emerged as an alternative tabling method. The idea of linear tabling is to use iterative computation rather than suspension to compute fixpoints. Although linear tabling is simple, easy to implement, and superior in space efficiency, the current implementations are several times slower than XSB, the state-of-the-art implementation of OLDT, due to re-evaluation of looping subgoals. In this paper, we present a new linear tabling method and propose several optimization techniques for fast computation of fixpoints. The optimization techniques significantly improve the performance by avoiding redundant evaluation of subgoals, re-application of clauses, and reproduction of answers in iterative computation. Our implementation of the method in B-Prolog not only consumes an order of magnitude less stack space than XSB for some programs but also compares favorably well with XSB in speed.

References

[1]

Bancilhon, F., and Ramakrishnan, R. An amateur's introduction to recursive query processing strategies. Proc. of ACM SIGMOD '86 (May 28-30, 1986), 16--52.]]

Digital Library

[2]

Bol, R. N., and Degerstedt, L. Tabulated resolution for the well-founded semantics. Journal of Logic Programming 34, 2 (Feb. 1998), 67--109.]]

[3]

Chen, W., and Warren, D. S. Tabled evaluation with delaying for general logic programs. Journal of the ACM 43, 1 (Jan. 1996), 20--74.]]

Digital Library

[4]

Demoen, B., and Sagonas, K. CAT: The copying approach to tabling. LNCS (PLILP) 1490 (1998), 21--35.]]

Digital Library

[5]

Demoen, B., and Sagonas, K. CHAT: The copy-hybrid approach to tabling. LNCS (PADL) 1551 (1999), 106--121.]]

Digital Library

[6]

Freire, J., Swift, T., and Warren, D. S. Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. LNCS (PLILP) 1140 (1996), 243--257.]]

Digital Library

[7]

Guo, H.-F., and Gupta, G. A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. LNCS (ICLP) 2237 (2001), 181--195.]]

Digital Library

[8]

Lloyd, J. W. Foundation of Logic Programming, 2 ed. Springer-Verlag, 1988.]]

Digital Library

[9]

Michie, D. "memo" functions and machine learning. Nature (Apr. 1968), 19--22.]]

[10]

Przymusinski, T. C. Every logic program has a natural stratification and an iterated least fixed point model. In PODS '89. Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29--31, 1989, Philadelphia, PA (1989), ACM, Ed., ACM Press, pp. 11--21.]]

Digital Library

[11]

Ramakrishnan, C. Model checking with tabled logic programming. In ALP News Letter (2002), ALP.]]

[12]

Rocha, R., Silva, F., and Costa, V. S. On a tabling engine that can exploit or-parallelism. LNCS (ICLP) 2237 (2001), 43--58.]]

Digital Library

[13]

Sagonas, K., and Swift, T. An abstract machine for tabled execution of fixed-order stratified logic programs. ACM Transactions on Programming Languages and Systems 20, 3 (1 May 1998), 586--634.]]

Digital Library

[14]

Shen, Y., Yuan, L., You, J., and Zhou, N. Linear tabulated resolution based on Prolog control strategy. Theory and Practice of Logic Programming (TPLP) 1, 1 (Feb. 2001), 71--103.]]

Digital Library

[15]

Tamaki, H., and Sato, T. OLD resolution with tabulation. In Proceedings of the Third International Conference on Logic Programming (London, 1986), E. Shapiro, Ed., Lecture Notes in Computer Science, Springer-Verlag, pp. 84--98.]]

Digital Library

[16]

Ullman, J. D. Database and Knowledge-Base Systems, vol. 1 & 2. Computer Science Press, 1988.]]

Digital Library

[17]

Uratani, N., Takezawa, T., Matsuo, H., and Morita, C. ATR integrated speech and language database. Technical Report TR-IT-0056, ATR Interpreting Telecommunications Research Laboratories, 1994. In Japanese.]]

[18]

Warren, D. S. Memoing for logic programs. Comm. of the ACM, Special Section on Logic Programming 35, 3 (Mar. 1992), 93.]]

Digital Library

[19]

Zhou, N., Sato, T., and Hasida, K. Toward a high-performance system for symbolic and statistical modeling. In IJCAI Workshop on Learning Statistical Models from Relational Data (2003), p. to appear.]]

[20]

Zhou, N.-F. Parameter passing and control stack management in Prolog implementation revisited. ACM Transactions on Programming Languages and Systems 18, 6 (Nov. 1996), 752--779.]]

Digital Library

[21]

Zhou, N.-F., Shen, Y.-D., Yuan, L.-Y., and You, J.-H. Implementation of a linear tabling mechanism. LNCS (PADL) 1753 (2000), 109--123.]]

Digital Library

Cited By

Willis ATabkhi HMendieta MNeff C(2019)Measuring Compute-Reuse Opportunities for Video Processing Acceleration2019 SoutheastCon10.1109/SoutheastCon42311.2019.9020648(1-7)Online publication date: Apr-2019
https://doi.org/10.1109/SoutheastCon42311.2019.9020648
Stoffers MSchemmel DDustmann OWehrle K(2018)On Automated Memoization in the Field of Simulation Parameter StudiesACM Transactions on Modeling and Computer Simulation10.1145/318631628:4(1-25)Online publication date: 24-Sep-2018
https://dl.acm.org/doi/10.1145/3186316
Stoffers MSchemmel DSoria Dustmann OWehrle KFujimoto RUnger BCarothers C(2016)Automated Memoization for Parameter Studies Implemented in Impure LanguagesProceedings of the 2016 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2901378.2901386(221-232)Online publication date: 15-May-2016
https://dl.acm.org/doi/10.1145/2901378.2901386
Show More Cited By

Index Terms

Efficient fixpoint computation in linear tabling
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Constraint and logic languages

Recommendations

Linear tabling strategies and optimizations

Recently there has been a growing interest in research in tabling in the logic programming community because of its usefulness in a variety of application domains including program analysis, parsing, deductive databases, theorem proving, model checking, ...
Semi-naive evaluation in linear tabling
PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming

Semi-naive evaluation is an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers. The impact of this technique on top-down evaluation had been unknown. In this paper, we introduce semi-naive ...
Termination proofs for logic programs with tabling

Tabled evaluation is receiving increasing attention in the logic programming community. It avoids many of the shortcomings of SLD execution and provides a more flexible and often considerably more efficient execution mechanism for logic programs. In ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PPDP '03: Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming

August 2003

292 pages

ISBN:1581137052

DOI:10.1145/888251

Conference Chair:
Konstantinos Sagonas
Uppsala University, SW
,
Program Chair:
Dale Miller
INRIA/Futurs & Ecole Polytechnique, France

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PPDP03

Sponsor:

PPDP03: 5th International Conference on Principles and Practice of Declarative Programming 2003

August 27 - 29, 2003

Uppsala, Sweden

Acceptance Rates

PPDP '03 Paper Acceptance Rate 24 of 48 submissions, 50%;

Overall Acceptance Rate 230 of 486 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
232
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Willis ATabkhi HMendieta MNeff C(2019)Measuring Compute-Reuse Opportunities for Video Processing Acceleration2019 SoutheastCon10.1109/SoutheastCon42311.2019.9020648(1-7)Online publication date: Apr-2019
https://doi.org/10.1109/SoutheastCon42311.2019.9020648
Stoffers MSchemmel DDustmann OWehrle K(2018)On Automated Memoization in the Field of Simulation Parameter StudiesACM Transactions on Modeling and Computer Simulation10.1145/318631628:4(1-25)Online publication date: 24-Sep-2018
https://dl.acm.org/doi/10.1145/3186316
Stoffers MSchemmel DSoria Dustmann OWehrle KFujimoto RUnger BCarothers C(2016)Automated Memoization for Parameter Studies Implemented in Impure LanguagesProceedings of the 2016 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2901378.2901386(221-232)Online publication date: 15-May-2016
https://dl.acm.org/doi/10.1145/2901378.2901386
Cao S(2015)On the Efficiency of Query-Subquery Nets with Right/Tail-Recursion Elimination in Evaluating Queries to Horn Knowledge BasesAdvanced Computational Methods for Knowledge Engineering10.1007/978-3-319-17996-4_22(243-254)Online publication date: 2015
https://doi.org/10.1007/978-3-319-17996-4_22
Cao SNguyen L(2015)An Empirical Approach to Query-Subquery Nets with Tail-Recursion EliminationNew Trends in Database and Information Systems II10.1007/978-3-319-10518-5_9(109-120)Online publication date: 2015
https://doi.org/10.1007/978-3-319-10518-5_9
Cao SNguyen L(2014)An Improved Depth-First Control Strategy for Query-Subquery Nets in Evaluating Queries to Horn Knowledge BasesAdvanced Computational Methods for Knowledge Engineering10.1007/978-3-319-06569-4_21(281-295)Online publication date: 2014
https://doi.org/10.1007/978-3-319-06569-4_21
Cao SQuyet TThanh BVan TBui MHong S(2013)On the efficiency of query-subquery netsProceedings of the 4th Symposium on Information and Communication Technology10.1145/2542050.2542085(148-157)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.1145/2542050.2542085
Maggiore GSantos CDini DPeters FBouwknegt HSpronck P(2013)LGOAP: Adaptive layered planning for real-time videogames2013 IEEE Conference on Computational Inteligence in Games (CIG)10.1109/CIG.2013.6633624(1-8)Online publication date: Aug-2013
https://doi.org/10.1109/CIG.2013.6633624
Madalińska-Bugaj ENguyen L(2012)A Generalized QSQR Evaluation Method for Horn Knowledge BasesACM Transactions on Computational Logic10.1145/2362355.236236013:4(1-28)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1145/2362355.2362360
Swift TWarren D(2012)XsbTheory and Practice of Logic Programming10.1017/S147106841100050012:1-2(157-187)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1017/S1471068411000500
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents