Polyvariant binding-time analysis for applicative languages

ABSTRACT

Binding-time analysis is a crucial component of an offline partial evaluator. The accuracy of the binding-time information that it produces determines the degree of specialization of programs. We present a binding-time analysis for applicative languages. This analysis is polyvariant and treats both higher-order functions and data structures. It handles typed as well as untyped programs. It has been implemented and is used in a partial evaluation system named Schism. The main contributions of this work can be summarized as follows. •Our analysis combines both a data flow and a control flow analyses. This key feature makes it possible to create different binding-time descriptions of a function (or a data structure) with respect to data flow information. Also, this approach yields more accurate control flow information than one that separates control flow and data flow analyses. •The degree of polyvariance achieved by our analysis is not fixed. In fact, the analysis is parameterized with respect to a function that defines the degree of polyvariance. •Untyped as well as typed programs are treated by our analysis. When available, type information is used to improve the accuracy of binding-time descriptions.

REFERENCES

• 1: A. Bondorf, Automatic autoprojection of higher order recursive equations, Proceedings of the third European symposium on programming on ESOP '90, p.70-87, May 1990, Copenhagen, Denmark
• 2: Anders Bondorf, Automatic autoprojection of higher order recursive equations, Science of Computer Programming, v.17 n.1-3, p.3-34, Dec. 1991
• 3: 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]
• 4: Charles Consel, New Insights into Partial Evaluation: the SCHISM Experiment, Proceedings of the 2nd European Symposium on Programming, p.236-246, March 21-24, 1988
• 5: C. Consel. Analyse de Programmes, Evaluation Partielle et Ggngration de Compilateurs. PhD thesis, Universit~ de Paris VI, Paris, France, June 1989.
• 6: Charles Consel, Binding time analysis for high order untyped functional languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.264-272, June 27-29, 1990, Nice, France [doi>10.1145/91556.91668]
• 7: Charles Consel, A tour of Schism: a partial evaluation system for higher-order applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.145-154, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154645]
• 8: C. Consel and S.C. Khoo. On-line &: off-line partial evaluation: Semantic specifications and correctness proofs. Research Report 896, Yale University, New Haven, Connecticut, USA, 1992.
• 9: A. Deutsch. Operational Models of Programming Languages and Representations of Relations on Regular Languages with Application to the Static Determination of Dynamic Aliasing Properties of Data. PhD thesis, LIX, Ecole Polytechnique, Palaiseau, France, 1991.
• 10: M. Gengler and B. Rytz. A polyvariant binding time analysis handfing partially known values. In Workshop on Static Analysis, volume 81-82 of Bigre Journal, pages 322-330. IRISA, Rennes, France, 1992.
• 11: Carsten K. Gomard, Partial type inference for untyped functional programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.282-287, June 27-29, 1990, Nice, France [doi>10.1145/91556.91672]
• 12: Fritz Henglein, Efficient type inference for higher-order binding-time analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.448-472, June 1991, Cambridge, Massachusetts, United States
• 13: P. Hudak , J. Young, A collecting interpretation of expressions, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-118, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73570]
• 14: Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
• 15: R. Milner, M. Tofte, ~nd R. Harper. The Definition of ML. MIT Press, 1990.
• 16: 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
• 17: F. Nielson , R. H. Nielson, Automatic binding time analysis for a typed &lgr;-calculus, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-106, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73569]
• 18: B. Rytz and M. Gengler. A polyvariant binding time analysis, in C. Consel, editor, A CM Workshop on Partial Evaluation and Semantics.Based Program Manipulation, pages 21-28. Yale University, 1992. Research Report 909.
• 19: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Optimization

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

General Terms:
Algorithms, Languages