Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T15:11:46.742Z Has data issue: false hasContentIssue false
  • English
  • Français

Linear tabling strategies and optimizations

Published online by Cambridge University Press:  01 January 2008

NENG-FA ZHOU ,
TAISUKE SATO  and
YI-DONG SHEN
NENG-FA ZHOU
Affiliation:
CUNY Brooklyn College & Graduate Center (email: [email protected])
TAISUKE SATO
Affiliation:
Tokyo Institute of Technology (email: [email protected])
YI-DONG SHEN
Affiliation:
Chinese Academy of Sciences (email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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, and logic-based probabilistic learning. The main idea of tabling is to memorize the answers to some subgoals and use the answers to resolve subsequent variant subgoals. Early resolution mechanisms proposed for tabling such as OLDT and SLG rely on suspension and resumption of subgoals to compute fixpoints. Recently, the iterative approach named linear tabling has received considerable attention because of its simplicity, ease of implementation, and good space efficiency. Linear tabling is a framework from which different methods can be derived on the basis of the strategies used in handling looping subgoals. One decision concerns when answers are consumed and returned. This article describes two strategies, namely, lazy and eager strategies, and compares them both qualitatively and quantitatively. The results indicate that, while the lazy strategy has good locality and is well suited for finding all solutions, the eager strategy is comparable in speed with the lazy strategy and is well suited for programs with cuts. Linear tabling relies on depth-first iterative deepening rather than suspension to compute fixpoints. Each cluster of interdependent subgoals as represented by a topmost looping subgoal is iteratively evaluated until no subgoal in it can produce any new answers. Naive re-evaluation of all looping subgoals, albeit simple, may be computationally unacceptable. In this article, we also introduce semi-naive optimization, an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers, into linear tabling. We give the conditions for the technique to be safe (i.e., sound and complete) and propose an optimization technique called early answer promotion to enhance its effectiveness. Benchmarking in B-Prolog demonstrates that with this optimization linear tabling compares favorably well in speed with the state-of-the-art implementation of SLG.

Keywords

Prologsemi-naive evaluationrecursiontablingmemoizationlinear tabling
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 8 , Issue 1 , January 2008 , pp. 81 - 109
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Apt, K., Blair, H. A. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann, San Francisco, 89–142.CrossRefGoogle Scholar
Bancilhon, F. and Ramakrishnan, R. 1986. An amateur's introduction to recursive query processing strategies. In Proc. of ACM SIGMOD '86, 16–52.Google Scholar
Chen, W. and Warren, D. S. 1996. Tabled evaluation with delaying for general logic programs. Journal of the ACM 43, 1, 20–74.CrossRefGoogle Scholar
Dawson, S., Ramakrishnan, C. R. and Warren, D. S. 1996. Practical program analysis using general purpose logic programming systems–-A case study. ACM SIGPLAN Notices 31, 5, 117–126.CrossRefGoogle Scholar
Demoen, B. and Sagonas, K. 1998. CAT: The copying approach to tabling. In Proc. of Programming Language Implementation and Logic Programming (PLILP), LNCS 1490, 21–35.Google Scholar
Demoen, B. and Sagonas, K. 1999. CHAT: The copy-hybrid approach to tabling. In Proc. of Practical Aspects of Declarative Programming (PADL), LNCS 1551, 106–121.Google Scholar
Dietrich, S. W. 1987. Extension tables: Memo relations in logic programming. In IEEE Fourth Symposium on Logic Programming. 264–272.Google Scholar
Eisner, J., Goldlust, E. and Smith, N. A. 2004. Dyna: A declarative language for implementing dynamic programs. In Proc. of the 42nd Annual Meeting of ACL.CrossRefGoogle Scholar
Freire, J., Swift, T. and Warren, D. S. 1998. Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. Journal of Functional and Logic Programming.Google Scholar
Guo, H.-F. and Gupta, G. 2001. A simple scheme for implementing tabled logic of programming systems based on dynamic reordering of alternatives. In Proc. of International Conference on Logic Programming (ICLP), LNCS 2237, 181–195.Google Scholar
Johnson, M. 1995. Memoization of top down parsing. Computational Linguistics 21, 3.Google Scholar
Liu, M. 1999. Deductive database languages: Problems and solutions. ACM Computing Surveys 31, 1, 27–62.CrossRefGoogle Scholar
Lloyd, J. W. 1988. Foundation of Logic Programming, 2nd ed.Springer-Verlag, New York.Google Scholar
Michie, D. 1968. “memo” functions and machine learning. Nature 218, 6, 19–22.CrossRefGoogle Scholar
Nielson, F., Nielson, H. R., Sun, H., Buchholtz, M., Hansen, R. R., Pilegaard, H. and Seidl, H. 2004. The succinct solver suite. In Proc. Tools and Algorithms for the Construction and Analysis of Systems: 10th International Conference (TACAS), LNCS 2988, 251–265.Google Scholar
Pientka, B. December 2003. Tabled Higher-order Logic Programming. PhD thesis, Technical Report CMU-CS-03-185, Carnegie Mellon University, Pittsburgh.Google Scholar
Przymusinski, T. C. 1989. 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. ACM Press, New York, 11–21.Google Scholar
Ramakrishnan, C. Feb. 2002. Model checking with tabled logic programming. In ALP News Letter. ALP.Google Scholar
Ramakrishnan, I., Rao, P., Sagonas, K., Swift, T. and Warren, D. 1998. Efficient access mechanisms for tabled logic programs. Journal of Logic Programming 38, 31–54.CrossRefGoogle Scholar
Ramakrishnan, R. and Ullman, J. D. 1995. A survey of deductive database systems. Journal of Logic Programming 23, 2, 125–149.CrossRefGoogle Scholar
Rocha, R., Silva, F. and Costa, V. S. 2005a. Dynamic mixed-strategy evaluation of tabled logic programs. In Proc. of International Conference on Logic Programming (ICLP), 250–264.Google Scholar
Rocha, R., Silva, F. and Costa, V. S. 2005b. On applying or-parallelism and tabling to logic programs. Theory and Practice of Logic Programming (TPLP) 5, 1 & 2, 161–205.CrossRefGoogle Scholar
Sagonas, K. and Swift, T. 1998. An abstract machine for tabled execution of fixed-order stratified logic programs. ACM Transactions on Programming Languages and Systems 20, 3, 586–634.CrossRefGoogle Scholar
Sagonas, K., Swift, T. and Warren, D. S. 1994. XSB as a deductive database. SIGMOD Record (ACM Special Interest Group on Management of Data) 23, 2, 512–512.Google Scholar
Sato, T. and Kameya, Y. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research, 391–454.Google Scholar
Shen, Y.-D., Yuan, L., You, J. and Zhou, N.-F. 2001. Linear tabulated resolution based on Prolog control strategy. Theory and Practice of Logic Programming (TPLP) 1, 1, 71–103.CrossRefGoogle Scholar
Shen, Y.-D., Yuan, L.-Y., You, J.-H. and Zhou, N.-F. 1999. Linear tabulated resolutions for the well-founded semantics. In Proc. of Logic Programming and Nonmonotonic Reasoning, 192–205.Google Scholar
Somogyi, Z. and Sagonas, K. in press. Tabling in mercury: Design and implementation. In Proc. of Practical Aspects of Declarative Programming (PADL) 15. Springer-Verlag, New York.Google Scholar
Tamaki, H. and Sato, T. 1986. OLD resolution with tabulation. In Proc. of the Third International Conference on Logic Programming, Shapiro, E., Ed. 84–98, LNCS 225, Springer.CrossRefGoogle Scholar
Ullman, J. D. 1988. Database and Knowledge-Base Systems, Vols. 1 & 2. Computer Science Press, New York.Google Scholar
Uratani, N., Takezawa, T., Matsuo, H. and Morita, C. 1994. ATR Integrated Speech and Language Database [Technical Report TR-IT-0056], ATR Interpreting Telecommunications Research Laboratories. In Japanese, ATR.Google Scholar
Warren, D. S. 1992. Memoing for logic programs. Communications of the ACM, Special Section on Logic Programming 35, 93–111.Google Scholar
Warren, D. S. 1999. Programming in Tabled Prolog [DRAFT 1]. url: http://www.cs.sunysb.edu/warren/xsbbook/book.html. Accessed April 1, 2006.Google Scholar
Zhou, N.-F. 1996. Parameter passing and control stack management in Prolog implementation revisited. ACM Transactions on Programming Languages and Systems 18, 6, 752–779.CrossRefGoogle Scholar
Zhou, N.-F. and Sato, T. 2003. Efficient fixpoint computation in linear tabling. In Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, 275–283.Google Scholar
Zhou, N.-F., Sato, T. and Hasida, K. 2003. Toward a high-performance system for symbolic and statistical modeling. In IJCAI Workshop on Learning Statistical Models from Relational Data, 153–159.Google Scholar
Zhou, N.-F., Shen, Y.-D. and Sato, T. 2004. Semi-naive evaluation in linear tabling. In Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, 90–97.Google Scholar
Zhou, N.-F., Shen, Y.-D., Yuan, L.-Y. and You, J.-H. 2000. Implementation of a linear tabling mechanism. In Proc. of Practical Aspects of Declarative Programming (PADL), LNCS 1753, 109–123.Google Scholar