A unified treatment of flow analysis in higher-order languages

ABSTRACT

We describe a framework for flow analysis in higher-order languages. It is both a synthesis and extension of earlier work in this area, most notably [20, 22]The framework makes explicit use of flow graphs for modeling control and data flow properties of untyped higher-order programs. The framework is parameterized, and can express a hierarchy of analyses with different cost/accuracy tradeoffs. The framework is also amenable to a direct, efficient implementation.We develop several instantiations of the framework, and prove their running-time complexity. In addition, we use the simplest instantiation to demonstrate the equivalence of a 0CFA style analysis and the set-based analysis of [8].

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: François Bourdoncle, Abstract debugging of higher-order imperative languages, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.46-55, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 4: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 5: Patrick Cousot. Semantic Foundations of Program Analysis. In Program Flow Analysis: Theory and Foundation, pages 303-342. Prentice-Hall, 1981.
• 6: 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]
• 7: Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
• 8: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 9: Paul Hudak , Jonathan Young, Collecting interpretations of expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.269-290, April 1991 [doi>10.1145/103135.103139]
• 10: Williams LudwelI Harrison III. The Interprocedural Analysis and Automatic Paralletization of Scheme Programs. Lisp and Symbolic Computation, 2(3/4):179-396, 1989.
• 11: Neil D. Jones , Steven S. Muchnick, Flow analysis and optimization of LISP-like structures, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.244-256, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567776]
• 12: Richard Kelsey and Jonathan Rees. Scheme48 Progress Report. Lisp and Symbolic Computation, 1994.
• 13: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 14: Jens Palsberg , Michael I. Schwartzbach, Safety analysis versus type inference, Information and Computation, v.118 n.1, p.128-141, April 1995 [doi>10.1006/inco.1995.1058]
• 15: Young Gil Park , Benjamin Goldberg, Escape analysis on lists, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.116-127, June 15-19, 1992, San Francisco, California, United States
• 16: Amr Sabry , Matthias Felleisen, Is continuation-passing useful for data flow analysis?, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.1-12, June 20-24, 1994, Orlando, Florida, United States
• 17: Zhong Shao , Andrew W. Appel, Space-efficient closure representations, Proceedings of the 1994 ACM conference on LISP and functional programming, p.150-161, June 27-29, 1994, Orlando, Florida, United States
• 18: Micha Sharir and Amir Pneuli. Two Approaches to Interprocedural DataJ#ow Analysis, pages 189-235. Prentice-Hall, 1981.
• 19: Olin Shivers. Data-flow Analysis and Type Recovery in Scheme. In Topics in Advanced Language Implementation. MIT Press, 1990.
• 20: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 21: Olin Shivers, The semantics of Scheme control-flow analysis, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-198, June 17-19, 1991, New Haven, Connecticut, United States
• 22: Dan Stefanescu , Yuli Zhou, An equational framework for the flow analysis of higher order functional programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.318-327, June 27-29, 1994, Orlando, Florida, United States
• 23: Yuli Zhou, June 1994. Personal Communication.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Languages, Theory, Verification