Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-19T07:00:32.718Z Has data issue: false hasContentIssue false
  • English
  • Français

On the correctness of pull-tabbing

Published online by Cambridge University Press:  06 July 2011

SERGIO ANTOY
SERGIO ANTOY*
Affiliation:
Computer Science Department, Portland State University, Portland, OR 97207, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Pull-tabbing is an evaluation approach for functional logic computations, based on a graph transformation recently proposed, which avoids making irrevocable nondeterministic choices that would jeopardize the completeness of computations. In contrast to other approaches with this property, it does not require an upfront cloning of a possibly large portion of the choice's context. We formally define the pull-tab transformation, characterize the class of programs for which the transformation is intended, extend the computations in these programs to include the transformation, and prove the correctness of the extended computations.

Keywords

functional logic programmingnondeterminismgraph rewritingpull-tabbing
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. 713 - 730
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

Alqaddoumi, A., Antoy, S., Fischer, S. and Reck, F. 2010. The pull-tab transformation. In Proc. of 3rd International Workshop on Graph Computation Models, Enschede, The Netherlands, 127–133. URL: http://gcm-events.org/gcm2010/pages/gcm2010-preproceedings.pdfGoogle Scholar
Antoy, S. 1992. Definitional trees. In Proc. of 3rd International Conference on Algebraic and Logic Programming, Volterra, Italy, Kirchner, H. and Levi, G., Eds. Lecture Notes in Computer Science, vol. 632. Springer, Berlin, 143–157.CrossRefGoogle Scholar
Antoy, S. 1997. Optimal nondeterministic functional logic computations. In Proc. of 6th International Conference on Algebraic and Logic Programming (ALP '97), Southampton, UK. Lecture Notes in Computer Science, vol. 1298. Springer, Berlin, 16–30.CrossRefGoogle Scholar
Antoy, S. 2001. Constructor-based conditional narrowing. In Proc. of 3rd International Conference on Principles and Practice of Declarative Programming (PPDP '01), Florence, Italy. ACM, New York, 199–206.Google Scholar
Antoy, S. 2005. Evaluation strategies for functional logic programming. Journal of Symbolic Computation 40 (1), 875–903.CrossRefGoogle Scholar
Antoy, S. May 2010. Programming with narrowing. Journal of Symbolic Computation 45 (5), 501–522.CrossRefGoogle Scholar
Antoy, S., Brown, D. and Chiang, S. 2006. Lazy context cloning for nondeterministic graph rewriting. In Proc. of 3rd International Workshop on Term Graph Rewriting (Termgraph '06), Vienna, Austria, 61–70.Google Scholar
Antoy, S. and Hanus, M. 2002. Functional logic design patterns. In Proc. of 6th International Symposium on Functional and Logic Programming (FLOPS '02), Aizu, Japan. Lecture Notes in Computer Science, vol. 2441. Springer, Berlin, 67–87.CrossRefGoogle Scholar
Antoy, S. and Hanus, M. 2005. Declarative programming with function patterns. In Proc. of 15th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR '05), London, UK. Lecture Notes in Computer Science, vol. 3901. Springer, Berlin, 6–22.Google Scholar
Antoy, S. and Hanus, M. 2006. Overlapping rules and logic variables in functional logic programs. In Proc. of 21nd International Conference on Logic Programming, Seattle, WA. Lecture Notes in Computer Science, vol. 4079. Springer, Berlin, 87–101.Google Scholar
Antoy, S. and Hanus, M. 2009. Set functions for functional logic programming. In Proc. of 11th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP '09), Lisbon, Portugal, 73–82.Google Scholar
Antoy, S. and Hanus, M. April 2010. Functional logic programming. Commission of the ACM 53 (4) (April), 74–85.CrossRefGoogle Scholar
Antoy, S., Hanus, M., Liu, J. and Tolmach, A. 2005. A virtual machine for functional logic computations. In Proc. of 16th International Workshop on Implementation and Application of Functional Languages (IFL '04), Lubeck, Germany. Lecture Notes in Computer Science, vol. 3474. Springer, Berlin, 108–125.CrossRefGoogle Scholar
Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press.CrossRefGoogle Scholar
Bezem, M., Klop, J. W. and de Vrijer, R. (eds.) 2003. Term Rewriting Systems. Cambridge University Press.Google Scholar
Brassel, B. 2011 Implementing Functional Logic Programs by Translation into Purely Functional Programs. PhD Thesis, Christian-Albrechts-Universität zu Kie (to appear).CrossRefGoogle Scholar
Brassel, B. and Huch, F. 2007. On a tighter integration of functional and logic programming. In Proc. of 5th Asian conference on Programming languages and systems. Springer-Verlag, Berlin, Heidelberg, 122–138.CrossRefGoogle Scholar
Caballero, R. and Sánchez, J., Eds. 2007. TOY: A Multiparadigm Declarative Language (version 2.3.1) [online]. URL: http://toy.sourceforge.netGoogle Scholar
Dershowitz, N. and Jouannaud, J. 1990. Rewrite systems. In Handbook of Theoretical Computer Science B: Formal Methods and Semantics, Chapter 6, van Leeuwen, J., Ed. North Holland, Amsterdam, 243–320.Google Scholar
Echahed, R. and Janodet, J. C. 1997. On Constructor-Based Graph Rewriting Systems. Technical Report 985-I, IMAG. URL: ftp://ftp.imag.fr/pub/labo-LEIBNIZ/OLD-archives/PMP/c-graph-rewriting.ps.gzGoogle Scholar
Echahed, R. and Janodet, J. C. 1998. Admissible graph rewriting and narrowing. In Proc. of Joint International Conference and Symposium on Logic Programming, Manchester, UK. MIT Press, Cambridge, MA, 325–340.Google Scholar
Hanus, M., Ed. 2006. Curry: An integrated functional logic language (vers. 0.8.2) [online]. URL: http://www.informatik.uni-kiel.de/~curryGoogle Scholar
Hanus, M., Ed. 2008. PAKCS 1.9.1: The Portland Aachen Kiel Curry System. URL: http://www.informatik.uni-kiel.de/~pakcsGoogle Scholar
Huet, G. and Lévy, J.-J. 1991. Computations in orthogonal term rewriting systems. In Computational Logic: Essays in Honour of Alan Robinson, Lassez, J.-L. and Plotkin, G., Eds. MIT Press, Cambridge, MA.Google Scholar
Hussmann, H. 1992. Nondeterministic algebraic specifications and nonconfluent rewriting. Journal of Logic Programming 12, 237–255.CrossRefGoogle Scholar
ISO. 1995. Information Technology - Programming Languages - Prolog - Part 1. General Core. ISO/IEC 13211-1.Google Scholar
Klop, J. W. 1992. Term Rewriting Systems. In Handbook of Logic in Computer Science, Vol. II, Abramsky, S., Gabbay, D., and Maibaum, T., Eds. Oxford University Press, 1–112.Google Scholar
López-Fraguas, F. J., Rodríguez-Hortalá, J. and Sánchez-Hernández, J. 2007. A simple rewrite notion for call-time choice semantics. In Proc. of 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP '07). ACM, New York, 197–208.Google Scholar
López-Fraguas, F. J., Rodríguez-Hortalá, J. and Sánchez-Hernández, J. 2008. Rewriting and call-time choice: The HO case. In Proc. of 9th International Symposium on Functional and Logic Programming (FLOPS '08). Lecture Notes in Computer Science, vol. 4989. Springer, Berlin, 147–162.CrossRefGoogle Scholar
O'Donnell, M. J. 1985. Equational Logic as a Programming Language. MIT Press.Google Scholar
Plump, D. 1999. Term graph rewriting. In Handbook of Graph Grammars, Vol. 2, Ehrig, H.-J. K. H., Engels, G. and Rozenberg, G., Eds. World Scientific, Singapore, 3–61.Google Scholar
Tolmach, A., Antoy, S. and Nita, M. 2004. Implementing functional logic languages using multiple threads and stores. In Proc. of 2004 International Conference on Functional Programming (ICFP), Snowbird, UT. ACM, New York, 90–102.Google Scholar