Live-structure dataflow analysis for Prolog

ABSTRACT

For the class of applicative programming languages, efficient methods for reclaiming the memory occupied by released data structures constitute an important aspect of current implementations. The present article addresses the problem of memory reuse for logic programs through program analysis rather than by run-time garbage collection. The aim is to derive run-time properties that can be used at compile time to specialize the target code for a program according to a given set of queries and to automatically introduce destructive assignments in a safe and transparent way so that fewer garbage cells are created. The dataflow analysis is constructed as an application of abstract interpretation for logic programs. An abstract domain for describing structure-sharing and liveness properties is developed as are primitive operations that guarantee a sound and terminating global analysis. We explain our motivation for the design of the abstract domain, make explicit the underlying implementation assumptions, and discuss the precision of the results obtained by a prototype analyzer.

REFERENCES

• 1: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 2: ~BIM 1990. ProLog by BIM--3.0.--Reference Manual. B-3078, BIM, Everberg, Belgium.
• 3: ~BOIZUMAULT, P. 1988. PROLOG L'Implantation Masson, Paris. In French.
• 4: Maurice Bruynooghe, A practical framework for the abstract interpretation of logic programs, Journal of Logic Programming, v.10 n.2, p.91-124, Feb. 1991 [doi>10.1016/0743-1066(91)80001-T]
• 5: ~BRUYNOOGHE, M., AND JANSSENS, G. 1988. An instance of abstract interpretation integrating ~type and mode inferencing. In Proceedings of the 5th international Conference and Symposium ~on Logic Programming. MIT Press, Cambridge, Mass, 669-683.
• 6: ~BRUYNOOGHE, M., AND WINSBOROUGH, W. 1992. Type graph unification. Rep. CW160, Dept. of ~Computer Science, Katholieke Universiteit Leuven, Belgium.
• 7: ~BRUYNOOGHE, M., JANSSENS, G., CALLEBAUT, A., AND DEMOEN, B. 1987. Abstract interpretation: ~Towards the global optimization of Prolog programs. In Proceedings of the 4th Symposium on ~Logzc Programming. IEEE Computer Society Press, Los Alamitos, Calif, 192-204.
• 8: ~BURTON, B., GUDJONSSON, G., AND WINSBOROUGH, W. 1992. An algorithm for computing alter- ~nating closure. Tech. Rep. CS-92-15, Dept. of Computer Science, The Pennsylvania State Univ, ~University Park, Pa.
• 9: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
• 10: ~CODISH, M., DAMS, D., AND YARDENI, E. 1991. Derivation and safety of an abstract unification~ ~algorithm for groundness and aliasing analysis. In Proceedings of the 8th International ~Conference on Logic Programmzng. MIT Press, Cambridge, Mass., 79-93.
• 11: ~CODISH, M., DAMS, D., AND YARDENI, E. 1990. Abstract unification and a bottom-up analysis to ~detect aliasing in logic programs. Tech. Rep. CS90-10, Dept. of Computer Science. Weizmann ~Institute of Science, Israel.
• 12: ~COLMERAUER, A. 1982. Prolog and infinite trees. In Logw Programming. Academic Press, New ~York, 231- 251.
• 13: ~CORTESI, A., AND FIL}~, G. 1991 Abstract interpretation of Prolog. The treatment of the ~built-ins. Rapporto Interno 11, Dept. of Mathematics, Univ. of Padoua.
• 14: ~CORTESI, n., FIL}~, G., AND WINSBOROUGH, W. 1991. Prop revisited: Propositional formula as ~abstract domain for groundness analysis. In Proceedtngs of the 6th Annual IEEE Symposium ~on Logic in Computer Science. IEEE Computer Society Press, Los Alamltos, Calif., 322-327.
• 15: ~Couso% P. 1981. Semantic foundations of program analysis. In Program Flow Analysis: ~Theory and Applications. Prentice-Hall, Englewood Cliffs, N.J., 303-342
• 16: Patrick Cousot , Radhia Cousot, Comparing the Galois Connection and Widening/Narrowing Approaches to Abstract Interpretation, Proceedings of the 4th International Symposium on Programming Language Implementation and Logic Programming, p.269-295, August 26-28, 1992
• 17: 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]
• 18: Saumya K. Debray, Efficient dataflow analysis of logic programs, Journal of the ACM (JACM), v.39 n.4, p.949-984, Oct. 1992 [doi>10.1145/146585.146624]
• 19: ~DEBRAY, S. K., AND WARREN, D.S. 1986a. Automatic mode inference for Prolog programs. In ~Proceedtngs of the 3rd Symposium on Logic Programming. IEEE Computer Society Press. Los ~Alamitos, Calif., 78-88.
• 20: Saumya K Debray , David S Warren, Detection and optimization of functional computations in Prolog, Proceedings on Third international conference on logic programming, p.490-504, September 1986, London, United Kingdom
• 21: ~FOSTER, I. 1989. Copy avoidance through local reuse. Tech. Rep. Preprint MCS-P99-0989, ~Mathematics and Computer Science D~v., Argonne National Lab
• 22: ~FOSTER, I., AND WINSBOROUGH, W. 1991. Copy avoidance through compile-time analysis and ~local reuse. In Proceedings of the International Logic Programming Symposium MIT Press~ ~Cambridge, Mass., 455-469.
• 23: GECSEC, F., AND STEINDY, M. 1984. Tree Automata. Akad(Smiai Kiad5.
• 24: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
• 25: ~HUDAK, P. 1987. A semantic model for reference counting and its abstraction. In Abstract ~Interpretation of Declarative Languages. Ellis Horwood, Chichester, 45-62.
• 26: Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
• 27: Gérard Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM (JACM), v.27 n.4, p.797-821, Oct. 1980 [doi>10.1145/322217.322230]
• 28: Katsuro Inoue , Koji Torii, Implementation and analysis of compile-time garbage collection, New Generation Computing, v.10 n.1, p.101-119, 1991 [doi>10.1007/BF03037524]
• 29: Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
• 30: ~JACOBS, D., AND LANGEN, A. 1989. Accurate and efficient approximation of variable aliasing in ~logic programs. In Proceedings of the North American Conference on Logic Programming. MIT ~Press, Cambridge, Mass., 154-165.
• 31: ~JANSSENS, G. 1990. Deriving run time properties of logic programs by means of abstract ~interpretation. Ph.D. thesis, Dept. of Computer Science, Katholieke Univ. Leuven, Belgium.
• 32: G. Janssens , M. Bruynooghe, Deriving descriptions of possible values of program variables by means of abstract interpretation, Journal of Logic Programming, v.13 n.2-3, p.205-258, July 1992 [doi>10.1016/0743-1066(92)90032-X]
• 33: ~JANSSENS, G., DEMOEN, B., AND WILLEMS, Y. 1987. Execution mechanism for Prolog. Rep. ~CW53, Dept. of Computer Science, Katholieke Univ. Leuven, Belgium.
• 34: T. P. Jensen , T. Æ Mogensen, A backwards analysis for compile-time garbage collection, Proceedings of the third European symposium on programming on ESOP '90, p.227-239, May 1990, Copenhagen, Denmark
• 35: ~JONES, N. D., AND MUCHNICK, S.S. 1981. Flow analysis and optimization of LISP-like struc- ~tures. In Program Flow Analysis: Theory and Applications. Prentice-Hall, Englewood Cliffs, ~N.J., 102-131.
• 36: ~JONES, N. D., AND SgINDERGAARD, H. 1987. A semantic-based framework for the abstract ~interpretation of Prolog. In Abstract Interpretation of Declarative Languages. Ellis Horwood, ~Chichester, 123-142.
• 37: ~KLUZNIAK, F. 1988. Compile-time garbage collection for ground Prolog. In Proceedings of the ~5th International Conference and Symposium on Logic Programming. MIT Press, Cambridge, ~Mass., 1490-1505.
• 38: ~KLU~NIAK, F. 1987. Type synthesis for ground Prolog. In Proceedings of the 4th International ~Conference on Logic Programming. MIT Press, Cambridge, Mass., 788-816.
• 39: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 40: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 41: ~MARI~:N, A., JANSSENS, G., MULKERS, A., AND BRUYNOOGHE, M. 1989. The impact of abstract ~interpretation: An experiment in code generation. In Proceedings of the 6th International ~Conference on Logtc Programmtng. MIT Press, Cambridge, Mass., 33-47.
• 42: ~MARRIOTT, K., AND SCtNDERGAARD, H. 1989. Semantics-based dataflow analysis of logic pro- ~grams. In Information Processing 89. North-Holland, New York, 601-606.
• 43: ~MELLtSH, C.S. 1987. Abstract interpretation of Prolog programs. In Abstract Interpretation of ~Declarative Languageg. Elli~ I-Iorwood, Chich~t~r, 181-198_
• 44: ~MELLiSH, C.S. 1985. Some global optimizations for a Prolog compiler, j. Logic Program. 2, ~43-66.
• 45: ~MULKERS, A. 1991. Deriving live data structures in logic programs by means of abstract ~interpretation. Ph.D. thesis, Dept. of Computer Science, Katholieke Univ. Leuven, Belgium. To ~appear in Lecture Notes in Computer Scwnce, vol. 675.
• 46: ~MULKERS, A., WlNSBOROUGH, W., AND BRUYNOOGHE, M. 1993. A live-structure data-flow analy- ~sis for Prolog: Theory. Rep. CW167, Dept. of Computer Science, Katholieke Univ. Leuven, ~Belgium.
• 47: ~MULKERS, A., WINSBOROUGH, W., AND BRUYNOOGHE, M. 1992. Static analysis of logic programs ~to detect run-time garbage cells. In Proceedings of the Internatmnal Conference on Computer ~Systems and Software Engineering. IEEE Computer Society Press, Los Alamitos, Calif., ~526-531.
• 48: Anne Mulkers , William Winsborough , Maurice Bruynooghe, Analysis of shared data structures for compile-time garbage collection in logic programs, Logic programming, MIT Press, Cambridge, MA, 1990
• 49: ~MULKERS, A., WINSBOROUGH, W., AND BRUYNOOGHE, M. 1990b. Analysis of shared data struc- ~tures for compile-time garbage collection in logic programs (extended version). Rep. CWll7, ~Dept. of Computer Science, Katholieke Univ. Leuven, Belgium.
• 50: ~MUTHUKUMAR, K., AND HERMENEGILDO, M. 1989. Determination of variable dependence infor- ~mation through abstract interpretation. In Proceedings of the North American Conference on ~Logic Programming. MIT Press, Cambridge, Mass., 166-185.
• 51: Ulf Nilsson, Systematic Semantic Approximations of Logic Programs, Proceedings of the 2nd International Workshop on Programming Language Implementation and Logic Programming, p.293-306, August 20-22, 1990
• 52: Young Gil Park , Benjamin Goldberg, Escape analysis on lists, ACM SIGPLAN Notices, v.27 n.7, p.116-127, July 1992
• 53: ~PLAISTED, D.A. 1984. The occur-check problem m Prolog. J. New Gen. Comput. 2, 4, 309-322.
• 54: 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
• 55: ~TARSKL A. 1955. A lattice-theoretical fixpoint theorem and its applications. Paciftc J. Math. 5, ~285-309.
• 56: ~TAYLOR, A. 1991. High performance Prolog implementation. Ph.D. thesis, Univ. of Sydney, ~Australia.
• 57: Andrew Taylor, LIPS on MIPS: results from Prolog compiler for a RISC, Logic programming, MIT Press, Cambridge, MA, 1990
• 58: ~TAYLOR, A. 1989. Removal of dereferencing and trailing in Prolog compilation. In Proceedzngs ~of the 6th International Conference on Logic Programming. MIT Press, Cambridge, Mass., ~48-60.
• 59: ~VAN CANEGHEM, M. 1986. L'Anatomie de Prolog. InterEditions. In French.
• 60: Peter Lodewijk Van Roy, Can logic programming execute as fast as imperative programming?, University of California at Berkeley, Berkeley, CA, 1991
• 61: 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
• 62: VATAJA, P., AND UKKONEN, E. 1984. Finding temporary terms in Prolog programs. In Proceed- ~~ng~ of the International Conference on Fifth Generation Computer Sy~tern~ Ohm~ha, LTD and ~North-Holland, Tokyo/Amsterdam, 275-282.
• 63: WARREN, D. H. D. 1983. An abstract Prolog instruction set. Tech. Rep., SRI International, ~Artificial Intelligence Center, Menlo Park, Calif.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Languages, Performance, Theory

Keywords:
Prolog, abstract interpretation, compile-time garbage collection, liveness, program analysis