Programming with Singular and Plural Non-deterministic Functions
| dc.book.title | PEPM '10: PROCEEDINGS OF THE 2010 ACM SIGPLAN WORKSHOP ON PARTIAL EVALUATION AND PROGRAM | |
| dc.contributor.author | Riesco Rodríguez, Adrián | |
| dc.contributor.author | Rodríguez-Hortalá, Juan | |
| dc.date.accessioned | 2023-06-20T05:44:45Z | |
| dc.date.available | 2023-06-20T05:44:45Z | |
| dc.date.issued | 2010 | |
| dc.description | ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation; Jan 18-19, 2010; Madrid, Spain | |
| dc.description.abstract | Non-strict non-deterministic functions are one of the most distinctive features of functional-logic languages. Traditionally, two semantic alternatives have been considered for this kind of functions: call-time choice and run-time choice. While the former is the standard choice of modern implementations of FLP, the latter lacks some basic properties mainly compositionality that have prevented its use in practical FLP implementations. Recently, a new compositional plural semantics for FLP has been proposed. Although this semantics allows an elegant encoding of some problems in particular those with an implicit manipulation of sets of values, call-time choice still remains the best option for many common programming patterns. In this paper we explore the expressive possibilities of the combination of singular and plural non-determinism. After formalizing the intended semantics by means of a logic calculus, several significant examples exploiting the capabilities of the semantics are presented. These examples have been tested and developed in a Maude-based prototype whose implementation is outlined. | |
| dc.description.department | Sección Deptal. de Sistemas Informáticos y Computación | |
| dc.description.faculty | Fac. de Ciencias Matemáticas | |
| dc.description.refereed | TRUE | |
| dc.description.status | pub | |
| dc.eprint.id | https://eprints.ucm.es/id/eprint/17952 | |
| dc.identifier.doi | 10.1145/1706356.1706373 | |
| dc.identifier.isbn | 978-1-60558-727-1 | |
| dc.identifier.officialurl | http://delivery.acm.org/10.1145/1710000/1706373/p83- | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14352/45388 | |
| dc.language.iso | eng | |
| dc.page.final | 92 | |
| dc.page.initial | 83 | |
| dc.publication.place | New York | |
| dc.publisher | ACM | |
| dc.relation.projectID | Spanish project DESAFIOS (TIN2006-15660-C02-01) | |
| dc.relation.projectID | PROMESAS-CAM (S-0505/TIC/0407) | |
| dc.relation.projectID | FAST-STAMP (TIN2008-06622-C03-01/TIN) | |
| dc.relation.projectID | UCM-BSCH-GR58/08-910502 | |
| dc.rights.accessRights | restricted access | |
| dc.subject.cdu | 004.43 | |
| dc.subject.keyword | Non-deterministic functions | |
| dc.subject.keyword | Semantics | |
| dc.subject.keyword | Program transformation | |
| dc.subject.keyword | Term rewriting | |
| dc.subject.keyword | Maude | |
| dc.subject.ucm | Lenguajes de programación | |
| dc.subject.unesco | 1203.23 Lenguajes de Programación | |
| dc.title | Programming with Singular and Plural Non-deterministic Functions | |
| dc.type | book part | |
| dcterms.references | E. Albert, M. Hanus, F. Huch, J. Oliver, and G. Vidal. Operational semantics for declarative multi-paradigm languages. Journal of Symbolic Computation, 40(1):795–829, 2005. B. Braßel and F. Huch. On a tighter integration of functional and logic programming. In Proc. 5th Asian Symposium on Programming Languages and Systems (APLAS’07), Springer LNCS 4807, pages 122–138, 2007. R. Caballero and F. J. López-Fraguas. Improving deterministic computations in lazy functional logic languages. Journal of Functional and Logic Programming, 2003, 2003. M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martí Oliet, J. Meseguer, and C. Talcott. All About Maude: A High-Performance Logical Framework, Springer LNCS 4350, 2007. M. Clavel, J. Meseguer, and M. Palomino. Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic. Theoretical Computer Science, 373(1-2): 70–91, 2007. S. Escobar. Implementing natural rewriting and narrowing efficiently. In Proc. 7th International Symposium on Functional and Logic Programming (FLOPS’04), Springer LNCS 2998, pages 147–162, 2004. S. Fischer, O. Kiselyov, and C.-c. Shan. Purely functional lazy nondeterministic programming. In Proc. 14th ACM SIGPLAN international conference on Functional programming (ICFP ’09), pages 11–22. ACM, 2009. J. González-Moreno, M. Hortalá-González, and M. Rodríguez-Artalejo. A higher order rewriting logic for functional logic programming. In Proc. International Conference on Logic Programming (ICLP’97), pages 153–167. MIT Press, 1997. J. C. González-Moreno, T. 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. M. Hanus. Functional logic programming: From theory to Curry. Technical report, Christian-Albrechts-Universit¨at Kiel, 2005. H. Hussmann. Non-Determinism in Algebraic Specifications and Algebraic Programs. Birkhäuser Verlag, 1993. J. Launchbury. A natural semantics for lazy evaluation. In Proc. ACM Symposium on Principles of Programming Languages (POPL’93), pages 144–154. ACM, 1993. F. J. López-Fraguas, J. Rodríguez-Hortalá, and J. Sánchez-Hernández. A lightweight combination of semantics for non-deterministic functions. In Proc. 18th Workshop on Logic-based methods in Programming Environments (WLPE’08), CoRR, abs/0903.2205, 2009. F. López-Fraguas and J. Sánchez-Hernández. T OY: A multiparadigm declarative system. In Proc. Rewriting Techniques and Applications (RTA’99), pages 244–247. Springer LNCS 1631, 1999. F. López-Fraguas, J. Rodríguez-Hortalá, and J. Sánchez-Hernández. A simple rewrite notion for call-time choice semantics. In Proc. Principles and Practice of Declarative Programming (PPDP’07), pages 197–208. ACM, 2007. F. López-Fraguas, J. Rodríguez-Hortalá, and J. Sánchez-Hernández. Rewriting and call-time choice: the HO case. In Proc. 9th International Symposium on Functional and Logic Programming (FLOPS’08), Springer LNCS 4989, pages 147–162, 2008. F. López-Fraguas, J. Rodríguez-Hortalá, and J. Sánchez-Hernández. A flexible framework for programming with non-deterministic functions. In Proc. 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation (PEPM’09), pages 91–100. ACM, 2009. W. Lux. Curry mailing list: Type-classes and call-time choice vs. runtime choice. http://www.informatik.uni-kiel.de/~curry/ listarchive/0790.html, August 2009. J. Meseguer. Conditional rewriting logic as a unified model of concurrency. Theoretical Computer Science, 96(1):73–155, 1992. R. J. Plasmeijer and M. C. J. D. van Eekelen. Functional Programming and Parallel Graph Rewriting. Addison-Wesley, 1993. A. Riesco and J. Rodríguez-Hortalá. A natural implementation of plural semantics in Maude. In Proc. 9th Workshop on Language Descriptions Tools and Applications (LDTA’09), 2009. J. Rodríguez-Hortalá. Curry mailing list: Re: Type-classes and call-time choice vs. run-time choice. http://www.informatik.unikiel.de/~curry/listarchive/0801.html, August 2009. J. Rodríguez-Hortalá. A hierarchy of semantics for non-deterministic term rewriting systems. In Proc. Foundations of Software Technology and Theoretical Computer Science (FSTTCS’08), 2008. H. Søndergaard and P. Sestoft. Non-determinism in functional languages. The Computer Journal, 35(5):514–523, 1992. A. Verdejo and N. Martí-Oliet. Two case studies of semantics execution in Maude: CCS and LOTOS. Formal Methods in System Design, 27:113–172, 2005. P. Wadler. How to replace failure by a list of successes. In Proc. Functional Programming and Computer Architecture. Springer LNCS201, 1985. P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad hoc. In Pro.16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 60–76. ACM, 1989. D. H. Warren. Higher-order extensions to Prolog: are they needed? In J. Hayes, D. Michie, and Y.-H. Pao, editors, Machine Intelligence 10, pages 441–454. Ellis Horwood Ltd., 1982. | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 068dda11-d320-4634-a908-28a4bc4b0eb4 | |
| relation.isAuthorOfPublication.latestForDiscovery | 068dda11-d320-4634-a908-28a4bc4b0eb4 |
Download
Original bundle
1 - 1 of 1