by Salvador Espaņa and Vicent Estruch
Declarative multi-paradigm languages combine the main features of functional and logic programming, like laziness, logic variables and non-determinism. Pure functional and pure logic programming have for long time taken advantage of tabling or memoization schemes, which motivates the interest in adapting this technique to the integrated paradigm. In this work, we introduce an operational description of narrowing with memoization whose main aim is to provide the basis for a complete sequential implementation. Since the success of memoization critically depends on efficiently indexing terms and accessing the table, we study the adequacy of known term representation techniques. Along this direction, we introduce a novel data structure for representing terms and show how to use this representation in our setting.
The main motivation of our work is to provide an operational description of a complete (i.e., without backtracking) narrowing mechanism taking advantage of a memoization technique inspired in the graph representation proposed in [4]. This description is intended to be used in a compiler for flat programs [14] into C++, which is currently under development. Since the success of memoization critically depends on efficiently accessing the tables, we face the problem of data structure representation and indexing. In this direction, we introduce a novel data structure for representing terms which combines a tree and a linear representation.
[1] M. Alpuente, F. J. Correa, and M. Falaschi. Debugging Scheme of Functional Logic Programs In M. Hanus, editor, Proc. of International Workshop on Functional and (Constraint) Logic Programming, WFLP'01, volume 64 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers, 2002.
[2] M. Alpuente, M. Falaschi, and G. Vidal. Partial Evaluation of Functional Logic Programs ACM Transactions on Programming Languages and Systems, 20(4):768--844, 1998.
[3] S. Antoy. Definitional Trees In H. Kirchner and G. Levi, editors, Proc. of the 3rd International Conference on Algebraic and Logic Programming, pages 143--157, Volterra, Italy, September 1992. Springer LNCS 632.
[4] S. Antoy and Z. M. Ariola. Narrowing the narrowing space In 9th Int'l Symp. on Prog. Lang., Implementations, Logics, and Programs (PLILP'97), volume 1292, pages 1--15, Southampton, UK, 9 1997. Springer LNCS.
[5] J. Barklund. Tabulation of Functions in Definite Clause Programs In Manuel Hermenegildo and Jaan Penjam, editors, Proc. of the Sixth International Symposium on Programming Language Implementation and Logic Programming, pages 465--466. Springer Verlag, 1994.
[6] W. Chen and D. S. Warren. Tabled Evaluation with Delaying for General Logic Programs Journal of the ACM, 43(1):20--74, 1996.
[7] B. Cook and J. Launchbury. Disposable Memo Functions ACM SIGPLAN Notices, 32(8):310--318, 1997.
[8] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms MIT Press, 1992.
[9] B. Demoen and K. Sagonas. Memory Management for Prolog with Tabling ACM SIGPLAN Notices, 34(3):97--106, 1999.
[10] B. Demoen and K. Sagonas. CAT: The Copying Approach to Tabling Lecture Notes in Computer Science, Springer-Verlag, 1490:21--35, Setp. 1998.
[11] P. Graf. Substitution Tree Indexing Technical Report MPI-I-94-251, Saarbruecken, 1994.
[12] M. Hanus. The Integration of Functions into Logic Programming: From Theory to Practice Journal of Logic Programming, 19\&20:583--628, 1994.
[13] M. Hanus. A Unified Computation Model for Functional and Logic Programming In Proc. 24st ACM Symposium on Principles of Programming Languages (POPL'97), pages 80--93, 1997.
[14] M. Hanus and C. Prehofer. Higher-Order Narrowing with Definitional Trees Journal of Functional Programming, 9(1):33--75, 1999.
[15] J. Hughes. Lazy memo-functions Lazy memo-functions Proc. of the 2nd Conference on Functional Programming Languages and Computer Architecture (FPCA). Lecture Notes in Computer Science, 201:129--146, 1985.
[16] F.J. López-Fraguas J.C. González-Moreno, M.T. Hortalá-González and M. Rodríguez-Artalejo. An Approach to Declarative Programming based on a Rewriting Logic Journal of Logic Programming, (40):47--87, 1999.
[17] B. Mertens M. Leuschel and K. Sagonas. Preserving Termination of Tabled Logic Programs while Unfolding In Proc. of LOPSTR'97: Logic Program Synthesis and Transformation, N. Fuchs,Ed. LNCS 1463:189--205, 1997.
[18] A. Riazanov R. Nieuwenhuis, T. Hillenbrand and A. Voronkov. On the Evaluation of Indexing Techniques for Theorem Proving In Proc of the First International Joint Conference, IJCAR 2001, Siena, Italy, June 18-23, 2001, Proc. LNCS 2083:257--271, 2001.
[19] I. V. Ramakrishnan, P. Rao, K. F. Sagonas, T. Swift, and D. S. Warren. Efficient access mechanisms for tabled logic programs Journal of Logic Programming, 38(1):31--54, 1999.
[20] J. Rivero. Data Structures and Algorithms for Automated Deduction with Equality Phd thesis, Universitat Politecnica de Catalunya, Barcelona, 2000.
[21] R. Echahed S. Antoy and M. Hanus. A Needed Narrowing Strategy In Journal of the ACM (JACM). volume 47, pages 776--822. ACM Press New York, NY, USA, 2000.
[22] K. Sagonas and M. Leuschel. Extending Partial Deduction to Tabled Execution: Some Results and Open Issues. ACM Computing Surveys, 30(3es), 1998.
[23] H. Tamaki and T. Sato. Old Resolution with Tabulation In 3rd International Conference on Logic Programming, volume Springer LNCS 225, pages 84--98, 1986.
| ELP | DSIC | UPV |
Last update Apr 2003 # sespana@dsic.upv.es and vestruch@dsic.upv.es