Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T20:19:11.463Z Has data issue: false hasContentIssue false
  • English
  • Français

Trends in applying abstract interpretation

Published online by Cambridge University Press:  07 July 2009

Andrew Bowles
Andrew Bowles
Affiliation:
Department of Artificial Intelligence, University of Edinburgh, Edinburgh, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

Abstract interpretation is a principled approach to inferring properties of a program's execution by simulating that execution using an interpreter which computes over some abstraction of the program's usual, concrete domain, and which collects the information of interest during the execution. Abstract interpretation has been used as the basis of research in logic and functional programming, particularly in applications concerned with compiler optimizations. However, abstract interpretation has the potential to be used in other applications, such as debugging or verification of programs. In this paper we review the use of abstract interpretation to both compiler optimizations and to other applications, attempting to give a flavour of the kind of information it is possible to infer and some of the issues involved

Type
Research Article
Information
The Knowledge Engineering Review , Volume 7 , Issue 2 , June 1992 , pp. 157 - 171
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S and Hankin, C, eds., 1987, Abstract Interpretation of Declarative Languages Ellis Horwood.Google Scholar
Bansal, A and Sterling, L, 1990, “An abstract interpretation scheme for logic programs based on type expressions,” New Generat. Comput. 1 273–324.CrossRefGoogle Scholar
Bowles, A, 1991, Detecting Prolog Programming Techniques Using Abstract Interpretation PhD thesis, University of Edinburgh.Google Scholar
Brna, P, Bundy, A, Dodd, T, Eisenstadt, M, Looi, CK, Pain, H, Robertson, D, Smith, B and van Someren, M, 1990, “Prolog programming techniques,” Instructional Sci. 19 (4/5).Google Scholar
Bruynooghe, M, 1988, “A practical framework for the abstract interpretation of logic programs. (To appear in Journal of Logic Programming)Google Scholar
Bruynooghe, M and Janssens, G, 1988, “An instance of abstract interpretation integrating type and mode inferencing,” In: Fifth Symposium and Conference on Logic Programming pp 669–683, Seattle, WA.Google Scholar
Bruynooghe, M, Janssens, G, Callebaut, A and Demoen, B, 1987, “Abstract interpretation: towards the global optimization of Prolog programs,” In: Logic Programming Symposium, pp 192–204, San Francisco, CA.Google Scholar
Codish, M, Gallagher, J and Shapiro, E, 1988, “Using safe approximations of fixed points for analysis of logic programs,” In: Abramson, H and Rogers, M, editors, Proceedings of the First Workshop on Meta-Programming in Logic-Programming, pp 233–261, Bristol, England.Google Scholar
Cousot, P and Cousot, R, 1977, “Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints,” In: Proceedings of the Fourth Annual ACM Symposium on Principles of Programming Languages, pp 238–252.CrossRefGoogle Scholar
Cousot, P and Cousot, R, 1979, “Systematic design of program analysis frameworks,” In: Proceedings of the Sixth Annual ACM Symposium on Principles of Programming Languages, pp 269–282.CrossRefGoogle Scholar
Debray, S and Warren, DS, 1988, “Automatic mode inference for logic programs,” Journal of Logic Programming 5(3) 207–230.CrossRefGoogle Scholar
Dietrich, SW, 1987, “Extension tables: memo relations in logic programming,” In: Logic Programming Symposium, pp 264–272, San Francisco, CA.Google Scholar
Gallagher, J and Bruynooghe, M, 1990a, “The derivation of an algorithm for program specialization,” In: DHD Warren and P Szeredi, editors, Proceedings of the Seventh International Conference on Logic Programming, pp 732–746, Jerusalem, Israel.Google Scholar
Gallagher, J and Bruynooghe, M, 1990, “Some low-level source transformations for logic programs,” In: Bruynooghe, M, editor, Proceedings of the Second Workshop on Meta-Programming in Logic, pp 229–244, Leuven, Belgium.Google Scholar
Gallagher, J, Codish, M and Shapiro, E, 1988, “Specialization of Prolog and FCP programs using abstract interpretations,” New Generat Computing, 6(2/3) 159–186.CrossRefGoogle Scholar
Harper, R, MacQueen, D and Milner, R, 1986, “Standard ML, Technical Report ECS-LFCS-86–2, Department of Computer Science, University of Edinburgh.Google Scholar
Hudak, P, 1986, “A semantic model of reference counting and its abstraction,” In: ACM Conference on Lisp and Functional Programming, pp 351–363, Cambridge, MA.CrossRefGoogle Scholar
Jacobs, D and Langen, A, 1989, “Accurate and efficient approximation of variable aliasing in logic programs,” In: E Lusk and R Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pp 154–165, Cleveland, OH.Google Scholar
Jones, ND and Søndergaard, , 1987, “A semantics-based framework for the abstract interpretation of Prolog,” In: Abramsky, S and Hankin, C, editors, Abstract Interpretation of Declarative Languages, pp 123–142, Ellis Horwood.Google Scholar
Kanamori, T, Kawamura, T and Maeji, M, 1989, “Logic program analysis by abstract hybrid interpretation, TR 485, ICOT.Google Scholar
Looi, CK, 1988, “Automatic Program Analysis in a Prolog Intelligent Technical System PhD thesis, University of Edinburgh.Google Scholar
Mellish, C, 1985, “Some global optimizations for a Prolog compiler,” Journal of Logic Programming, 2(1) 43–66.CrossRefGoogle Scholar
Mellish, C, 1987, “Abstract interpretation of Prolog programs,” In: Abramsky, S and Hankin, C, editors, Abstract Interpretation of Declarative Languages, pp 181–198, Ellis Horwood.Google Scholar
Mishra, P, 1984, “Towards a theory of types in Prolog,” In: Logic Programming Symposium, pp 289–298, Atlantic City, NJ.Google Scholar
Mulkers, A, Winsborough, W and Bruynooghe, M, 1990, “Analysis of shared structures for compile-time garbage collection in logic programs,” In: DHD Warren and P Szeredi, editors, Proceedings of the Seventh International Conference on Logic Programming pp 747–762, Jerusalem, Israel.Google Scholar
Muthukumar, K and Hermenegildo, M, 1989, “Determination of variable dependence information through abstract interpretation,” In: E Lusk and R Overbeek, editors, Proceedings of the North American Conference on Logic Programming pp 166–185, Cleveland, OH.Google Scholar
Mycroft, A, 1981, Abstract Interpretation and Optimizing Transformations PhD thesis, University of Edinburgh.Google Scholar
Mycroft, A and O'Keefe, R, 1984, “A polymorphic type system for Prolog,” Artificial Intelligence, 23 296–307.CrossRefGoogle Scholar
Søndergaard, , 1986, “An application of abstract interpretation of logic programs: Occur check reduction,” In: Robinet, B and Wilhelm, R, editors, ESOP 86 European Symposium on Programming, pp 327–338, Saarbrucken, Germany.Google Scholar
Tamaki, H and Sato, T, 1986, “Old resolution with tabulation,” In: Shapiro, E, editor, Proceedings of the Third International Conference on Logic Programming pp 84–98, London, England.CrossRefGoogle Scholar
van Gelder, A, 1987, “Efficient loop detection in Prolog using the tortoise-and-hare techniques,” Journal of Logic Programming 4 23–31.CrossRefGoogle Scholar
Verschaetse, K and de Schreye, D, 1991, “Deriving termination proofs for logic programs, using abstract procedures,” In: K Furukawa, editor, Proceedings of the Eighth International Conference on Logic Programming, pp 301–315, Paris, France.Google Scholar
Wang, B and Shyamasundar, R, 1990, “Towards a characterization of termination in logic programs,” In: Proceedings of the International workshop PLILP'90, Volume 456 of Lecture Notes in Computer Science, Springer-Verlag, 204–221.Google Scholar
Zobel, J, 1987, “Derivation of polymorphic types for Prolog programs,” In: J-L Lassez, editor, Proceedings of the Fourth International Conference on Logic Programming pp 817–838, Melbourne, Australia.Google Scholar