Precise pair-sharing analysis of logic programs

ABSTRACT

The paper presents a novel approach to pair-sharing analysis of logic programs. The pair-sharing domain ASub of Søndergaard is known to be more efficient than the set-sharing domain Sharing of Jacobs and Langen and gains accuracy because of linearity tracking. However, it is less accurate because of weaker groundness information, and the fact that it loses track of where new groundness eliminates sharing. In this paper we present a new domain which inherits the advantages of both ASub and Sharing and is uniformly more accurate in terms of pair-sharing than each of the two domains.The proposed domain expresses pair-sharing in terms of existence of <i>traversable paths</i> in <i>relation graphs</i> derived from program constraints. Each edge of a relation graph has an attached <i>groundness formula</i> which defines under what groundness conditions it still causes sharing. This allows the domain to maintain information about when groundness can eliminate sharing. Relation graphs are augmented by separate groundness information (usually Def or Pos). The groundness analysis and groundness formulae can be represented using efficient ROBDD methods.

REFERENCES

• 1: Krzysztof R. Apt, Logic programming, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 2: T. Armstrong, K. Marriott, P. Schachte, and H. Søndergaard. Boolean functions for dependency analysis: Algebraic properties and efficient representation. In 1st International Symposium on Static Analysis, volume 864 of LNCS, pages 266--280. Springer-Verlag, 1994.
• 3: Roberto Bagnara , Patricia M. Hill , Enea Zaffanella, Set-Sharing is Redundant for Pair-Sharing, Proceedings of the 4th International Symposium on Static Analysis, p.53-67, September 08-10, 1997
• 4: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 5: 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]
• 6: M. García de la Banda, K. Marriott, P.J. Stuckey, and H. Søndergaard. Differential methods in logic program analysis. Journal of Logic Programming, 35(1):1--37, 1998.
• 7: M. Hermenegildo, F. Bueno, D. Cabeza, M. Carro, M. García de la Banda, and G. Puebla P. López-García. The CIAO multi-dialect compiler and system: An experimentation workbench for future (C)LP systems. In Parallelism and Implementation of Logic and Constraint Logic Programming, pages 65--85. Nova Science, 1999.
• 8: M. V. Hermenegildo , K. J. Greene, Prolog and its performance: exploiting independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
• 9: Dean Jacobs , Anno Langen, Static analysis of logic programs for independent and parallelism, Journal of Logic Programming, v.13 n.2-3, p.291-314, July 1992 [doi>10.1016/0743-1066(92)90034-Z]
• 10: V. Lagoon and P.J. Stuckey. Precise pair-sharing analysis of logic programs. Technical report, Department of Computer Science and Software Engineering, University of Melbourne, 2002. http://www.cs.mu.oz.au/~pjs/papers.html+.
• 11: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 12: Kim Marriott , Harald Søndergaard, Precise and efficient groundness analysis for logic programs, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.181-196, March–Dec. 1993 [doi>10.1145/176454.176519]
• 13: 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]
• 14: D. A. Plaisted. The occur-chack problem in Prolog. In Int. Symp. on Logic Programming, pages 272--280. IEEE Computer Society Press, 1984.
• 15: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages

Keywords:
program analysis, sharing