Computing with subspaces

ABSTRACT

We propose a new definition and use of a primitive getAllValues, for computing all the values of a non-deterministic expression in a functional logic program. Our proposal restricts the validity of the argument of getAllValues. This restriction ensures that essential language features like the call-time choice semantics, the independence of the order of evaluation, and the referential transparency of the language are preserved when getAllValues is executed. Up to now, conflicts between these language features and primitives like getAllValues have been seen as one of the main problems for employing such primitives in functional logic languages.

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: Sergio Antoy, Definitional Trees, Proceedings of the Third International Conference on Algebraic and Logic Programming, p.143-157, September 02-04, 1992
• 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, Constructor-based conditional narrowing, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.199-206, September 05-07, 2001, Florence, Italy [doi>10.1145/773184.773205]
• 5: S. Antoy. Evaluation strategies for functional logic programming. Journal of Symbolic Computation, 40(1):875--903, 2005.
• 6: S. Antoy, D. Brown, and S. Chiang. Lazy context cloning for non-deterministic graph rewriting. In Proc. of the 3rd International Workshop on Term Graph Rewriting, Termgraph'06, pages 61--70, Vienna, Austria, April 2006. Extended version to appear in ENTCS.
• 7: S. Antoy, D. Brown, and S. Chiang. On the correctness of bubbling. In F. Pfenning, editor, 17th International Conference on Rewriting Techniques and Applications (RTA'06). Springer, 2006.
• 8: S. Antoy, R. Echahed, and M. Hanus. Parallel evaluation strategies for functional logic languages. In Proceedings of the 14th International Conference on Logic Programming (ICLP'97), pages 138--152, Leuven, Belgium, July 1997.
• 9: S. Antoy and M. Hanus. Overlapping rules and logic variables in functional logic programs. In Twenty Second International Conference on Logic Programming, pages 87--101, Seattle, WA, Aug. 2006. Springer LNCS 4079.
• 10: Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
• 11: J. W. Klop , Marc Bezem , R. C. De Vrijer, Term Rewriting Systems, Cambridge University Press, New York, NY, 2001
• 12: B. Braßel, M. Hanus, and F. Huch. Encapsulating non-determinism in functional logic computations. Journal of Functional and Logic Programming, 2004(6), 2004.
• 13: Bernd Braβel , Frank Huch, Translating curry to haskell system demo, Proceedings of the 2005 ACM SIGPLAN workshop on Curry and functional logic programming, September 29-29, 2005, Tallinn, Estonia [doi>10.1145/1085099.1085112]
• 14: Nachum Dershowitz, Equational programming, Machine intelligence 11, Oxford University Press, Inc., New York, NY, 1988
• 15: R. Echahed and J. -C. Janodet. On constructor-based graph rewriting systems. Research Report 985-I, IMAG, 1997. Available at http://citeseer.ist.psu.edu/echahed97constructorbased.html.
• 16: J. C. González Moreno, F. J. López Fraguas, M. T. Hortalá González, and M. Rodríguez Artalejo. An approach to declarative programming based on a rewriting logic. The Journal of Logic Programming, 40:47--87, 1999.
• 17: M. Hanus (ed.). Curry: An integrated functional logic language (vers.0.8.2). Available at http://www.informatik.uni-kiel.de/~ curry, March 28, 2006.
• 18: M. Hanus (ed.). PAKCS 1.7.3: The Portland Aachen Kiel Curry System. Available at http://www.informatik.uni-kiel.de/~pakcs, Sept. 4, 2006.
• 19: Heinrich Hussmann, Nondeterministic algebraic specifications and nonconfluent term rewriting, Journal of Logic Programming, v.12 n.3, p.237-255, Feb. 1992 [doi>10.1016/0743-1066(92)90026-Y ]
• 20: 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
• 21: W. Lux. An abstract machine for the efficient implementation of Curry. In H. Kuchen, editor, Workshop on Functional and Logic Programming, Arbeitsbericht No. 63. Institut für Wirtschaftsinformatik, Universität Münster, 1998.
• 22: Michael J. O'Donnell, Computing in Systems Described by Equations, Springer-Verlag New York, Inc., Secaucus, NJ, 1977
• 23: Advanced topics in term rewriting, Springer-Verlag, London, 2002
• 24: D. Plump, Term graph rewriting, Handbook of graph grammars and computing by graph transformation: vol. 2: applications, languages, and tools, World Scientific Publishing Co., Inc., River Edge, NJ, 1999
• 25: Uday S. Reddy. Narrowing as the operational semantics of functional languages. In Proceedings of the IEEE International Symposium on Logic in Computer Science, pages 138--151, Boston, 1985.
• 26: Programming constraint services: high-level programming of standard and new constraint services, Springer-Verlag, London, 2002
• 27: R. C. Sekar , I. V. Ramakrishnan, Programming in equational logic: beyond strong sequentiality, Information and Computation, v.104 n.1, p.78-109, May 1993 [doi>10.1006/inco.1993.1026 ]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

General Terms:
Algorithms, Design, Languages

Keywords:
functional logic programming languages, non-determinism, rewrite systems, subspaces