S. K. Debray
ABSTRACT
We investigate a framework for efficient flow analyses of logic programs. A major problem in this context is that unification can give rise to aliasing and dependencies between variables whose effects are difficult to predict, and which make sound flow analysis algorithms computationally expensive. We give a simple characterization of the class of flow analysis problems for which aliasing effects can be ignored without loss of soundness, and describe an efficient analysis procedure for this class of problems. The utility of our approach is illustrated by discussing its application to several analysis and optimization problems for logic programs. Our results are useful in the design of efficient flow analysis systems for logic programming languages.
- 1.A.V. Aho, R. Sethi and J. D. Ullman, Compilers- Principles, Techniques and Tools, Addison-Wesley, 1986. Google Scholar
Digital Library
- 2.M. Bruynooghe, Compile time Garbage Collection, in Proc. IFIP Working Conference on Program Transformation and Verification, Elsevier-North Holland, 1986. Google ScholarDigital Library
- 3.M. Bruynooghe, B. Demoen, A. Callebaut and G. Janssens, Abstract Interpretation: Towards the Global Optimization of Prolog Programs, in Proc. 4 th. IEEE Syrup. on Logic Programming, San Fransisco, CA, Sep. 1987.Google Scholar
- 4.P. Cousot and R. Cousot, Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints, Conf. Rec. 4th A CM Syrup. on Prin. of Programming Languages, 1977, pp. 238-252. Google ScholarDigital Library
- 5.S.K. Debray and D. S. Warren, Detection and Optimization of Functional Computations in ProIog, in Proc. Third Int. Conf. on Logic Programming, London, July 1986. Springer-Verlag LNCS vol. 225. Google ScholarDigital Library
- 6.S.K. Debray and D. S. Warren, Automatic Mode Inference for Prolog Programs, in Proc. 1986 Int. Syrup. on Logic Programming, Salt Lake City, Utah, Sept. 1986, pp. 78-88.Google Scholar
- 7.S.K. Debray, The SB-Prolog System, Version B.2: A User Manual, Department of Computer Science, University of Arizona, Tucson, AZ, March t987.Google Scholar
- 8.S.K. Debray, Flow Analysis of a Simple Class of Dynamic Logic Programs, in Proe. 4th. {EEE Syrup. on Logic Programming, San Fransisco, CA, Sep. 1987, pp. 307-316.Google Scholar
- 9.S.K. Debray, Static Inference of Modes and Data Dependencies in Logic Programs, Tech. Rep. 87-24, Dept. of Computer Science, University of Arizona, Tucson, AZ, Aug. 1987.Google Scholar
- 10.S.W. Dietrich, Extension Tables: Memo Relations in Logic Programming, in Proc. 4th. IEEE Syrup. on Logic Programming, San Fransisco, CA, Sep. 1987, pp. 264-272.Google Scholar
- 11.H. Mannila and E. Ukkonen, Flow Analysis of Prolog Programs, in Proc. 4th. {EEE Symp. on Logic Programming, San Fransisco, CA, Sep. 1987.Google Scholar
- 12.C.S. Mellish, The Automatic Generation of Mode Declarations for Prolog Programs, DAI Research Paper 1{}3, Dept. of Artificial Intelligence, University of Edinburgh, Aug. 1981.Google Scholar
- 13.C. S. Mellish, Some Global Optimizations for a Prolog Compiler, 3". Logic Programming P, I (Apr. 1985), 43-66.Google ScholarCross Ref
- 14.E.W. Myers, A Precise Inter-Procedural Data Flow Algorithm, ia Proc. 8th. A CM Symposium on Principles of Programming Languages, 1981, pp. 219-230. Google ScholarDigital Library
- 15.L. Naish, Negation and Control in Prolog, Dept. of Computer Science, Univ. of Melbourne, Parkville, Australia, 1985. Ph.D. Thesis.Google Scholar
- 16.U.S. Reddy, Transformation of Logic Programs into Functional Programs, in Proc. 198~ Int. Syrup. on Logic Programming, IEEE Computer Society, Atlantic City, New Jersey, Feb. 1984, 187-196.Google Scholar
- 17.H. Tamaki and T. Sato, OLD-Resolution with Tabulation, in Proc. 3rd. International Conference on Logic Programming, London, July 1986, 84-98. Springer-Verlag LNCS vol. 225. Google ScholarDigital Library
- 18.P. Van Roy, B. Demoea and Y. D. Willems, Improving the Execution Speed of Compiled Prolog with Modes, Clause Selection and Determinism, in Proe. TAPSOFT 1987, Pisa, Italy, Mar. 1987. Google ScholarDigital Library
- 19.D.H.D. Warren, Implementing Prolog- Compiling Predicate Logic Programs, Research Reports 39 and 40, Dept. of Artificial Intelligence, University of Edinburgh, 1977.Google Scholar
Index Terms
- Efficient dataflow analysis of logic programs
Recommendations
Efficient dataflow analysis of logic programs
A framework for efficient dataflow analyses of logic programs is investigated. A number of problems arise in this context: aliasing effects can make analysis computationally expensive for sequential logic programming languages; synchronization issues ...
Logic-flow analysis of higher-order programs
POPL '07: Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThis work presents a framework for fusing flow analysis and theorem proving called logic-flow analysis (LFA). The framework itself is the reduced product of two abstract interpretations: (1) an abstract state machine and (2) a set of propositions in a ...
Comments