Path dependent analysis of logic programs
Author: 
Lunjin LuAuthors Info & Claims
Abstract
This paper presents an abstract semantics that uses information about execution paths to improve precision of data flow analyses of logic programs. We illustrate the abstract semantics by abstracting execution paths using call strings of fixed length and the last transfer of control. Abstract domains that have been developed for logic program analyses can be used with the new abstract semantics without modification.
References
[1]
R. Barbuti and R. Giacobazzi. A bottom-up polymorphic type inference in logic programming. Science of computer programming, 19(3):133-181, 1992.
[2]
R. Barbuti, R. Giacobazzi, and G. Levi. A general framework for semantics-based bottom-up abstract interpretation of logic programs. ACM Transactions on Programming Languages and Systems, 15(1):133-181, 1993.
[3]
M. Bruynooghe. A practical framework for the abstract interpretation of logic progams. Journal of Logic Programming, 10(2):91-124, 1991.
[4]
B. Le Charlier and P. Van Hentenryck. Experimental evaluation of a generic abstract interpretation algorithm for prolog. The ACM Transaction on Programming Languages and Systems, 16(1):35-101, 1994.
[5]
M. Codish, D. Dams, and E. Yardani. Bottom-up abstract interpretation of logic programs. Journal of Theoretical Computer Science, 124:93-125, 1994.
[6]
M. Codish and V. Lagoon. Type dependencies for logic programs using ACI-unification. Journal of Theoretical Computer Science, 238:131-159, 2000.
[7]
A. Cortesi, G. File, and W. Winsborough. Optimal groundness analysis using propositional logic. Journal of Logic Programming, 27(2):137-168, 1996.
[8]
P. Cousot and R. Cousot. Abstract interpretation: a unified framework for static analysis of programs by construction or approximation of fixpoints. In Proc. POPL'77, pages 238-252. The ACM Press, 1977.
[9]
P. Cousot and R. Cousot. Abstract interpretation and application to logic programs. Journal of Logic Programming, 13(1, 2, 3 and 4):103-179, 1992.
[10]
S.K. Debray. Functional computations in logic programs. ACM Transactions on Programming Languages and Systems, 11(3):451-481, 1989.
[11]
S.K. Debray. Static inference of modes and data dependencies in logic programs. ACM Transactions on Programming Languages and Systems, 11(3):418-450, 1989.
[12]
S.K. Debray and D. S. Warren. Automatic mode inference for logic programs. Journal of Logic Programming, 5(3):207-230, 1988.
[13]
P. Deransart, B. Lorho, and J. Ma luszynski, editors. Proceedings of the First International Workshop on Programming Language Implementation and Logic Programming, Lecture Notes in Computer Science 348. Springer, 1988.
[14]
K. Furukawa, editor. Proceedings of the Eighth International Conference on Logic Programming. The MIT Press, 1991.
[15]
M. Hermenegildo, R. Warren, and S.K. Debray. Global ow analysis as a practical compilation tool. Journal of Logic Programming, 13(4):349-366, 1992.
[16]
D. Jacobs and A. Langen. Static analysis of logic programs for independent and parallelism. Journal of Logic Programming, 13(1-4):291-314, 1992.
[17]
G. Janssens and M. Bruynooghe. Deriving descriptions of possible values of program variables by means of abstract interpretation. Journal of Logic Programming, 13(1-4):205-258, 1992.
[18]
T. Kanamori. Abstract interpretation based on Alexander Templates. Journal of Logic Programming, 15(1 & 2):31-54, 1993.
[19]
T. Kanamori and K. Horiuchi. Type inference in Prolog and its application. In A.K. Joshi, editor, Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pages 704-707. Morgan Kaufmann, 1985.
[20]
T. Kanamori and T. Kawamura. Abstract interpretation based on OLDT resolution. Journal of Logic Programming, 15(1 & 2):1-30, 1993.
[21]
R. A. Kowalski and K. A. Bowen, editors. Proceedings of the Fifth International Conference and Symposium on Logic Programming. The MIT Press, 1988.
[22]
G. Levi and F. Spoto. An Experiment in Domain Refinement: Type Domains and Type Representations for Logic Programs. In C. Palamidessi, H. Glaser, and K. Meinke, editors, Principles of Declarative Programming, Lecture Notes in Computer Science 1490, pages 152-169. Springer-Verlag, 1998.
[23]
T. Lindgren. Control ow analysis of Prolog. In J.W. Lloyd, editor, Logic Programming, Proceedings of the 1995 International Symposium, pages 432-446. The MIT Press, 1995.
[24]
J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.
[25]
L. Lu. Abstract interpretation, bug detection and bug diagnosis in normal logic programs. PhD thesis, University of Birmingham, 1994.
[26]
L. Lu. A polymorphic type analysis in logic programs by abstract interpretation. Journal of Logic Programming, 36(1):1-54, 1998.
[27]
L. Lu. A precise type analysis of logic programs. In M. Gabbrielli and F. Pfenning, editors, Proceedings of the Second International ACM SIGPLAN Conference on Principles and Practices of Declarative Programming, pages 214-225. The ACM Press, 2000.
[28]
K. Marriott and H. S~ndergaard. Bottom-up abstract interpretation of logic programs. In Kowalski and Bowen {21}, pages 733-748.
[29]
K. Marriott and H. S~ndergaard. Bottom-up data ow analysis of normal logic programs. Journal of Logic Programming, 13(1-4):181-204, 1992.
[30]
K. Marriott, H. S~ndergaard, and N. D. Jones. Denotational abstract interpretation of logic programs. ACM Transactions on Programming Languages and Systems, 16(3):607-648, 1994.
[31]
C. Mellish. Abstract interpretation of Prolog programs. In S. Abramsky and C. Hankin, editors, Abstract interpretation of declarative languages, pages 181-198. Ellis Horwood Limited, 1987.
[32]
K. Muthukumar and M. Hermenegildo. Compile-time derivation of variable dependency using abstract interpretation. Journal of Logic Programming, 13(1-4):315-347, 1992.
[33]
F. Nielson and H. Riis Nielson. Infinitary control ow analysis: a collecting semantics for closure analysis. In Proc. POPL'97, pages 332-345. ACM Press, 1997.
[34]
U. Nilsson. Towards a framework for the abstract interpretation of logic programs. In Deransart et al. {13}, pages 68-82.
[35]
D. De Schreye and M. Bruynooghe. An application of abstract interpretation in source level program transformation. In Deransart et al. {13}, pages 35-57.
[36]
M. Sharir and A. Pnueli. Two approaches to interprocedural data ow analysis. In S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis, pages 189-233. Prentice Hall International, 1981.
[37]
H. S~ndergaard. An application of abstract interpretation of logic programs: occur check problem. In B. Robinet and R. Wilhelm, editors, ESOP 86, European Symposium on Programming, Lecture Notes in Computer Science 213, pages 324-338. Springer, 1986.
[38]
H. Tamaki and T. Sato. OLD resolution with tabulation. In Proceedings of the Third International Conference on Logic Programming, pages 84-98, London, U.K., 1986.
[39]
A. Taylor. Removal of dereferencing and trailing in Prolog compilation. In G. Levi and M. Martelli, editors, Proceedings of the Sixth International Conference on Logic Programming, pages 48-60. The MIT Press, 1989.
[40]
M.H. van Emden and R.A. Kowalski. The semantics of predicate logic as a programming language. Artificial Intelligence, 23(10):733-742, 1976.
[41]
K. Verschaetse and D. De Schreye. Deriving termination proofs for logic programs, using abstract procedures. In Furukawa {14}, pages 301-315.
[42]
A. Waern. An implementation technique for the abstract interpretation of Prolog. In Kowalski and Bowen {21}, pages 700-710.
[43]
W. Winsborough. Path-Dependent Reachability Analysis for Multiple Specialization. In E. L. Lusk and R. A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 133-153, Cleveland, Ohio, USA, 1989.
- Path dependent analysis of logic programs
Recommendations
Path Dependent Analysis of Logic Programs
This paper presents an abstract semantics that uses information about execution paths to improve precision of data flow analyses of logic programs. The abstract semantics is illustrated by abstracting execution paths using call strings of fixed length ...
Path dependent analysis of logic programs
PEPM '02: Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulationThis paper presents an abstract semantics that uses information about execution paths to improve precision of data flow analyses of logic programs. We illustrate the abstract semantics by abstracting execution paths using call strings of fixed length ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2002 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 January 2002
Published in SIGPLAN Volume 37, Issue 3
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 109Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in