Search
1992 Volume 7
Article Contents
RESEARCH ARTICLE   Open Access    

Trends in applying abstract interpretation

More Information
  • 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
  • 加载中
  • Abramsky S and Hankin C, eds., 1987, Abstract Interpretation of Declarative LanguagesEllis Horwood.

    Google Scholar

    Bansal A and Sterling L, 1990, “An abstract interpretation scheme for logic programs based on type expressions,” New Generat. Comput.1273–324.

    Google 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.

    Google 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.

    Google Scholar

    Debray S and Warren DS, 1988, “Automatic mode inference for logic programs,” Journal of Logic Programming5(3) 207–230.

    Google 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.

    Google 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.

    Google 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.

    Google 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, 23296–307.

    Google 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.

    Google Scholar

    van Gelder A, 1987, “Efficient loop detection in Prolog using the tortoise-and-hare techniques,” Journal of Logic Programming423–31.

    Google 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

  • Cite this article

    Andrew Bowles. 1992. Trends in applying abstract interpretation. The Knowledge Engineering Review. 7:6275 doi: 10.1017/S0269888900006275
    Andrew Bowles. 1992. Trends in applying abstract interpretation. The Knowledge Engineering Review. 7:6275 doi: 10.1017/S0269888900006275

Article Metrics

Article views(15) PDF downloads(55)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Trends in applying abstract interpretation

The Knowledge Engineering Review  7 Article number: 10.1017/S0269888900006275  (1992)  |  Cite this article

Abstract: 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

    • Copyright © Cambridge University Press 19921992Cambridge University Press
References (34)
  • About this article
    Cite this article
    Andrew Bowles. 1992. Trends in applying abstract interpretation. The Knowledge Engineering Review. 7:6275 doi: 10.1017/S0269888900006275
    Andrew Bowles. 1992. Trends in applying abstract interpretation. The Knowledge Engineering Review. 7:6275 doi: 10.1017/S0269888900006275
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return