On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications

ABSTRACT

We present a static analysis method for determining aliasing and lifetime of dynamically allocated data in lexically scoped, higher-order, strict and polymorphic languages with first class continuations. The goal is validate program transformations that introduce imperative constructs such as destructive updatings, stack allocations and explicit deallocations in order to reduce the run-time memory management overhead. Our method is based on an operational model of higher order functional programs from which we construct statically computable abstractions using the abstract interpretation framework. Our method provides a solution to a problem left open [Hudak 86]: determining isolation of data in the case of higher order languages with structured data.

REFERENCES

• Aasa, Holmstrom & Nilsson 88: A. Aasa , Sören Holmström , Christina Nilsson, An efficiency comparison of some representations of purely functional arrays, BIT, v.28 n.3, p.490-503, 1988
• Appel 87: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• Appel 89: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• Barth 77: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• Bloss 89: Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
• Cardelli 84: Luca Cardelli, Compiling a functional language, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.208-217, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802037]
• Chase 88: D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
• Cousot & Cousot 77a: 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]
• Cousot & Cousot 77b: Patrick Causot , Radhia Cousot, Static determination of dynamic properties of generalized type unions, ACM SIGPLAN Notices, v.12 n.3, p.77-94, March 1977
• Cousot & Cousot 79: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• Cousot 78: P. Cousot. Methodes iteratives de construction et d'approximation de points fixes d'operateurs monotones sur un treillis, analyse acmantique de programmes. These d'etat, Mar. 1978. Universite scientifique et medicale de Grenoble.
• Cousot 81: P. Cousot. Program Flow Analysis: Theory and Applications, chapter Semantic foundations of program analysis, pages 303--342. Prentice-Hall, 1981.
• Coutant 86: Deborah S. Coutant, Retargetable high-level alias analysis, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-118, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512654]
• Deutsch 89: A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications (extended version). Research Report LiX/RR/89/(to appear), Ecole Polytechnique, 91128 Palaiseau, France, 1989.
• Fairbairn & Wray 86: Jon Fairbairn , Stuart C. Wray, Code generation techniques for functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.94-104, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319853]
• Goldberg 87: Benjamin Goldberg, Detecting sharing of partial applications in functional languages, Proc. of a conference on Functional programming languages and computer architecture, p.408-425, October 1987, Portland, Oregon, United States
• Haynes & Friedman 87: Christopher T. Haynes , Daniel P. Friedman, Embedding continuations in procedural objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.582-598, Oct. 1987 [doi>10.1145/29873.30392]
• Hecht 77: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• Horwitz, Pfeiffer & Reps 89: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
• Hudak 86: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• Hughes 87: J. Hughes. Backward analysis of functional programs. In D. Bjorner, A.P. Ershov, and N.D Jones, editors, Proc. Workshop on Partial Evaluation and Mixed Computation, pages 155-169, North-Holland, Denmark, Oct. 1987.
• Inoue, Seki & Yagi 88: Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
• Jones & Le Metayer 89: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• Jones & Muchnick 81: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• Jones & Muchnick 82: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• Jones 81: N.D. Jones. Flow analysis of lambda expressions. In Symposium on Funtional Languages and Computer Architecture, pages 376-401, Chalmers University of Technology, Goteborg, Sweden, Jun. 1981.
• Jouvelot & Gifford 89: P. Jouvelot , D. K. Gifford, Reasoning about continuations with control effects, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.218-226, June 19-23, 1989, Portland, Oregon, United States
• Kastens & Schmidt 86: U Kastens , M Schmidt, Lifetime analysis for procedure parameters, Proc. of the European symposium on programming on ESOP 86, p.53-69, March 1986, Saarbru:9Aicken, Germany
• Kennedy 76: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• Landin 64: J. Landin. The Mechanical Evaluation of Expressions. Volume 6, Computer Journal, Jan. 1964.
• Larus & Hilfinger 88: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• Launchbury 87: J. Launchbury. Projections for specialisation. In D. Bjorner, A.P. Ershov, and N.D. Jones, editors, Workshop on Partial Evaluation and Mixed Computation, pages 299-315, North Holland, Oct. I987.
• Mogensen 87: T.AE. Mogensen. Partially static structures in a self-applicable partial evaluator. In D. Bjorner, A.P. Ershov, and N.D. Jones, editors, Workshop on Partial Evaluation and Mixed Computation, pages 325-347, North Holland, Oct. 1987.
• Mogensen 89: Torben Æ. Mogensen, Binding Time Analysis for Polymorphically Typed Higher Order Languages, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, p.298-312, March 13-17, 1989
• Neirynck, Panangaden & Demers 87: A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41650]
• Nielson & Nielson 86: Hanne R. Nielson , Flemming Neilson, Semantics directed compiling for functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.249-257, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319867]
• Nielson & Nielson 88: Flemming Nielson , Hanne Riis Nielson, Two-level semantics and code generation, Theoretical Computer Science, v.56 n.1, p.59-133, Jan. 1988 [doi>10.1016/0304-3975(86)90006-X]
• Nielson 85: Nielson. Flemming, Expected forms of data flow analyses, on Programs as data objects, p.172-191, April 1986, Copenhagen, Denmark
• Raoult & Sethi 84: Jean-Claude Raoult , Ravi Sethi, The global storage needs of a subcomputation, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.148-157, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800526]
• Raoult & Sethi 85: J.C. Raoult and R. Sethi. On Finding Stacked Attributes. Technical Report 206, LRI, Universite Paris-Sud, 91405 Orsay, France, Feb. 1985.
• Rees & Clinger 86: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• Ruggieri & Murtagh 88: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• Schmidt 85: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• Schwartz 78: J. Schwartz. Verifying the safe use of destructive operations in applicative programs. In B. Robinet, editor, Transformations de programmes : 3e colloque international, sur la programmation, pages 394-410, Dunod, Paris, mar. 1978.
• Sestoft 89: Peter Sestoft, Replacing function parameters by global variables, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.39-53, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99374]
• Sharir & Pnueli 81: M. Sharir and A. Pnueli. Program Flow Analysis: Theory and Applications, chapter Two approaches to inter procedural data flow analysis, pages 189-234. Prentice-Hall, 1981.
• Shivers 88: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• Stransky 88: I. Stransky. Analyse semantique de structures de donnces dynamiques aves application au cas particulier de langages LISPiens. PhD thesis, Universite de Paris-Sud, Orsay, France, Jun. 1988.
• Wadler 88: Philip Wadler, Deforestation: transforming programs to eliminate trees, Proceedings of the Second European Symposium on Programming, p.231-248, January 1988, Nancy, France
• Weihl 80: 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:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Algorithms, Languages, Verification