Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-29T16:16:52.039Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient analyses for realistic off-line partial evaluation

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Anders Bondorf  and
Jesper Jørgensen
Anders Bondorf
Affiliation:
DIKU, Department of Computer Science, University of CopenhagenUniversitetsparken 1, DK-2100 Copenhagen ø, Denmark (e-mail: anders@diku.dk)
Jesper Jørgensen
Affiliation:
DIKU, Department of Computer Science, University of CopenhagenUniversitetsparken 1, DK-2100 Copenhagen ø, Denmark (e-mail: knud@diku.dk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Based on Henglein's efficient binding-time analysis for the lambda calculus (with constants and ‘fix’) (Henglein, 1991), we develop three efficient analyses for use in the preprocessing phase of Similix, a self-applicable partial evaluator for a higher-order subset of Scheme. The analyses developed in this paper are almost-linear in the size of the analysed program. (1) A flow analysis determines possible value flow between lambda-abstractions and function applications and between constructor applications and selector/predicate applications. The flow analysis is not particularly biased towards partial evaluation; the analysis corresponds to the closure analysis of Bondorf (1991b). (2) A (monovariant) binding-time analysis distinguishes static from dynamic values; the analysis treats both higher-order functions and partially static data structures. (3) A new is-used analysis, not present in Bondorf (1991b), finds a non-minimal binding-time annotation which is ‘safe’ in a certain way: a first-order value may only become static if its result is ‘needed’ during specialization; this ‘poor man's generalization’ (Holst, 1988) increases termination of specialization. The three analyses are performed sequentially in the above mentioned order since each depends on results from the previous analyses. The input to all three analyses are constraint sets generated from the program being analysed. The constraints are solved efficiently by a normalizing union/find-based algorithm in almost-linear time. Whenever possible, the constraint sets are partitioned into subsets which are solved in a specific order; this simplifies constraint normalization. The framework elegantly allows expressing both forwards and backwards components of analyses. In particular, the new is-used analysis is of backwards nature. The three constraint normalization algorithms are proved correct (soundness, completeness, termination, existence of a best solution). The analyses have been implemented and integrated in the Similix system. The new analyses are indeed much more efficient than those of Bondorf (1991b); the almost-linear complexity of the new analyses is confirmed by the implementation.

Type
Articles
Information
Journal of Functional Programming , Volume 3 , Issue 3 , July 1993 , pp. 315 - 346
Copyright
Copyright © Cambridge University Press 1993

References

Bondorf, Anders. (1991a) Automatic autoprojection of higher order recursive equations. Science of computer programming, 17(1–3), 3–34. Revision of paper in ESOP'90, LNCS 432, May 1990.CrossRefGoogle Scholar
Bondorf, Anders. (1991b) (Sept.). Similix Manual, system version 4.0. DIKU, University of Copenhagen, Denmark.Google Scholar
Bondorf, Anders. (1992) (June). Improving binding times without explicit cps-conversion. Pages 1–10of: 1992 ACM Conference on Lisp and Functional Programming.San Francisco, California. LISP Pointers V, 1.CrossRefGoogle Scholar
Bondorf, Anders, & Danvy, Olivier. (1991) Automatic autoprojection of recursive equations with global variables and abstract data types. Science of computer programming, 16, 151–195.Google Scholar
Bondorf, Anders, & Jørgensen, Jesper. (1993) Efficient analyses for realistic off-line partial evaluation: extended version. Tech. rept. 93/4. DIKU, University of Copenhagen, Denmark.CrossRefGoogle Scholar
Consel, Charles. (1990) (June). Binding time analysis for higher order untyped functional languages. Pages 264–272of: 1990 ACM Conference on Lisp and Functional Programming.Nice, France.Google Scholar
Gomard, Carsten K., & Jones, Neil D. (1991) A partial evaluator for the untyped lambda-calculus. Journal of functional programming, 1(1), 21–69.Google Scholar
Henglein, Fritz. (1991) Efficient type inference for higher-order binding-time analysis. Pages 448–472of: Hughes, John (ed), Conference on Functional Programming and Computer Architecture,Cambridge, Massachusetts.Lecture Notes in Computer Science 523. Springer-Verlag.Google Scholar
Henglein, Fritz. (1992) (Mar.). Simple closure analysis. Working note.Google Scholar
Holst, Carsten Kehler. (1988) (Aug.). Poor man's generalization. Working note.Google Scholar
IEEE standard for the Scheme programming language. IEEE Std 1178-1990. (1990) May.Google Scholar
Jones, Neil D., Sestoft, Peter, & Søndergaard, Harald. (1985) An experiment in partial evaluation: the generation of a compiler generator. Pages 124–140of: Jouannaud, Jean-Pierre (ed), Rewriting Techniques and Applications, Dijon, France. Lecture Notes in Computer Science 202. Springer-Verlag.Google Scholar
Jones, Neil D., Sestoft, Peter, & Søndergaard, Harald. (1989) MIX: a self-applicable partial evaluator for experiments in compiler generation. Lisp and symbolic computation, 2(1), 9–50.Google Scholar
Jørgensen, Jesper. (1992) (Jan.). Generating a compiler for a lazy language by partial evaluation. Pages 258–268of: Nineteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages.Albuquerque, New Mexico.CrossRefGoogle Scholar
Katz, Morry, & Weise, Daniel. (1992) (June). Towards a new perspective on partial evaluation. Pages 29–37of: ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, San Francisco, California. Yale University, report YALEU/DCS/RR-909.Google Scholar
Launchbury, John. (1991) Projection factorisations in partial evaluation. Distinguished Dissertations in Computer Science. Cambridge University Press.Google Scholar
Nielson, Hanne R., & Nielson, Flemming. (1988) Automatic binding time analysis for a typed λ-calculus. Pages 98–106of: Fifteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages.San Diego, California.CrossRefGoogle Scholar
Palsberg, Jens. (1993) Correctness of binding time analysis. Journal of functional programming, special issue on partial evaluation.CrossRefGoogle Scholar
Schmidt, David A. (1988) Static properties of partial evaluation. Pages 465–483of: Bjørner, Dines, Ershov, Andrei P., & Jones, Neil D. (eds), Partial Evaluation and Mixed Computation. North-Holland.Google Scholar
Sestoft, Peter. (1988) (Student Report 88-7-2, October). Replacing function parameters by global variables. M.Phil. thesis, DIKU, University of Copenhagen, Denmark.Google Scholar
Wand, Mitchell. (1993) Specifying the correctness of binding-time analysis. Journal of functional programming, special issue on partial evaluation.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.