Pattern driven lazy reduction: A unifying evaluation mechanism for functional and logic programs

ABSTRACT

A novel lazy evaluation mechanism, pattern-driven lazy reduction, is developed that serves as a unifying evaluation mechanism for both functional and logic programs. The reduction of a function call can be viewed as “semantically” unifying the function call with the left hand side of a defining equation, and applying the unifier to the right hand side. Lazy reduction is achieved by the pattern which the function call matches against. Function reductions are actually “driven” by patterns in this sense. It is shown that this evaluation mechanism works well for both functional programs and logic programs that involve “executable” functions. As a result, logic programs can be enhanced with (1) the availability of a functional computing environment where there is no notion of backtracking, thus alleviating the degree of control difficulties typically encountered in logic programs, and (2) the ability to terminate “infinite computations” without the introduction of complex control issues at the user-level. On the other hand, functional programs can be equipped with the power of logic programming languages, e.g., Prolog.

REFERENCES

• 1: Kenneth A. Bowen, Prolog, Proceedings of the 1979 annual conference, p.14-23, January 1979 [doi>10.1145/800177.810020]
• 2: R. M.Burstall and D.T. Sannella. HOPE User's Manual. Dept. of Computer Science, University of Edinburgh, Edinburgh, Scotland, 1980.
• 3: Keith L. Clark , Steve Gregory, A relational language for parallel programming, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.171-178, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806776]
• 4: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 5: M. H.van Emden. Programming with resolution logic. Machine Intelligence 8, London, 1978, pp. 266-299.
• 6: D. P.Friedman and D.S. Wise. CONS should not Evaluate Its Arguments. Automata, Languages and Programming, Edinburgh, 1976.
• 7: The Utah Symbolic Computation Group. The Portable Standard Lisp Users Manual. 3.1 edition, Dept. of Computer Science, University of Utah, 1983.
• 8: A. Hansson, S.Haridi and S.-A. Tarnlund. Properties of a logic programming language. Logic programming, New York, 1982, pp. 267-280.
• 9: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 10: Robert M.Keller. Semantics and applications of function graphs. Tech. Rept. UUCS-8-112, University of Utah, Dept. of Computer Science, October, 1980.
• 11: Bill Kornfeld. Equality for Prolog. 8th International Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, August, 1983.
• 12: R.A.Kowalski. Predicate logic as a programming language. Proceeding of IFIP 74, 74, pp. 556-574.
• 13: Alberto Martelli , Ugo Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.258-282, April 1982 [doi>10.1145/357162.357169]
• 14: Luis Moniz Pereira, Fernando C N Pereira and David H.D. Warren. User's Guide to DECsystem-10 Prolog. 1978.
• 15: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 16: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 17: J. A.Robinson and E.E. Sibert. Logic programming in Lisp. School of Computer and Information Science, Syracuse University, December, 1980.
• 18: D.A.Turner. SASL Language Manual. University of St. Andrews, 1979.
• 19: David H D Warren , Luis M. Pereira , Fernando Pereira, Prolog - the language and its implementation compared with Lisp, ACM SIGPLAN Notices, v.12 n.8, p.109-115, August 1977

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Patterns

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.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Algorithms, Languages, Theory