A flexible framework for programming with non-deterministicfunctions

ABSTRACT

The possibility of non-deterministic reductions is a distinctive feature of some declarative languages. Two semantics commonly adopted for non-determinism are call-time choice-- a notion that at the operational level is related to the sharing mechanism of lazy evaluation in functional languages-- and run-time choice, which corresponds closely to ordinary term rewriting. But there are practical situations where neither semantics is appropriate, if used in isolation. In this paper we propose to annotate functions in a program with the semantics most adequate to its intended use. Annotated programs are then mapped into a unified core language (but still high level), designed to achieve a careful but neat combination of ordinary rewriting --to cope with run-time choice-- with local bindings via a let-construct devised to express call-time choice. The result is a flexible framework into which existing languages using pure run-time or call-time choice can be embedded, either directly --in the case of run-time choice-- or by means of a simple program transformation introducing lets in function definitions --for the case of call-time choice--. We prove the adequacy of the embedding, as well as other relevant properties of the framework.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: 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.
• 3: Sergio Antoy, Optimal Non-deterministic Functional Logic Computations, Proceedings of the 6th International Joint Conference on Algebraic and Logic Programming, p.16-30, September 03-05, 1997
• 4: Sergio Antoy , Michael Hanus, Compiling Multi-Paradigm Declarative Programs into Prolog, Proceedings of the Third International Workshop on Frontiers of Combining Systems, p.171-185, March 22-24, 2000
• 5: Sergio Antoy , Andrew P. Tolmach, Typed Higher-Order Narrowing without Higher-Order Strategies, Proceedings of the 4th Fuji International Symposium on Functional and Logic Programming, p.335-353, November 11-13, 1999
• 6: Zena M. Ariola , Matthias Felleisen, The call-by-need lambda calculus, Journal of Functional Programming, v.7 n.3, p.265-301, May 1997 [doi>10.1017/S0956796897002724]
• 7: Zena M. Ariola , John Maraist , Martin Odersky , Matthias Felleisen , Philip Wadler, A call-by-need lambda calculus, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-246, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199507]
• 8: R. Caballero-Roldan and F. Lopez-Fraguas. Parsing with nondeterministic functions. In Proc. APPIA-GULP-PRODE'98, 1--16, 1998.
• 9: M. Clavel, F. Duran, S. Eker, P. Lincoln, N. Marti-Oliet, J. Meseguer, and C. Talcott. All About Maude. Springer LNCS 4350, 2007.
• 10: R. Echahed and J.-C. Janodet. On constructor-based graph rewriting systems. Research Report 985-I, IMAG, 1997.
• 11: J. Gonzalez-Moreno, M. Hortala-Gonzalez, and M. Rodriguez-Artalejo. A higher order rewriting logic for functional logic programming. In Proc. Int. Conf. on Logic Programming (ICLP'97), 153--167. MIT Press, 1997.
• 12: J. C. Gonzalez-Moreno. A correctness proof for Warren's HO into FO translation. In Proc. GULP'93, 569--584, 1993.
• 13: J. C. González-Moreno , Maria Teresa Hortalá-González , Francisco Javier López-Fraguas , Mario Rodríguez-Artalejo, A Rewriting Logic for Declarative Programming, Proceedings of the 6th European Symposium on Programming Languages and Systems, p.156-172, April 22-24, 1996
• 14: J. C. Gonzalez-Moreno, T. Hortala-Gonzalez, F. Lopez-Fraguas, and M. Rodriguez-Artalejo. An approach to declarative programming based on a rewriting logic. Journal of Logic Programming, 40(1):47--87, 1999.
• 15: M. Hanus. Multi-paradigm declarative languages. In Proc. Int. Conf. on Logic Programming (ICLP'07), 45--75. Springer LNCS 4670, 2007.
• 16: M. Hanus (ed.). Curry: An integrated functional logic language (version 0.8.2). Available at http://www.informatik.unikiel. de/~curry/report.html, March 2006.
• 17: J. Hughes, Why functional programming matters, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• 18: Heinrich Hussmann, Nondeterminism in algebraic specifications and algebraic programs, Birkhauser Verlag, Basel, Switzerland, 1993
• 19: John Launchbury, A natural semantics for lazy evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.144-154, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158618]
• 20: F. Lopez-Fraguas, J. Rodriguez-Hortala, and J. Sanchez-Hernandez. Narrowing for non-determinism with call-time choice semantics. In Proc. Workshop on Logic Programming (WLP'07), Tech. Rep. 434 Univ. Wurzburg, 224--233, 2007.
• 21: Francisco J. López-Fraguas , Juan Rodríguez-Hortalá , Jaime Sánchez-Hernández, A simple rewrite notion for call-time choice semantics, Proceedings of the 9th ACM SIGPLAN international conference on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland [doi>10.1145/1273920.1273947]
• 22: Francisco J. Lopez-Fraguas , Juan Rodriguez-Hortala , Jaime Sanchez-Hernandez, A flexible framework for programming with non-deterministicfunctions, Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, January 19-20, 2009, Savannah, GA, USA [doi>10.1145/1480945.1480959]
• 23: F. Lopez-Fraguas, J. Rodriguez-Hortala, and J. Sanchez-Hernandez. Rewriting and call-time choice: the HO case. In Proc. Fuji Int. Symp. on Functional and Logic Programming (FLOPS'08), 147--162, Springer LNCS 4989, 2008.
• 24: F. Lopez-Fraguas, J. Rodriguez-Hortala, and J. Sanchez-Hernandez. A Lightweight Combination of Semantics for Non-deterministic Functions. In Proc. Workshop on Logic Programming Environments (WLPE'08), 2008.
• 25: Francisco Javier López-Fraguas , Jaime Sánchez Hernández, TOY: A Multiparadigm Declarative System, Proceedings of the 10th International Conference on Rewriting Techniques and Applications, p.244-247, July 02-04, 1999
• 26: H. Søndergaard , P. Sestoft, Non-determinism in functional languages, The Computer Journal, v.35 n.5, p.514-523, Oct. 1992 [doi>10.1093/comjnl/35.5.514]
• 27: 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

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Nondeterministic languages**

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Languages, Theory

Keywords:
call-time choice, local bindings, non-deterministic functions, run-time-choice, term rewriting systems