Abstract
The advantages of tabled evaluation regarding program termination and reduction of complexity are well known —as are the significant implementation, portability, and maintenance efforts that some proposals (especially those based on suspension) require. This implementation effort is reduced by program transformation-based continuation call techniques, at some efficiency cost. However, the traditional formulation of this proposal [1] limits the interleaving of tabled and non-tabled predicates and thus cannot be used as-is for arbitrary programs. In this paper we present a complete translation for the continuation call technique which, while requiring the same runtime support as the traditional approach, solves these problems and makes it possible to execute arbitrary tabled programs. We also present performance results which show that the resulting CCall approach offers a useful tradeoff that can be competitive with other state-of-the-art implementations.
This work was funded in part by EU FET project IST-15905 MOBIUS, and FP7 grant agreement 215483 S-Cube, Spanish MEC project TIN2008-05624 DOVES, ITEA2/PROFIT FIT-340005-2007-14 ES_PASS, and by Madrid Regional Government program S-0505/TIC/0407 PROMESAS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ramesh, R., Chen, W.: Implementation of tabled evaluation with delaying in prolog. IEEE Trans. Knowl. Data Eng. 9(4), 559–574 (1997)
Tamaki, H., Sato, M.: OLD resolution with tabulation. In: Shapiro, E. (ed.) ICLP 1986. LNCS, vol. 225, pp. 84–98. Springer, Heidelberg (1986)
Warren, D.: Memoing for logic programs. Communications of the ACM 35(3), 93–111 (1992)
Chen, W., Warren, D.S.: Tabled Evaluation with Delaying for General Logic Programs. Journal of the ACM 43(1), 20–74 (1996)
Ramakrishnan, R., Ullman, J.D.: A survey of research on deductive database systems. Journal of Logic Programming 23(2), 125–149 (1993)
Warren, R., Hermenegildo, M., Debray, S.K.: On the Practicality of Global Flow Analysis of Logic Programs. In: Fifth International Conference and Symposium on Logic Programming, pp. 684–699. MIT Press, Cambridge (1988)
Dawson, S., Ramakrishnan, C., Warren, D.: Practical Program Analysis Using General Purpose Logic Programming Systems – A Case Study. In: Proceedings of PLDI 1996, pp. 117–126. ACM Press, New York (1996)
Zou, Y., Finin, T., Chen, H.: F-OWL: An Inference Engine for Semantic Web. In: Hinchey, M.G., Rash, J.L., Truszkowski, W.F., Rouff, C.A. (eds.) FAABS 2004. LNCS, vol. 3228, pp. 238–248. Springer, Heidelberg (2004)
Ramakrishna, Y., Ramakrishnan, C., Ramakrishnan, I., Smolka, S., Swift, T., Warren, D.: Efficient Model Checking Using Tabled Resolution. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 143–154. Springer, Heidelberg (1997)
Sagonas, K., Swift, T.: An Abstract Machine for Tabled Execution of Fixed-Order Stratified Logic Programs. ACM Transactions on Programming Languages and Systems 20(3), 586–634 (1998)
Demoen, B., Sagonas, K.: CAT: The Copying Approach to Tabling. In: Palamidessi, C., Meinke, K., Glaser, H. (eds.) ALP 1998 and PLILP 1998. LNCS, vol. 1490, pp. 21–35. Springer, Heidelberg (1998)
Demoen, B., Sagonas, K.F.: Chat: The copy-hybrid approach to tabling. In: Practical Applications of Declarative Languages, pp. 106–121 (1999)
Zhou, N.F., Shen, Y.D., Yuan, L.Y., You, J.H.: Implementation of a linear tabling mechanism. Journal of Functional and Logic Programming 2001(10) (October 2001)
Zhou, N.F., Sato, T., Shen, Y.D.: Linear Tabling Strategies and Optimizations. Theory and Practice of Logic Programming 8(1), 81–109 (2008)
Guo, H.-F., Gupta, G.: A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 181–196. Springer, Heidelberg (2001)
de Guzmán, P.C., Carro, M., Hermenegildo, M., Silva, C., Rocha, R.: An Improved Continuation Call-Based Implementation of Tabling. In: Hudak, P., Warren, D.S. (eds.) PADL 2008. LNCS, vol. 4902, pp. 198–213. Springer, Heidelberg (2008)
Casas, A., Cabeza, D., Hermenegildo, M.: A Syntactic Approach to Combining Functional Notation, Lazy Evaluation and Higher-Order in LP Systems. In: FLOPS 2006, Fuji Susono (Japan) (April 2006)
Demoen, B., Sagonas, K.: CHAT is θ(SLG-WAM). In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS, vol. 1705, pp. 337–357. Springer, Heidelberg (1999)
Bueno, F., Cabeza, D., Carro, M., Hermenegildo, M., López-García, P. (eds.): G.P.: The Ciao System. Ref. Manual (v1.13). Technical report, C. S. School, UPM (2006)
Cabeza, D., Hermenegildo, M.: The Ciao Modular, Standalone Compiler and Its Generic Program Processing Library. Special Issue on Parallelism and Implementation of (C)LP Systems. Electronic Notes in Theoretical Computer Science 30(3) (March 2000)
Rocha, R., Silva, F., Costa, V.S.: YapTab: A Tabling Engine Designed to Support Parallelism. In: Conference on Tabulation in Parsing and Deduction. pp. 77–87 (2000)
Castro, L., Swift, T., Warren, D.: Suspending and Resuming Computations in Engines for SLG Evaluation. In: Krishnamurthi, S., Ramakrishnan, C.R. (eds.) PADL 2002. LNCS, vol. 2257, pp. 332–346. Springer, Heidelberg (2002)
Carro, M., Morales, J., Muller, H., Puebla, G., Hermenegildo, M.: High-Level Languages for Small Devices: A Case Study. In: Flautner, K., Kim, T. (eds.) Compilers, Architecture, and Synthesis for Embedded Systems, pp. 271–281. ACM Press / Sheridan (October 2006)
Morales, J., Carro, M., Hermenegildo, M.: Improving the Compilation of Prolog to C Using Moded Types and Determinism Information. In: Jayaraman, B. (ed.) PADL 2004. LNCS, vol. 3057, pp. 86–103. Springer, Heidelberg (2004)
Morales, J., Carro, M., Hermenegildo, M.: Comparing Tag Scheme Variations Using an Abstract Machine Generator. In: 10th Int’l. ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2008), pp. 32–43. ACM Press, New York (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Guzman, P.C., Carro, M., Hermenegildo, M.V. (2008). Towards a Complete Scheme for Tabled Execution Based on Program Transformation. In: Gill, A., Swift, T. (eds) Practical Aspects of Declarative Languages. PADL 2009. Lecture Notes in Computer Science, vol 5418. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92995-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-92995-6_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92994-9
Online ISBN: 978-3-540-92995-6
eBook Packages: Computer ScienceComputer Science (R0)