Functional computations in logic programs

ABSTRACT

Although the ability to simulate nondeterminism and to compute multiple solutions for a single query is a powerful and attractive feature of logic programming languages, it is expensive in both time and space. Since programs in such languages are very often functional, that is, they do not produce more than one distinct solution for a single input, this overhead is especially undesirable. This paper describes how programs may be analyzed statically to determine which literals and predicates are functional, and how the program may then be optimized using this information. Our notion of “functionality” subsumes the notion of “determinacy” that has been considered by various researchers. Our algorithm is less reliant on language features such as the cut, and thus extends more easily to parallel execution strategies, than others that have been proposed.

REFERENCES

• 1: BRUYNOOGHE, M., AND PEREIRA, L. M. Deduction revision by intelligent backtracking. In Implementations of Prolog, J. A. Campbell, Ed. Ellis Horwood Ltd., Chichester, 1984, pp. 194-215.
• 2: BUTLER, R., LUSK, E. L., OLSON, R., AND OVERBEEK, R.A. ANLWAM: A parallel implementation of the Warren abstract machine. Intern. Rep., Argonne National Laboratory, Chicago, Ill., 1986.
• 3: CHANG, J., AND DESPAIN, A.M. Semi-intelligent backtracking of Prolog based on static data dependency analysis. In Proceedings of the 1985 Symposium on Logic Programming (Boston, Mass., Feb. 1985). IEEE, Washington, D.C., 1985, pp. 10-21.
• 4: CLARK, $. r. Negation as failure. In Logic and Data Bases, H. Gallaire and J. Minker, Eds. Plenum, New York, 1978.
• 5: John S. Conery, Parallel execution of logic programs, Kluwer Academic Publishers, Norwell, MA, 1986
• 6: DEBRAY, S.K. The SB-Prolog system, version 2.3.2: A user manual. Tech. Rep. 87-15, Dept. of Computer Science, Univ. of Arizona, Tucson, Ariz., Dec. 1987. (Revised March 1988.)
• 7: Saumya K. Debray , Prateek Mishra, Denotational and operational semantics for Prolog, Journal of Logic Programming, v.5 n.1, p.61-91, March 1988 [doi>10.1016/0743-1066(88)90007-6]
• 8: Saumya K. Debray , David S. Warren, Automatic mode inference for logic programs, Journal of Logic Programming, v.5 n.3, p.207-229, Sept. 1988 [doi>10.1016/0743-1066(88)90010-6]
• 9: DEGROOT, D. Restricted AND-parallelism. In Proceedings of the International Conference on Fifth Generation Computer Systems ICOT, (Tokyo, 1984 ).
• 10: DERANSART, P., AND MALUSZYNSKI, J. Relating logic programs and attribute grammars. J. Logic Program. 2, 2 (July 1985), 119-156.
• 11: HAUSMAN, B., CIEPIELEWSKI, A., AND HARIDI, S. Or-parallel Prolog made efficient on shared memory multiproeessors. In Proceedings of the 1987 IEEE Symposium on Logic Programming (San Francisco, Calif., Aug. 1987). IEEE, New York, 191~7, pp. 69-79.
• 12: Manuel V Hermenegildo, An abstract machine for restricted AND-parallel execution of logic programs, Proceedings on Third international conference on logic programming, p.25-39, September 1986, London, United Kingdom
• 13: JONES, N. D., AND MYCROrT, A. Stepwise developmenL of operational and denotational semantics for PROLOG. In Proceedings of the 1984 Internatwnal Symposium on Logic Programming (Atlantic City, N.J., Feb. 6-9, 1984). IEEE, New York, ~.984, pp. 289-298.
• 14: KALE, L. V. The REDUCE-OR process model for parallel evaluation of logic programs. In Proceedings of the 4th International Conference on Logi( Programming. (Melbourne, May 25-29, 1987). MIT Press, Cambridge, Mass., 1987, pp. 616-632
• 15: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 16: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 17: MELLISH, C.S. Some global optimizations for a Prok,g compiler. J. Logic Program. 2, I (Apr. 1985), 43-66.
• 18: MENOELZON, A.O. Functional dependencies in logic programs. In Proceedings of the 11th ACM International Conference on Very Large Data Bases (Stockholm, Aug. 1985). ACM, New York, 1985.
• 19: Lee Naish, Negations and quantifiers in NU-Prolog, Proceedings on Third international conference on logic programming, p.624-634, September 1986, London, United Kingdom
• 20: Lee Naish, Negation and control in Prolog, Springer-Verlag New York, Inc., New York, NY, 1986
• 21: O'KEEFE, R.A. On the treatment of cuts in Prolog sou me-level tools. In Proceedings of the 1985 Symposium on Logic Programming (Boston, Mass., Julv 15-18, 1985) IEEE, Washington, D.C., 1985, pp. 73-77.
• 22: OVERBEEK, R. a., GABRIEL, J., LINDHOLM, W., AND I. USK, E.L. Prolog on multiprocessors. Intern. Rep., Argonne National Laboratory, Chicago, IlL 1985.
• 23: ROBINSON, J.A. Logic programming--Past, present end future. New Generation Comput. I, 2 (1983).
• 24: SAWAMURA, $., AND TAKESHIMA, T. Recursive unsob~ability of determinacy, solvable cases of determinacy and their applications to Prolog optimizati(,n. In Proceedings of the 1985 Symposium on Logic Programming (Boston, Mass., July 15-18, 19~5). IEEE, Washington, D.C., 1985, pp. 200-207.
• 25: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 26: WARREN, D. $. D. Implementing Prolog--Compiling predicate logic programs. Res. Reps. 39 and 40, Dept. of Artificial Intelligence, Univ. of Edinbul'gh, 1977.
• 27: WARREN, D. H.D. Efficient processing of interactive relational database queries expressed in logic. In Proceedings of the 7th Conference on Very Large Data Bases (Cannes, Sept. 9-11, 1981). ACM, New York, 1981, pp. 272-281.
• 28: WARREN, D. $. D. An abstract Prolog instruction set. Tech. Note 309, SRI International, Menlo Park, Calif., Oct. 1983.
• 29: WARREN, D. $. D. The SRI model for or-parallel execution of Prolog--Abstract design and implementation issues. In Proceedings of the 1987 IEEE Symposium on Logic Programming (San Francisco, Calif., Aug. 31-Sept. 4, 1987). IEEE, New Ycrk, pp. 92-102.
• 30: WARREN, D. S., AHAMAD, M., DEBRAY, S. K., AND KALE, L.V. Executing distributed Prolog programs on a broadcast network. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, Washington, D.C., 1984.
• 31: WESTPHAL, H., ROBERT, P., CHASSIN, J., AND SYRE, J. The PEPSys model: Combining backtracking, AND- and OR-parallelism. In Proceedings of the 1987 IEEE Symposium on Logic Programming, (San Francisco, Calif., Aug. 31-Sept. 4, 1987). IEEE, New York, 1987, pp. 436-448.
• 32: WISE, M.J. Epilog: Reinterpreting and extending Prolog for a multiprocessor environment. In Implementations o{ Prolog, J. A. Campbell, Ed. Ellis Horwood Ltd., Chichester, 1984, pp. 341-351.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Languages, Performance, Verification