Just enough tabling

ABSTRACT

We introduce just enough tabling (JET), a mechanism to suspend and resume the tabled execution of logic programs at an arbitrary point. In particular, JET allows pruning of tabled logic programs to be performed without resorting to any recomputation. We discuss issues that are involved in supporting pruning in tabled resolution, how re-execution of tabled computations which were previously pruned can be avoided, and we describe the implementation of such a scheme based on an abstract machine like CHAT, which implements the suspension/resumption support that tabling requires through a combination of freezing and copying of execution states of suspended computations. Properties of just enough tabling and possible uses of the JET mechanism in a tabling system are also briefly discussed.

REFERENCES

• 1: Luís Fernando Castro , Terrance Swift , David Scott Warren, Suspending and Resuming Computations in Engines for SLG Evaluation, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.332-350, January 19-20, 2002
• 2: L. F. Castro and D. S. Warren. Approximate pruning in tabled logic programming. In P. Degano, editor, Programming Languages and Systems: Proceedings of the European Symposium on Programming, number 2618 in LNCS, pages 69--83. Springer, Apr. 2003.
• 3: Weidong Chen , David S. Warren, Tabled evaluation with delaying for general logic programs, Journal of the ACM (JACM), v.43 n.1, p.20-74, Jan. 1996 [doi>10.1145/227595.227597]
• 4: Bart Demoen , Konstantinos F. Sagonas, CHAT Is Theta(SLG-Wam), Proceedings of the 6th International Conference on Logic Programming and Automated Reasoning, p.337-357, September 06-10, 1999
• 5: Bart Demoen , Konstantinos Sagonas, CHAT: the copy-hybrid approach to tabling, Future Generation Computer Systems, v.16 n.7, p.809-830, May 2000 [doi>10.1016/S0167-739X(99)00092-8]
• 6: Hai-Feng Guo , Gopal Gupta, A Simple Scheme for Implementing Tabled Logic Programming Systems Based on Dynamic Reordering of Alternatives, Proceedings of the 17th International Conference on Logic Programming, p.181-196, November 26-December 01, 2001
• 7: H.-F. Guo and G. Gupta. Cuts in tabled logic programming. In B. Demoen, editor, Proceedings of CICLOPS'2002, the Colloquium on Implementation of Constraint and LOgic Programming Systems, pages 62--73, July 2002.
• 8: I. V. Ramakrishnan, P. Rao, K. Sagonas, T. Swift, and D. S. Warren. Efficient access mechanisms for tabled logic programs. J. of Logic Program., 38(1):31--54, Jan. 1999.
• 9: R. Rocha, F. Silva, and V. Santos Costa. YapTab: A tabling engine designed to support parallelism. In Proceedings of Tabulation in Parsing and Deduction (TAPD), pages 77--87, Sept. 2000.
• 10: Konstantinos Sagonas , Terrance Swift, An abstract machine for tabled execution of fixed-order stratified logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.586-634, May 1998 [doi>10.1145/291889.291897]
• 11: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: Z. Somogyi, F. Henderson, and T. Conway. The execution algorithm of Mercury, an efficient purely declarative logic programming language. J. of Logic Program., 26(1-3):17--64, Oct./Dec. 1996.
• 13: Hisao Tamaki , Taisuke Sato, OLD Resolution with Tabulation, Proceedings of the Third International Conference on Logic Programming, p.84-98, July 14-18, 1986
• 14: D. H. D. Warren. An abstract Prolog instruction set. Technical Report 309, SRI International, Menlo Park, U.S.A., Oct. 1983.
• 15: N.-F. Zhou, Y.-D. Shen, L.-Y. Yuan, and J.-H. You. Implementation of a linear tabling mechanism. J. of Functional and Logic Program., 2001(10), 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

General Terms:
Algorithms, Languages

Keywords:
logic programming, pruning, suspension/resumption in the WAM, tabling