An abstract machine for tabled execution of fixed-order stratified logic programs

ABSTRACT

SLG resolution uses tabling to evaluate nonfloundering normal logic pr ograms according to the well-founded semantics. The SLG-WAM, which forms the engine of the XSB system, can compute in-memory recursive queries an order of magnitute faster than current deductive databases. At the same time, the SLG-WAM tightly intergrates Prolog code with tabled SLG code, and executes Prolog code with minimal overhead compared to the WAM. As a result, the SLG-WAM brings to logic programming important termination and complexity properties of deductive databases. This article describes the architecture of the SLG-WAM for a powerful class of programs, the class of fixed-order dynamically stratified programs. We offer a detailed description of the algorithms, data structures, and instructions that the SLG-WAM adds to the WAM, and a performance analysis of engine overhead due to the extensions.

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: CHEN, W., SWIFT, T., AND WARREN, D. S. 1995. Efficient top-down computation of queries under the well-founded semantics. J. Logic Program. 24, 3 (Sept.), 161-199.
• 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: CODISH, M., DEMOEN, B., AND SAGONAS, I~. 1996. Semantics-based program analysis for logicbased languages using XSB. Tech. Rep. CW 245, Katholieke Universiteit Leuven, Heverlee Belgium.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Steven Dawson , C. R. Ramakrishnan , David S. Warren, Practical program analysis using general purpose logic programming systems—a case study, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.117-126, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 7: Suzanne Wagner Dietrich, Extension tables for recursive query evaluation, 1987
• 8: Juliana Freire , Terrance Swift , David Scott Warren, Beyond Depth-First: Improving Tabled Logic Programs through Alternative Scheduling Strategies, Proceedings of the 8th International Symposium on Programming Languages: Implementations, Logics, and Programs, p.243-258, September 24-27, 1996
• 9: FREIRE, J., SWIFT, T., AND WARREN, D. S. 1997. Treating I/O seriously: Resolution reconsidered for disk. In Proceedings of the 14th International Conference on Logic Programming, L. Naish, Ed. The MIT Press, Cambridge, Mass., 198-212.
• 10: LARSON, R., WARREN, D. S., FREIRE, J., GOMEZ, O. P., AND SAGONAS, K. 1997. Semantica. The MIT Press, Cambridge, Mass.
• 11: LARSON, R., WARREN, D. S., FREIRE, J., AND SAGONAS, K. 1996. Syntactica. The MIT Press, Cambridge, Mass.
• 12: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 13: T. C. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-21, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73723]
• 14: Y. S. Ramakrishna , C. R. Ramakrishnan , I. V. Ramakrishnan , Scott A. Smolka , Terrance Swift , David Scott Warren, Efficient Model Checking Using Tabled Resolution, Proceedings of the 9th International Conference on Computer Aided Verification, p.143-154, June 22-25, 1997
• 15: RAMAKRISHNAN, I. V., RAO, P., SAGONAS, K., SWIFT, T., AND WARREN, D. S. 1995. Efficient tabling mechanisms for logic programs. In Proceedings of the 12th International Conference on Logic Programming, L. Sterling, Ed. The MIT Press, Cambridge, Mass., 687-711.
• 16: RAMAKRISHNAN, R., SRIVASTAVA, D., AND SUDARSHAN, S. 1992a. Controlling the search in bottomup evaluation. In Proceedings of the Joint International Conference and Symposium on Logic Programming, K. Apt, Ed. The MIT Press, Cambridge, Mass., 273-287.
• 17: Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, CORAL - Control, Relations and Logic, Proceedings of the 18th International Conference on Very Large Data Bases, p.238-250, August 23-27, 1992
• 18: R. Ramesh , Weidong Chen, Implementation of Tabled Evaluation with Delaying in Prolog, IEEE Transactions on Knowledge and Data Engineering, v.9 n.4, p.559-574, July 1997 [doi>10.1109/69.617050]
• 19: RAO, P., RAMAKRISHNAN, C. R., AND RAMAKRISHNAN, I. V. 1996. A thread in time saves tabling time. In Proceedings of the Joint International Conference and Symposium on Logic Programruing, M. Maher, Ed. The MIT Press, Cambridge, Mass., 112-126.
• 20: Kenneth A. Ross, Modular stratification and magic sets for Datalog programs with negation, Journal of the ACM (JACM), v.41 n.6, p.1216-1266, Nov. 1994 [doi>10.1145/195613.195646]
• 21: 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
• 22: SAGONAS, K., SWIFT, T., AND WARREN, D. S. 1996a. An abstract machine for computing the wellfounded semantics. In Joint International Conference and Symposium on Logic Programming, M. Maher, Ed. The MIT Press, Cambridge, Mass., 274-288.
• 23: Konstantinos F. Sagonas , Terrance Swift , David Scott Warren, The Limits of Fixed-Order Computation, Proceedings of the International Workshop on Logic in Databases, p.343-363, July 01-02, 1996
• 24: Terrance Lee Swift, Efficient evaluation of normal logic programs, State University of New York at Stony Brook, Stony Brook, NY, 1994
• 25: Terrance Swift , David S. Warren, Analysis of SLG-WAM evaluation of definite programs, Proceedings of the 1994 International Symposium on Logic programming, p.219-235, November 1994, Symposia, Melbourne
• 26: Hisao Tamaki , Taisuke Sato, OLD resolution with tabulation, Proceedings on Third international conference on logic programming, p.84-98, September 1986, London, United Kingdom
• 27: TAYLOR, t. 1991. High performance Prolog implementation. Ph.D. thesis, Dept. of Computer Science, University of Sidney, Sidney, Australia.
• 28: Evan Tick, Memory performance of prolog architectures, Kluwer Academic Publishers, Norwell, MA, 1988
• 29: Alan van Gelser, Negation as failure using tight derivations for general logic programs, Journal of Logic Programming, v.6 n.1-2, p.109-133, Jan./Mar. 1989 [doi>10.1016/0743-1066(89)90032-0]
• 30: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 31: Peter Lodewijk Van Roy, Can logic programming execute as fast as imperative programming?, University of California at Berkeley, Berkeley, CA, 1991
• 32: VAN ROY, P. 1994. 1983-1993: The wonder years of sequential Prolog implementation. J. Logic Program. 19/20, 385-441.
• 33: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 34: L. Vielle, Recursive query processing: the power of logic, Theoretical Computer Science, v.69 n.1, p.1-53, Dec. 5, 1989 [doi>10.1016/0304-3975(89)90088-1]
• 35: WARREN, D. H. D. 1983. An Abstract Prolog instruction set. Tech. Rep. 309, SRI International, Menlo Park, Calif.
• 36: David H. D. Warren, Or-Parallel Execution Models of Prolog, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Functional and Logic Programming and Specifications (CFLP), p.243-259, March 23-27, 1987
• 37: WARREN, D. S. 1984. Efficient Prolog memory management for flexible control strategies. In Proceedings of the 1984 Symposium on Logic Programming. IEEE Computer Science Press, Los Alamitos, Calif., 198-202.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters; Optimization; Compilers

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming; Nonmonotonic reasoning and belief revision; Resolution

General Terms:
Algorithms, Experimentation, Performance

Keywords:
SLG, WAM, memoing, prolog, stratification theories, tabling