Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-01-08T13:41:45.094Z Has data issue: false hasContentIssue false
  • English
  • Français

Abstract interpretation by dynamic partitioning

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

François Bourdoncle
François Bourdoncle
Affiliation:
DIGITAL Paris Research Laboratory, 85, avenue Victor Hugo, 92500 Rueil-Malmaison, France Centre de Mathématiques Appliquées, Ecole des Mines de Paris, Sophia-Antipolis, 06560 Valbonne, France(e-mail: bourdoncle@prl.dec.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The essential part of abstract interpretation is to build a machine-representable abstract domain expressing interesting properties about the possible states reached by a program at runtime. Many techniques have been developed which assume that one knows in advance the class of properties that are of interest. There are cases however when there are no a priori indications about the 'best' abstract properties to use. We introduce a new framework that enables non-unique representations of abstract program properties to be used, and expose a method, called dynamic partitioning, that allows the dynamic determination of interesting abstract domains using data structures built over simpler domains. Finally, we show how dynamic partitioning can be used to compute non-trivial approximations of functions over infinite domains and give an application to the computation of minimal function graphs.

Type
Articles
Information
Journal of Functional Programming , Volume 2 , Issue 4 , October 1992 , pp. 407 - 435
Copyright
Copyright © Cambridge University Press 1992

References

Bourdoncle, F. 1990. Interprocedural abstract interpretation of block structured languages with nested procedures, aliasing and recursivity. In: Proc. International Workshop PLILP'90. Vol. 456 of Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Cousot, P. and Cousot, R. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximations of fixpoints. In: Proc. 4th ACM Symp. on POPL, 238–252.Google Scholar
Cousot, P. and Halbwachs, N. 1978. Automatic discovery of linear constraints among variables of a program. In: Proc. 5th ACM Symp. on POPL, 84–97.Google Scholar
Cousot, P. 1978. Méthodes itératives de construction et d'approximation de points fixes d'opérateurs monotones sur un treillis. Analyse sémantique de programmes. PhD Thesis, Université Scientifique et Médicale de Grenoble.Google Scholar
Cousot, P. and Cousot, R. 1978. Static determination of dynamic properties of recursive procedures. In: Formal Description of Programming Concepts. North-Holland, 237–277.Google Scholar
Cousot, P. 1981. Semantic foundations of program analysis. In: Muchnick, and Jones, (eds), Program Flow Analysis, Theory and Applications. Prentice-Hall, 303–343.Google Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M., Scott, D. S. 1980. A Compendium of Continuous Lattices. Springer-Verlag.CrossRefGoogle Scholar
Gunter, C. A. and Scott, D. S. 1990. Semantic domains. In: Handbook of Theoretical Computer Science (Chapter 12). Elsevier, 635–673.Google Scholar
Jones, N. D. and Muchnick, S. 1982. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In: Proc. 9th ACM Symp. on POPL.Google Scholar
Jones, N. D. and Mycroft, A. 1986. Data flow analysis of applicative programs using minimal function graphs. In: Proc. 13th ACM Symp. on POPL, 296–306.Google Scholar
Mycroft, A. and Nielson, F. 1983. Strong abstract interpretation using power domains (extended abstract). In: Proc. 10th ICALP. Vol. 154 of Lectures Notes in Computer Science. Springer-Verlag, 536–547.Google Scholar
Stransky, J. 1990. A lattice for abstract interpretation of dynamic (lisp-like) structures. L.I.X. internal report LIX/RR/90/03.Google Scholar
Sharir, M. and Pnueli, A. 1981. Two approaches to interprocedural data flow analysis. In: Muchnick, and Jones, (eds), Program Flow Analysis, Theory and Applications. Prentice-Hall, 189–233.Google Scholar
Schmidt, D. A. 1953. Denotational Semantics. Allyn and Bacon, Inc.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.