skip to main content
10.1145/1929501.1929523acmconferencesArticle/Chapter ViewAbstractPublication PagespepmConference Proceedingsconference-collections
research-article

A program transformation for returning states in functional-logic programs

Published: 24 January 2011 Publication History

Abstract

This paper studies the conditions necessary to safely introduce new values as part of the results of function rules in functional-logic programs. The idea is to consider an initial functional-logic program and to produce, by means of a program transformation, a new program including states. Each rule of the new program returns pairs of values, with the first value the same as in the original program, and the second one a new value that can be defined in terms of the values returned by the function calls occurring in the rule. We prove that the transformation ensures the equivalence of the two programs with respect to the Constructor-based ReWriting Logic, a suitable semantics for functional-logic programs.

References

[1]
M. Abengózar-Carneros et al. Toy: A multiparadigm declarative language. version 1.0. Technical Report SIP-119/00, Universidad Complutense de Madrid, Departamento de Sistemas Informáticos y Programación, UCM, February 2002.
[2]
E. Albert, M. Hanus, and G. Vidal. A residualizing semantics for the partial evaluation of functional logic programs. Inf. Process. Lett., 85 (1): 19--25, 2003.
[3]
E. Albert, M. Hanus, F. Huch, J. Oliver, and G. Vidal. Operational semantics for declarative multi-paradigm languages. Journal of Symbolic Computation, 40: 795--829, 2005.
[4]
S. Antoy and M. Hanus. Functional logic programming. Commun. ACM, 53 (4): 74--85, 2010.
[5]
R. Caballero and F. López-Fraguas. A functional-logic perspective of parsing. In A. Middeldorp and T. Sato, editors, Functional and Logic Programming, volume 1722 of Lecture Notes in Computer Science, pages 85--99. Springer Berlin / Heidelberg, 1999.
[6]
R. Caballero and M. Rodríguez-Artalejo. A Declarative Debugging System for Lazy Functional Logic Programs. Electronic Notes in Theoretical Computer Science, 64: 113--175, 2002.
[7]
R. Caballero-Roldán. Técnicas de Diagnóstico y Depuración Declarativas para lenguajes lógico-funcionales. PhD thesis, Departamento de Sistemas Informáticos y Programación, Universidad Complutense de Madrid, 2004.
[8]
J. González-Moreno, M. Hortalá-González, F. López-Fraguas, and M. Rodrıguez-Artalejo. A rewriting logic for declarative programming. In Proc. European Symposium on Programming (ESOP'96), volume 1058 of LNCS, pages 156--172. Springer, 1996.
[9]
J. González-Moreno, M. Hortalá-González, F. López-Fraguas, and M. Rodrıguez-Artalejo. An approach to declarative programming based on a rewriting logic. Journal of Logic Programming, 40 (1): 47--87, 1999.
[10]
M. Hamana. Semantics for Interactive Higher-order Functional-Logic Programming. PhD thesis, University of Tsukuba, 1998.
[11]
M. Hanus. Curry: An Integrated Functional Logic Language (version 0.8.2, 2006). Available at: http://www.curry-language.org, 2006.
[12]
M. Hanus. Multi-paradigm declarative languages. In ICLP'07: Proceedings of the 23rd international conference on Logic programming, pages 45--75, Berlin, Heidelberg, 2007. Springer-Verlag.
[13]
S. P. Jones, editor. Haskell 98 Language and Libraries: The Revised Report. http://haskell.org/, September 2002. URL http://haskell.org/definition/haskell98-report.pdf.
[14]
R. Loogen, F. J. López-Fraguas, and M. Rodrıguez-Artalejo. A demand driven computation strategy for lazy narrowing. In PLILP '93: Proceedings of the 5th International Symposium on Programming Language Implementation and Logic Programming, pages 184--200, London, UK, 1993. Springer-Verlag.
[15]
F. López-Fraguas, J. Rodrıguez-Hortalá, and J. Sánchez-Hernández. Rewriting and call-time choice: The ho case. In J. Garrigue and M. Hermenegildo, editors, Functional and Logic Programming, volume 4989 of Lecture Notes in Computer Science, pages 147--162. Springer Berlin / Heidelberg, 2008.
[16]
E. Moggi. Notions of computation and monads. Information and Computation, 93: 55--92, 1989.
[17]
l. Naish and T. Barbour. A declarative debugger for a logical-functional language. In Eight International Conferencie on Industrial and Engineering Applications of Artificial Intelligence and Expert System - Invited and Additional Papers, volume 2, pages 91--99. DSTO General Document 51, 1995.
[18]
J. Paakki. Attribute grammar paradigmsa high-level methodology in language implementation. ACM Comput. Surv., 27: 196--255, June 1995.
[19]
P. Wadler. Comprehending monads. In LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming, pages 61--78, New York, NY, USA, 1990. ACM.

Index Terms

  1. A program transformation for returning states in functional-logic programs

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PEPM '11: Proceedings of the 20th ACM SIGPLAN workshop on Partial evaluation and program manipulation
    January 2011
    72 pages
    ISBN:9781450304856
    DOI:10.1145/1929501
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 24 January 2011

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. functional-logic languages
    2. program transformation
    3. statetul computations

    Qualifiers

    • Research-article

    Conference

    POPL '11
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 66 of 120 submissions, 55%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 102
      Total Downloads
    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media