Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-21T22:57:03.435Z Has data issue: false hasContentIssue false
  • English
  • Français

On combining linear-based strategies for tabled evaluation of logic programs

Published online by Cambridge University Press:  06 July 2011

MIGUEL AREIAS  and
RICARDO ROCHA
MIGUEL AREIAS
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: miguel-areias@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
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: miguel-areias@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
Get access Rights & Permissions [Opens in a new window]

Abstract

Tabled evaluation is a recognized and powerful technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant subcomputations. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear tabling. While suspension-based mechanisms are considered to obtain better results in general, they have more memory space requirements and are more complex and harder to implement than linear tabling mechanisms. Arguably, the SLDT and Dynamic Reordering of Alternatives (DRA) strategies are the two most successful extensions to standard linear tabled evaluation. In this work, we propose a new strategy, named dynamic reordering of solutions, and we present a framework, on top of the Yap system, that supports the combination of all these three strategies. Our implementation shares the underlying execution environment and most of the data structures used to implement tabling in Yap. We thus argue that all these common features allows us to make a first and fair comparison between these different linear tabling strategies and, therefore, better understand the advantages and weaknesses of each, when used solely or combined with the others.

Keywords

linear tablingintegrationimplementation
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. 681 - 696
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

Areias, M. and Rocha, R. 2010. An efficient implementation of linear tabling based on dynamic reordering of alternatives. In Proc. of International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 5967. Springer-Verlag, 279–293.CrossRefGoogle 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
de Guzmán, P. C., Carro, M. and Hermenegildo, M. V. 2009. Towards a complete scheme for tabled execution based on program transformation. In Proc. of International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 5418. Springer-Verlag, 224–238.Google Scholar
Freire, J., Swift, T. and Warren, D. S. 1996. Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. In Proc. of International Symposium on Programming Language Implementation and Logic Programming. Lecture Notes in Computer Science, vol. 1140. Springer-Verlag, 243–258.Google Scholar
Guo, H.-F. and Gupta, G. 2001. A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. In Proc. of International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 2237. Springer-Verlag, 181–196.CrossRefGoogle Scholar
Lloyd, J. W. 1987. Foundations of Logic Programming. Springer-Verlag.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
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
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
Somogyi, Z. and Sagonas, K. 2006. Tabling in mercury: Design and implementation. In Proc. of International Symposium on Practical Aspects of Declarative Languages. Lecture Notes in Computer Science, vol. 3819. Springer-Verlag, 150–167.Google Scholar
Tamaki, H. and Sato, T. 1986. OLDT resolution with tabulation. In Proc. of International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 225. Springer-Verlag, 84–98.Google Scholar
Zhou, N.-F., Sato, T. and Shen, Y.-D. 2008. Linear tabling strategies and optimizations. Theory and Practice of Logic Programming 8 (1), 81–109.CrossRefGoogle 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 Languages. Lecture Notes in Computer Science, vol. 1753. Springer-Verlag, 109–123.Google Scholar