An implementation of narrowing strategies

ABSTRACT

This paper describes an implementation of narrowing, an essential component of implementations of modern functional logic languages. These implementations rely on narrowing, in particular on some optimal narrowing strategies, to execute functional logic programs. We translate functional logic programs into imperative (Java) programs without an intermediate abstract machine. A central idea of our approach is the explicit representation and processing of narrowing computations as data objects. This enables the implementation of operationally complete strategies (i.e., without backtracking) or techniques for search control (e.g., encapsulated search). Thanks to the use of an intermediate and portable represen tation of programs, our implementation is general enough to be used as a common back end for a wide variety of functional logic languages.

REFERENCES

• 1: H. Aït-Kaci, P. Lincoln, and R. Nasr. Le Fun: Logic, equations, and functions. In Proc. 4th IEEE Internat. Symposium on Logic Programming, pages 17--23, San Francisco, 1987.
• 2: Elvira Albert , Michael Hanus , Germán Vidal, A Practical Partial Evaluator for a Multi-Paradigm Declarative Language, Proceedings of the 5th International Symposium on Functional and Logic Programming, p.326-342, March 07-09, 2001
• 3: Sergio Antoy, Definitional Trees, Proceedings of the Third International Conference on Algebraic and Logic Programming, p.143-157, September 02-04, 1992
• 4: S. Antoy. Needed narrowing in Prolog. Technical report 96-2, Portland State University, 1996.
• 5: 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
• 6: 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]
• 7: Sergio Antoy , Rachid Echahed , Michael Hanus, A needed narrowing strategy, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.268-279, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177899]
• 8: 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
• 9: Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
• 10: Staffan Bonnier , Jan Maluszynski, Towards a Clean Amalgamation of Logic Programs with External Procedures, Proceedings of the 1st International Workshop on Programming Language Implementation and Logic Programming, p.20-34, May 16-18, 1988
• 11: M. Chakravarty and H. Lock. Towards the uniform implementation of declarative languages. Computer Languages, 23(2--4):121--160, 1997.
• 12: Pui Hung Cheong , Laurent Fribourg, Implementation of narrowing: the Prolog-based approach, Logic programming languages: constraints, functions, and objects, MIT Press, Cambridge, MA, 1993
• 13: Enrico Denti , Andrea Omicini , Alessandro Ricci, tu Prolog: A Light-Weight Prolog for Internet Applications and Infrastructures, Proceedings of the Third International Symposium on Practical Aspects of Declarative Languages, p.184-198, March 11-12, 2001
• 14: M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19&20:583--628, 1994.
• 15: Michael Hanus, Efficient Translation of Lazy Functional Logic Programs into Prolog, Proceedings of the 5th International Workshop on Logic Programming Synthesis and Transformation, p.252-266, September 20-22, 1995
• 16: Michael Hanus, A unified computation model for functional and logic programming, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-93, January 15-17, 1997, Paris, France [doi>10.1145/263699.263710]
• 17: M. Hanus, S. Antoy, J. Koj, R. Sadre, and F. Steiner. PAKCS 1.3: The Portland Aachen Kiel Curry System User Manual. Technical report, University of Kiel, Germany, 2000. Available at http://www.informatik.uni-kiel.de/~pakcs.
• 18: Michael Hanus , Christian Prehofer, Higher-order narrowing with definitional trees, Journal of Functional Programming, v.9 n.1, p.33-75, January 1999 [doi>10.1017/S0956796899003330]
• 19: M. Hanus and R. Sadre. An abstract machine for Curry and its concurrent implementation in Java. Journal of Functional and Logic Programming, 1999(6), 1999.
• 20: Michael Hanus , Frank Steiner, Controlling Search in Declarative Programs, Proceedings of the 10th International Symposium on Principles of Declarative Programming, p.374-390, September 16-18, 1998
• 21: M. Hanus (ed.). Curry: An Integrated Functional Logic Language. Available at http://www.informatik.uni-kiel.de/~curry, 2000.
• 22: Maria Teresa Hortalá-González , Eva Ullán, An Abstract Machine Based System for a Lazy Narrowing Calculus, Proceedings of the 5th International Symposium on Functional and Logic Programming, p.216-232, March 07-09, 2001
• 23: G. Huet and J.-J. Lévy. 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: S. Janson. AKL -- A Multiparadigm Programming Language. PhD thesis, Swedish Institute of Computer Science, 1994.
• 25: J. Lloyd. Programming in an integrated functional and logic language. Journal of Functional and Logic Programming, 1999(3):1--49, 1999.
• 26: R. Loogen. Relating the implementation techniques of functional and functional logic languages. New Generation Computing, 11:179--215, 1993.
• 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: Wolfgang Lux, Implementing Encapsulated Search for a Lazy Functional Logic Language, Proceedings of the 4th Fuji International Symposium on Functional and Logic Programming, p.100-113, November 11-13, 1999
• 30: Aart Middeldorp, Call by need computations to root-stable form, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.94-105, January 15-17, 1997, Paris, France [doi>10.1145/263699.263711]
• 31: Christian Schulte , Gert Smolka, Encapsulated search for higher-order concurrent constraint programming, Proceedings of the 1994 International Symposium on Logic programming, p.505-520, November 1994, Symposia, Melbourne
• 32: James R. Slagle, Automated Theorem-Proving for Theories with Simplifiers Commutativity, and Associativity, Journal of the ACM (JACM), v.21 n.4, p.622-642, Oct. 1974 [doi>10.1145/321850.321859]
• 33: P. Tarau. Jinni. Available at http://www.binnetcorp.com/Jinni/, 2001.
• 34: D. Warren. Higher-order extensions to Prolog: are they needed? In Machine Intelligence 10, pages 441--454, 1982.

INDEX TERMS

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

General Terms:
Design, Experimentation, Languages, Theory

Keywords:
Curry, Java, XML, functional logic, narrowing