Analyzing logic programs with dynamic scheduling

ABSTRACT

Traditional logic programming languages, such as Prolog, use a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, usually provide more flexible scheduling in which computation generally proceed left-to-right but in which some calls are dynamically “delayed” until their arguments are sufficiently instantiated to allow the call to run efficiently. Such dynamic scheduling has a significant cost. We give a framework for the global analysis of logic programming languages with dynamic scheduling and show that program analysis based on this framework supports optimizations which remove much of the overhead of dynamic scheduling.

REFERENCES

• 1: M. Carlsson. Freeze, Indexing, and Other Implementation Issues in the Warn. In Fourth International Conference on Logic Programming, pages 40-58. University of Melbourne, MIT Press, May 1987.
• 2: M. Carlsson. Sicstus Protog User's Manual. Po Box 1263, S-16313 Spanga, Sweden, February 1988.
• 3: M. Codish. A Provably Correct Algorithm for Sharing and Freeness Inference. In 1992 Workshop on Static Analysis WSA'92, September 1992.
• 4: M. Codish, M. Fataschi, and K. Marriott. Suspension Analysis for Concurrent Logic Programs. In K. Furukawa, editor, Proc. Eighth Int'l Conf. on Logic Programming, pages 331- 345. The MIT Press, Cambridge, Mass., 1991.
• 5: Michael Codish , Moreno Falaschi , Kim Marriott , William H. Winsborough, Efficient Analysis of Concurrent Constraint Logic Programs, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.633-644, July 05-09, 1993
• 6: Christian Codognet , Philippe Codognet , Marc-Michel Corsini, Abstract interpretation for concurrent logic languages, Proceedings of the 1990 North American conference on Logic programming, p.215-232, January 1990, Austin, Texas, United States
• 7: 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]
• 8: P. Cousot and R. Cousot. Comparing the Galois Connection and Widening/Narrowing Approaches to Abstract Interpretation. Technical report, LIX, Ecole Polytechnique, France, 1991.
• 9: Patrick Cousot , Rahida Cousot, Abstract interpretation and application to logic programs, Journal of Logic Programming, v.13 n.2-3, p.103-179, July 1992 [doi>10.1016/0743-1066(92)90030-7]
• 10: g. Dehray. ~tatic Analysi~ of Parallel Logic Programs. In Fi~h Int'l Conference and Symposium on Logic Programming, Seattle,Wasinghton, August 1988. MIT Press.
• 11: Saumya K. Debray, Static inference of modes and data dependencies in logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.418-450, July 1989 [doi>10.1145/65979.65983]
• 12: S.K. Debray. QD-Janus: A Sequential Implementation of Janus in Prolog. Technical Report, University of Arizona, 1993.
• 13: 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]
• 14: M. Falaschi, M. Gabbrielh, K. Marriott and C. Palamidessi. Compositional analysis for concurrent constraint programming. IEEE Symposium on Logic in Computer Science, Montreal, June 1993.
• 15: M. Garcia de la Panda and M. Hermenegildo. A Practical Application of Sharing and Freeness Inference. In 1992 Workshop on Static Analysis WSA '92, pages 118- 125, Bourdeaux, France, September 1992.
• 16: D. Gudeman, K. De Bosschere and S.K. Debray. jc: An Efficient and Portable Sequential Implementation of Janus. In Proc. of 1992 Joint International Conference and Symposium on Logic Programming, 399-413. MIT Press, November 1992.
• 17: M. Hanus. On the Completeness of Residuation. In posium on Logic Programming, 192-206. MIT Press, November 1992.
• 18: Michael Hanus, Analysis of nonlinear constraints in CLP( R ), Proceedings of the tenth international conference on logic programming on Logic programming, p.83-99, August 1993, Budapest, Hungary
• 19: M. V. Hermenegildo , K. J. Greene, Prolog and its performance: exploiting independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
• 20: M. V. Hermenegildo , R. Warren , S. K. Debray, Global flow analysis as a practical compilation tool, Journal of Logic Programming, v.13 n.4, p.349-366, Aug. 1992 [doi>10.1016/0743-1066(92)90053-6]
• 21: Timothy Hickey , Shyam Mudambi, Global compilation of prolog, Journal of Logic Programming, v.7 n.3, p.193-230, Nov. 1989 [doi>10.1016/0743-1066(89)90021-6]
• 22: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 23: Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
• 24: Kim Marriott , Harald Søndergaard , Philip Dart, A characterization of non-floundering logic programs, Proceedings of the 1990 North American conference on Logic programming, p.661-680, January 1990, Austin, Texas, United States
• 25: Kim Marriott , Harald Søndergaard , Neil D. Jones, Denotational abstract interpretation of logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.607-648, May 1994 [doi>10.1145/177492.177650]
• 26: C. S. Mellish. The automatic generation of mode declarations for Prolog programs. Technical Report 163, Dept. of Artificial Intelligence, University of Edinburgh, Scotland, 1981.
• 27: K. Muthukumar , M. V. Hermenegildo, The DCG, UDG, and MEL methods for automatic compile-time parallelization of logic programs for independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
• 28: K. Muthukumar and M. Hermenegildo. Combined Determination of Sharing and Freeness of Program Variables Through Abstract Interpretation. In 1991 International Con}erence on Logic Programming, pages 49-63. MIT Press, June 1991.
• 29: K. Muthukumar , M. Hermenegildo, Compile-time derivation of variable dependency using abstract interpretation, Journal of Logic Programming, v.13 n.2-3, p.315-347, July 1992 [doi>10.1016/0743-1066(92)90035-2]
• 30: Lee Naish, Negation and control in Prolog, Springer-Verlag New York, Inc., New York, NY, 1986
• 31: Andrew Taylor, LIPS on MIPS: results from Prolog compiler for a RISC, Logic programming, MIT Press, Cambridge, MA, 1990
• 32: Peter Van Roy , Alvin M. Despain, The benefits of global dataflow analysis for an optimizing Prolog compiler, Proceedings of the 1990 North American conference on Logic programming, p.501-515, January 1990, Austin, Texas, United States
• 33: R. Warren, M. Hermenegildo and S.K. Debray. On the Practicality of Global Flow Analysis of Logic Programs. Proc. of the 5th International Con}erence and Symposium on Logic Programming, 684-699, 1988.
• 34: K. A. Yelick , J. L. Zachary, Moded type systems for logic programming, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.116-124, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75287]

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: Optimization

General Terms:
Measurement, Performance, Theory