Static inference of modes and data dependencies in logic programs

ABSTRACT

Mode and data dependency analyses find many applications in the generation of efficient executable code for logic programs. For example, mode information can be used to generate specialized unification instructions where permissible, to detect determinacy and functionality of programs, generate index structures more intelligently, reduce the amount of runtime tests in systems that support goal suspension, and in the integration of logic and functional languages. Data dependency information can be used for various source-level optimizing transformations, to improve backtracking behavior and to parallelize logic programs. This paper describes and proves correct an algorithm for the static inference of modes and data dependencies in a program. The algorithm is shown to be quite efficient for programs commonly encountered in practice.

REFERENCES

• 1: BRUYNOOGHE, M., DEMOEN, B., CALLEBAUT, A., AND JANSSENS, C. Abstract interpretation: Towards the global optimization of Prolog programs. In Proceedings of the Fourth IEEE Symposium on Logic Programming (San Francisco, Sept. 1987). IEEE, New York, 1987.
• 2: CHANG, J., DESPAIN, A. M., AND DEGROOT, D. AND-parallelism of logic programs based on a static data dependency analysis. In Digest of Papers, Compcon 85 (Feb. 1985). IEEE, New York, 1985.
• 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, July 1985). IEEE, New York, 1985, pp. 10-21.
• 4: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 5: DEBRAY, S. K. Synthesizing control strategies for AND-parallel logic programs. Tech. Rep. 87-12, Dept. of Computer Science, Univ. of Arizona, Tucson, May 1987.
• 6: 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]
• 7: S. K. Debray, Unfold/fold transformations and loop optimization of logic programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.297-307, June 20-24, 1988, Atlanta, Georgia, United States
• 8: 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]
• 9: Saumya K. Debray , David S. Warren, Functional computations in logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.451-481, July 1989 [doi>10.1145/65979.65984]
• 10: S. K. Debray, Flow analysis of dynamic logic programs, Journal of Logic Programming, v.7 n.2, p.149-176, Sept. 1989 [doi>10.1016/0743-1066(89)90013-7]
• 11: DERANSART, P., AND MAEUSZYNSKI, J. Relating logic programs and attribute grammars. J. Logic Program. 2, 2 (July 1985), 119-156.
• 12: DIETRICH, S.W. Extension tables: Memo relations in logic programming. In Proceedings of the Fourth IEEE Symposium on Logic Programming (San ?rancisco, Sept. 1987). IEEE, New York, 1987, pp. 264-272.
• 13: JANSSENS, G., AND BRUYNOOGHE, M. An instance o ~ abstract interpretation integrating type and mode inferencing. In Proceedings of the Fifth International Conference on Logic Programming (Seattle, Wash., Aug. 1988). MIT Press, Cambridge, Mass., 1988, pp. 669-683.
• 14: JONES, N. D., AND MYCROFT, A. Stepwise development of operational and denotational semantics for PROLOG. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, New York, 1984, pp. 289-298.
• 15: MANNILA, H., AND UKKONEN, E. Flow analysis of Prolog programs. In Proceedings of the Fourth IEEE Symposium on Logic Programming (San ?rancisco, Sept. 1987). IEEE, New York, 1987.
• 16: MELLISH, C. S. The automatic generation of mode declarations for Prolog programs. DAI Research Paper 163, Dept. of Artificial Intelligence, Univ. of Edinburgh, Aug. 1981.
• 17: MELL!SH, C.S. Some global optimizations for a Prolog compiler. J. Logic Program. 2, I (Apr. 1985), 43-66.
• 18: C S Mellish, Abstract interpretation of Prolog programs, Proceedings on Third international conference on logic programming, p.463-474, September 1986, London, United Kingdom
• 19: Lee Naish, Negation and control in Prolog, Springer-Verlag New York, Inc., New York, NY, 1986
• 20: PLAISTED, D. The occur-check problem in Prolog. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, New York, 1984, pp. 272-280.
• 21: REDD~, U.S. Transformation of logic programs into fimctional programs. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, New York, 1984, pp. 187-196.
• 22: H Sondergaard, An application of abstract interpretation of logic programs: occur check reduction, Proc. of the European symposium on programming on ESOP 86, p.327-338, March 1986, Saarbru:9Aicken, Germany
• 23: Sicstus Prolog User's Manual. Swedish Institute of Co mputer Science, Sweden, Sept. 1987.
• 24: Hisao Tamaki , Taisuke Sato, OLD resolution with tabulation, Proceedings on Third international conference on logic programming, p.84-98, September 1986, London, United Kingdom
• 25: P. Van Roy , B. Demoen , Y. D. Willems, Improving the execution speed of compiled prolog with modes, clause selection, and determinism, II and Colloquium on Functional and Logic Programming and Specifications (CFLP) on TAPSOFT '87: Advanced Seminar on Foundations of Innovative Software Development, p.111-125, March 1987, Pisa, Italy
• 26: WARREN, D. H.D. Implementing Prolog--compiling predicate logic programs. Res. Reps. 39 and 40, Dept. of Artificial Intelligence, Univ. of Edinbu~'gh, 1977.
• 27: WARREN, R., HERMENEGILDO, M., AND DEBRAY, S. K. On the practicality of global flow analysis of logic programs. In Proceedings of the Fifth In~ ernational Conference on Logic P~'ogramming (Seattle, Wash., Aug. 1988). MIT Press, Cambridge, Mass., 1988.

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.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Predicate logic

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