Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-19T07:10:33.706Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient instance retrieval of subgoals for subsumptive tabled evaluation of logic programs

Published online by Cambridge University Press:  06 July 2011

FLÁVIO CRUZ  and
RICARDO ROCHA
FLÁVIO CRUZ
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: [email protected], [email protected])
RICARDO ROCHA
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Tabled evaluation is an implementation technique that solves some problems of traditional Prolog systems in dealing with recursion and redundant computations. Most tabling engines determine if a tabled subgoal will produce or consume answers by using variant checks. A more refined method, named call subsumption, considers that a subgoal A will consume from a subgoal B if A is subsumed by (an instance of) B, thus allowing greater answer reuse. We recently developed an extension, called Retroactive Call Subsumption, that improves upon call subsumption by supporting bidirectional sharing of answers between subsumed/subsuming subgoals. In this paper, we present both an algorithm and an extension to the table space data structures to efficiently implement instance retrieval of subgoals for subsumptive tabled evaluation of logic programs. Experiments results using the YapTab tabling system show that our implementation performs quite well on some complex benchmarks and is robust enough to handle a large number of subgoals without performance degradation.

Keywords

tabled evaluationcall subsumptionimplementation
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 697 - 712
Copyright
Copyright © Cambridge University Press 2011

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

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
Cruz, F. and Rocha, R. 2010. Retroactive subsumption-based tabled evaluation of logic programs. In Proc. of European Conference on Logics in Artificial Intelligence. Lecture Notes in Artificial Intelligence, vol. 6341. Springer-Verlag, 130–142.Google Scholar
Johnson, E. 2000. Interfacing a tabled-WAM engine to a tabling subsystem supporting both variant and subsumption checks. In Proc. of Conference on Tabulation in Parsing and Deduction, 155–162.Google Scholar
Johnson, E., Ramakrishnan, C. R., Ramakrishnan, I. V. and Rao, P. 1999. A space efficient engine for subsumption-based tabled evaluation of logic programs. In Proc. of Fuji International Symposium on Functional and Logic Programming. Lecture Notes in Computer Science, vol. 1722. Springer-Verlag, 284–300.CrossRefGoogle Scholar
Ramakrishnan, I. V., Rao, P., Sagonas, K., Swift, T. and Warren, D. S. 1999. Efficient access mechanisms for tabled logic programs. Journal of Logic Programming 38 (1), 31–54.CrossRefGoogle Scholar
Rao, P., Ramakrishnan, C. R. and Ramakrishnan, I. V. 1996. A thread in time saves tabling time. In Proc. of Joint International Conference and Symposium on Logic Programming. The MIT Press, 112–126.Google Scholar
Rao, P., Sagonas, K., Swift, T., Warren, D. S. and Freire, J. 1997. XSB: A system for efficiently computing well-founded semantics. In Proc. of International Conference on Logic Programming and Non-Monotonic Reasoning. Lecture Notes in Computer Science, vol. 1265. Springer-Verlag, 431–441.Google Scholar
Rocha, R., Silva, F. and Santos Costa, V. 2000. YapTab: A tabling engine designed to support parallelism. In Proc. of Conference on Tabulation in Parsing and Deduction, 77–87.Google Scholar
Rocha, R., Silva, F. and Santos Costa, V. 2005. On applying or-parallelism and tabling to logic programs. Theory and Practice of Logic Programming 5 (1–2), 161–205.CrossRefGoogle Scholar
Yang, G. and Kifer, M. 2000. Flora: Implementing an efficient Dood system using a tabling logic engine. In Proc. of Computational Logic. Lecture Notes in Computer Science, vol. 1861. Springer-Verlag, 1078–1093.Google Scholar