Charles Consel
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.
- 1.A. Bondorf. Automatic autoprojection of higher order recursive equations. In N. D. Jones, editor, ESOP'90, 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 70-87. Springer-Verlag, 1990. Google Scholar
Digital Library
- 2.A. Bondorf. Automatic autoprojection of higherorder recursive equations. Science of Computer Programming, 17:3-34, 1991. Google ScholarDigital Library
- 3.W. Clinger and J. Rees (editors). Revised4 report on the algorithmic language Scheme. LISP Pointers, IV(3):1-55, July-September 1991. Google ScholarDigital Library
- 4.C. Consel. New insights into partial evaluation: the Schism experiment. In H. Ganzinger, editor, ESOP'88, 2nd European Symposium on Programming, volume 300 of Lecture Notes in Computer Science, pages 236-246. Springer-Verlag, 1988. Google ScholarDigital Library
- 5.C. Consel. Analyse de Programmes, Evaluation Partielle et Ggngration de Compilateurs. PhD thesis, Universit~ de Paris VI, Paris, France, June 1989.Google Scholar
- 6.C. Consel. Binding time analysis for higher order untyped functional languages, in A CM Conference on Lisp and Functional Programming, pages 264- 272, 1990. Google ScholarDigital Library
- 7.C. Consel. A tour of Schism: A partial evaluation system for higher-order applicative languages. In A CM Symposium on Partial Evaluation and Semantics-Based Program Manipulation, 1993. To appear. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 11.C. K. Gomard. Partial type inference for untyped functional programs. In A CM Conference on Lisp and Functional Programming, pages 282-287, 1990. Google ScholarDigital Library
- 12.F. Henglein. Efficient type inference for higherorder binding-time analysis. In FPCA'91, 5th International Conference on Functional Programming Languages and Computer Architecture, pages 448-472, 1991. Google ScholarDigital Library
- 13.P. Hudak and J. Young. A collecting interpretation of expressions (without Powerdomains). In A CM Symposium on Principles of Programming Languages, pages 107-118, 1988. Google ScholarDigital Library
- 14.N. D. Jones and A. Mycroft. Data flow analysis of appficative programs using minimal function graphs, in A CM Symposium on Principles of Programming Languages, 1986. Google ScholarDigital Library
- 15.R. Milner, M. Tofte, ~nd R. Harper. The Definition of ML. MIT Press, 1990.Google Scholar
- 16.T. Mogensen. Binding time analysis for polymorphically typed higher order languages. In J. Diaz and F. Orejas, editors, International Joint Conference on Theory and Practice of Software Development, volume: 352 of Lecture Notes in Computer Science, pages 298-312. Springer-Verlag, 1989. Google ScholarDigital Library
- 17.H. R. Nielson and F. Nielson. Automatic binding time analysis for a typed ),-calculus. In A CM Symposium on Principles of Programming Languages, pages 98-106, 1988. Google ScholarDigital Library
- 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.Google Scholar
- 19.P. Sestoft. Replacing function parameters by global variables. In FPCA '89, 4th international Conference on Functional Programming Languages and Computer ArcJiitecture, pages 39-53, 1989. Google ScholarDigital Library
Index Terms
- Polyvariant binding-time analysis for applicative languages
Recommendations
Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity
PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationSince a binding-time analysis determines how an off-line partial evaluator will specialize a program, the accuracy of the binding-time information directly determines the degree of specialization. We have designed and implemented a binding-time analysis ...
Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity
Since a binding-time analysis determines how an off-line partial evaluator will specialize a program, the accuracy of the binding-time information directly determines the degree of specialization. We have designed and implemented a binding-time analysis ...
Comments