Computation of aliases and support sets

ABSTRACT

We provide a scheme for determining which global variables are involved when an expression is evaluated in a language with higher order constructs and imperative features. The heart of our scheme is a mechanism for computing the support of an expression, i.e. the set of global variables involved in its evaluation. This computation requires knowledge of all the aliases of an expression. The inference schemes are presented as abstract semantic interpretations. We prove the soundness of our estimates by establishing a correspondence between the abstract semantics and the standard semantics of the programming language.

REFERENCES

• 1: Samson Abramsky, Strictness analysis and polymorphic invariance, on Programs as data objects, p.1-23, April 1986, Copenhagen, Denmark
• 2: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 3: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 4: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• 5: Geoffrey L. Burn , Chris Hankin , Samson Abramsky, The theory of strictness analysis for higher order functions, Programs as Data Objects, Proceedings of a Workshop, p.42-62, October 17-19, 1985
• 6: Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
• 7: P. Cousot. Semantic fondations of program analysis. In S.S. Muehnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, Prentice-Hall, 1981.
• 8: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 9: P. Cousot and R. Cousot. Static determination of dynamic properties of programs. In Proceedings of the end International Symposium on Pro#rammin9, 1976.
• 10: David K. Gifford , John M. Lucassen, Integrating functional and imperative programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.28-38, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319848]
• 11: Paul Hudak , Jonathan Young, Higher-order strictness analysis in untyped lambda calculus, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-109, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512653]
• 12: Prateek Mishra, Static inference in applicative languages (semantics, type-checking, optimization), 1985
• 13: Prateek Mishra , Robert M. Keller, Static inference of properties of applicative programs, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.235-244, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800535]
• 14: A. Mycroft. Abstract Interpretetion and Optiraising Transformations for Applicative Programs. PhD thesis, University of Edinburgh, Scotland, 1981.
• 15: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• 16: Alan Mycroft , Neil D. Jones, A relational framework for abstract interpretation, Programs as Data Objects, Proceedings of a Workshop, p.156-171, October 17-19, 1985
• 17: Alan Mycroft , Flemming Nielson, Strong Abstract Interpretation Using Power Domains (Extended Abstract), Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.536-547, July 18-22, 1983
• 18: Anne Neirynck , Prakash Panangaden , Alan J. Demers, Computation of Aliases and Support Sets, Cornell University, Ithaca, NY, 1986
• 19: F. Nielson. Abstract Interpretation Usino Domain Theory. PhD thesis, University of Edinburgh, Scotland, 1984.
• 20: F. Nielson. A denotational framework for data flow analysis. Acts lnforrnatica, 18, 1982.
• 21: Flemming Nielson, Program transformations in a denotational setting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.359-379, July 1985 [doi>10.1145/3916.3917]
• 22: F. Nielson. Towards viewing nondeterminism as abstract interpretation, in FST ~ TCSS, 1983.
• 23: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages, Theory