Conditional narrowing without conditions

ABSTRACT

We present a new evaluation strategy for functional logic programs described by weakly orthogonal conditional term rewriting systems. Our notion of weakly orthogonal conditional rewrite system extends a notion of Bergstra and Klop and covers a large part of programs defined by conditional equations. Our strategy combines the flexibility of logic programming (computation of solutions for logic variables) with efficient evaluation methods from functional programming. In particular, it is the first known narrowing strategy for this class of programs that evaluates ground terms deterministically. This is achieved by a transformation of conditional term rewriting systems (CTRS) into unconditional ones which is sound and complete w.r.t. the semantics of the original CTRS. We show that the transformation preserves weak orthogonality for the terms of interest. This property allows us to apply a relatively efficient evaluation strategy for weakly orthogonal unconditional term rewriting systems (parallel narrowing) on the transformed programs.

REFERENCES

• 1: Sergio Antoy, Definitional Trees, Proceedings of the Third International Conference on Algebraic and Logic Programming, p.143-157, September 02-04, 1992
• 2: 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]
• 3: S. Antoy, R. Echahed, and M. Hanus. A parallel narrowing strategy. Technical report tr 96-1, Portland State University, 1996.
• 4: S. Antoy, R. Echahed, and M. Hanus. Parallel evaluation strategies for functional logic languages. In Proc. of the Fourteenth International Conference on Logic Programming (ICLP'97), pages 138--152. MIT Press, 1997.
• 5: Sergio Antoy , Rachid Echahed , Michael Hanus, A needed narrowing strategy, Journal of the ACM (JACM), v.47 n.4, p.776-822, July 2000 [doi>10.1145/347476.347484]
• 6: Sergio Antoy , Bart Massey , Michael Hanus , Frank Steiner, An implementation of narrowing strategies, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.207-217, September 05-07, 2001, Florence, Italy [doi>10.1145/773184.773206]
• 7: Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
• 8: J A Bergstra , J W Klop, Conditional rewrite rules: Confluence and termination, Journal of Computer and System Sciences, v.32 n.3, p.323-362, June 1986 [doi>10.1016/0022-0000(86)90033-4]
• 9: J. A. Bergstra , J. V. Tucker, Algebraic specifications of computable and semicomputable data types, Theoretical Computer Science, v.50 n.2, p.137-181, 1987 [doi>10.1016/0304-3975(87)90123-X]
• 10: D Bert , R Echahed, Design and implementation of a generic, logic and functional programming language, Proc. of the European symposium on programming on ESOP 86, p.119-132, March 1986, Saarbru:9Aicken, Germany
• 11: B. Brassel. Conditional narrowing with lazy evaluation (in german). Master's thesis, RWTH Aachen, 1999.
• 12: Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 13: Nachum Dershowitz , M. Okada, A rationale for conditional equational programming, Theoretical Computer Science, v.75 n.1-2, p.111-138, Sep. 1990 [doi>10.1016/0304-3975(90)90064-O]
• 14: L. Fribourg. SLOG: A logic programming language interpreter based on clausal superposition and rewriting. In Proc. IEEE Internat. Symposium on Logic Programming, pages 172--184, Boston, 1985.
• 15: Elio Giovannetti , Giorgio Levi , Corrado Moiso , Catuscia Palamidessi, Kernel-LEAF: a logic plus functional language, Journal of Computer and System Sciences, v.42 n.2, p.139-185, April 1991 [doi>10.1016/0022-0000(91)90009-T]
• 16: E. Giovannetti , C. Moiso, Notes on the elimination of conditions, 1st international workshop on Conditional Term Rewriting Systems, p.91-97, August 1988, Orsay, France
• 17: Michael Hanus, Compiling Logic Programs with Equality, Proceedings of the 2nd International Workshop on Programming Language Implementation and Logic Programming, p.387-400, August 20-22, 1990
• 18: M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19\&20:583--628, 1994.
• 19: M. Hanus. Reduction strategies for declarative programming. In B. Gramlich and S. Lucas, editors, Electronic Notes in Theoretical Computer Science, volume 57. Elsevier Science Publishers, 2001.
• 20: Michael Hanus , Salvador Lucas , Aart Middeldorp, Strongly sequential and inductively sequential term rewriting systems, Information Processing Letters, v.67 n.1, p.1-8, July 16, 1998 [doi>10.1016/S0020-0190(98)00016-7]
• 21: M. Hanus (ed.). Curry: An integrated functional logic language (vers. 0.8). Available at http://www.informatik.uni-kiel.de/~curry, 2003.
• 22: Claus Hintermeier, How to Transform Canonical Decreasing CTRSs into Equivalent Canonical TRSs, Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems, p.186-205, July 13-15, 1994
• 23: G. Huet and J.-J. Levy. Computations in orthogonal rewriting systems. In J.-L. Lassez and G. Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson, pages 395--443. MIT Press, 1991.
• 24: Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
• 25: J. W. Klop, Term rewriting systems, Handbook of logic in computer science (vol. 2): background: computational structures, Oxford University Press, Inc., New York, NY, 1993
• 26: J. Lloyd. Programming in an integrated functional and logic language. Journal of Functional and Logic Programming, (3):1--49, 1999.
• 27: Rita Loogen , Francisco Javier López-Fraguas , Mario Rodríguez-Artalejo, A Demand Driven Computation Strategy for Lazy Narrowing, Proceedings of the 5th International Symposium on Programming Language Implementation and Logic Programming, p.184-200, August 25-27, 1993
• 28: 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
• 29: Massimo Marchiori, Unravelings and Ultra-properties, Proceedings of the 5th International Conference on Algebraic and Logic Programming, p.107-121, September 25-27, 1996
• 30: Juan José Moreno-Navarro , Herbert Kuchen , Rita Loogen , Mario Rodríguez-Artalejo, Lazy Narrowing in a Graph Machine, Proceedings of the Second International Conference on Algebraic and Logic Programming, p.298-317, October 01-03, 1990
• 31: Juan Jose Moreno-Navarro , Mario Rodriguez-Artalejo, Logic programming with functions and predicates: the language Babel, Journal of Logic Programming, v.12 n.3, p.191-223, Feb. 1992 [doi>10.1016/0743-1066(92)90024-W]
• 32: Michael J. O'Donnell, Equational logic as a programming language, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 33: Enno Ohlebusch, Transforming Conditional Rewrite Systems with Extra Variables into Unconditional Systems, Proceedings of the 6th International Conference on Logic Programming and Automated Reasoning, p.111-130, September 06-10, 1999
• 34: G. Smolka. The Oz programming model. In J. van Leeuwen, editor, Computer Science Today: Recent Trends and Developments, pages 324--343. Springer LNCS 1000, 1995.
• 35: Z. Somogyi, F. Henderson, and T. Conway. The execution algorithm of Mercury, an efficient purely declarative logic programming language. Journal of Logic Programming, 29(1-3):17--64, 1996.
• 36: Patrick Viry, Elimination of conditions, Journal of Symbolic Computation, v.28 n.3, p.381-400, Sept. 1999 [doi>10.1006/jsco.1999.0288]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming

General Terms:
Languages, Theory

Keywords:
conditional rewriting, evaluation strategies, functional logic programming, narrowing