Programming with singular and plural non-deterministic functions

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.

References

1. 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.
2. 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.
3. R. Caballero and F.J. López-Fraguas. Improving deterministic computations in lazy functional logic languages. Journal of Functional and Logic Programming, 2003, 2003.
4. 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.
5. 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.
6. 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.
7. S. Fischer, O. Kiselyov, and C.-c. Shan. Purely functional lazy non-deterministic programming. In Proc. 14th ACM SIGPLAN international conference on Functional programming (ICFP '09), pages 11--22. ACM, 2009.
8. 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.
9. 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.
10. M. Hanus. Functional logic programming: From theory to Curry. Technical report, Christian-Albrechts-Universität Kiel, 2005.
11. H. Hussmann. Non-Determinism in Algebraic Specifications and Algebraic Programs. Birkhäuser Verlag, 1993.
12. J. Launchbury. A natural semantics for lazy evaluation. In Proc. ACM Symposium on Principles of Programming Languages (POPL'93), pages 144--154. ACM, 1993.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. W. Lux. Curry mailing list: Type-classes and call-time choice vs. run-time choice. http://www.informatik.uni-kiel.de/~curry/listarchive/0790.html, August 2009.
19. J. Meseguer. Conditional rewriting logic as a unified model of concurrency. Theoretical Computer Science, 96(1):73--155, 1992.
20. R.J. Plasmeijer and M.C.J.D. van Eekelen. Functional Programming and Parallel Graph Rewriting. Addison-Wesley, 1993.
21. 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.
22. J. Rodríguez-Hortalá. Curry mailing list: Re: Type-classes and call-time choice vs. run-time choice. http://www.informatik.uni-kiel.de/~curry/listarchive/0801.html, August 2009.
23. 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.
24. H. Søndergaard and P. Sestoft. Non-determinism in functional languages. The Computer Journal, 35(5):514--523, 1992.
25. 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.
26. P. Wadler. How to replace failure by a list of successes. In Proc. Functional Programming and Computer Architecture. Springer LNCS 201, 1985.
27. 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.
28. 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.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

    • General programming languages

      • Language types

• Theory of computation

  • Formal languages and automata theory