article

A self-applicable online partial evaluator for recursive flowchart languages

Author:

Robert GlückAuthors Info & Claims

Software—Practice & Experience, Volume 42, Issue 6

Pages 649 - 673

https://doi.org/10.1002/spe.1086

Published: 01 June 2012 Publication History

Abstract

This paper describes a self-applicable online partial evaluator for a flowchart language with recursive calls. Self-application of the partial evaluator yields generating extensions that are as efficient as those reported in the literature for offline partial evaluation. This result is remarkable because it has been assumed that online partial evaluation techniques unavoidably lead to inefficient and overgeneralized generating extensions. The purpose of this paper is not to determine which kind of partial evaluation is better, but to show how the problem can be solved by recursive polyvariant specialization. The design of the self-applicable online partial evaluator is based on a number of known techniques, but by combining them in a new way this result can be produced. The partial evaluator, its techniques, and its implementation are presented in full. Self-application according to all three Futamura projections is demonstrated. The complete bootstrap of a compiler generator from a partial evaluator is also reported. Copyright © 2011 John Wiley & Sons, Ltd.

References

[1]

Futamura Y. Partial evaluation of computing process—An approach to a compiler-compiler. Systems, Computers, Controls 1971; 2(5):45–50. Reprinted in Higher-order and Symbolic Computation 1999; 12(4):381–391.

[2]

Jones ND, Sestoft P, Søndergaard H. An experiment in partial evaluation: The generation of a compiler generator. Rewriting Techniques and Applications. Proceedings (Lecture Notes in Computer Science, vol. 202), Jouannaud JP (ed.). Springer: Berlin, 1985; 124–140.

[3]

Consel C. New insights into partial evaluation: The Schism experiment. ESOP'88. Proceedings (Lecture Notes in Computer Science, vol. 300), Ganzinger H (ed.). Springer: Berlin, 1988; 236–247.

[4]

Mogensen TÆ. Partially static structures in a self-applicable partial evaluator. Partial Evaluation and Mixed Computation, Bjørner D, Ershov AP, Jones ND (eds). North-Holland: Amsterdam, 1988; 325–347.

[5]

Romanenko SA. The specializer Unmix. 1990. Program and documentation available at: {30 October 2010}.

[6]

Bondorf A, Danvy O. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming 1991; 16(2):151–195.

[7]

Gomard CK, Jones ND. Compiler generation by partial evaluation: A case study. Structured Programming 1991; 12(3):123–144.

[8]

Jones ND, Gomard CK, Sestoft P. Partial Evaluation and Automatic Program Generation. Prentice-Hall: Englewood Cliffs, NJ, 1993.

[9]

Jones ND. Automatic program specialization: A re-examination from basic principles. Partial Evaluation and Mixed Computation, Bjørner D, Ershov AP, Jones ND (eds). North-Holland: Amsterdam, 1988; 225–282.

[10]

Bulyonkov MA. Polyvariant mixed computation for analyzer programs. Acta Informatica 1984; 21(5):473–484.

[11]

Hatcliff J. An introduction to online and offline partial evaluation using a simple flowchart language. Partial Evaluation. Practice and Theory (Lecture Notes in Computer Science, vol. 1706), Hatcliff J, Mogensen TÆ, Thiemann P (eds). Springer: Berlin, 1999; 20–82.

[12]

Debois S. Imperative-program transformation by instrumented-interpreter specialization. Higher-order and Symbolic Computation 2008; 21(1–2):37–58.

[13]

Christensen NH, Glück R. Offline partial evaluation can be as accurate as online partial evaluation. ACM TOPLAS 2004; 26(1):191–220.

[14]

Glück R, Sørensen MH. A roadmap to metacomputation by supercompilation. Partial Evaluation. Proceedings (Lecture Notes in Computer Science, vol. 1110), Danvy O, Glück R, Thiemann P (eds). Springer: Berlin, 1996; 137–160.

[15]

Aho AV, Sethi R, Ullman JD. Compilers: Principles, Techniques, and Tools. Addison-Wesley: Reading, MA, 1986.

[16]

Glück R. An experiment with the fourth Futamura projection. Perspectives of System Informatics. Proceedings (Lecture Notes in Computer Science, vol. 5947), Pnueli A, Virbitskaite I, Voronkov A (eds). Springer: Berlin, 2010; 135–150.

Digital Library

[17]

Ruf E, Weise D. On the specialization of online program specializers. Journal of Functional Programming 1993; 3(3):251–281.

[18]

Asai K. Integrating partial evaluators into interpreters. Semantics, Applications, and Implementation of Program Generation. Proceedings (Lecture Notes in Computer Science, vol. 2196), Taha W (ed.). Springer: Berlin, 2001; 126–145.

[19]

Glück R, Jørgensen J. Generating optimizing specializers. IEEE International Conference on Computer Languages. IEEE Computer Society Press: Silver Spring, MD, 1994; 183–194.

[20]

Ershov AP. Mixed computation in the class of recursive program schemata. Acta Cybernetica 1978; 4(1):19–23.

[21]

Jones ND. Mix ten years later. Partial Evaluation and Semantics-based Program Manipulation. Proceedings. ACM Press: New York, 1995; 24–38.

[22]

Jones ND, Sestoft P, Søndergaard H. Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation 1989; 2(1):9–50.

[23]

Ershov AP. On the partial computation principle. Information Processing Letters 1977; 6(2):38–41.

[24]

Glück R. Is there a fourth Futamura projection? Partial Evaluation and Program Manipulation. Proceedings. ACM Press: New York, 2009; 51–60.

[25]

Jones ND. Challenging problems in partial evaluation and mixed computation. Partial Evaluation and Mixed Computation, Bjørner D, Ershov AP, Jones ND (eds). North-Holland: Amsterdam, 1988; 1–14.

[26]

Sestoft P. The structure of a self-applicable partial evaluator. Technical Report 85/11, DIKU, University of Copenhagen, Denmark 1985. Extended version of a paper with the same title in Lecture Notes in Computer Science, vol. 217, 1986; 236–256.

Digital Library

[27]

Bondorf A. A self-applicable partial evaluator for term rewriting systems. TAPSOFT'89. Proceedings (Lecture Notes in Computer Science, vol. 352), Díaz J, Orejas F (eds). Springer: Berlin, 1989; 81–95.

[28]

Gade J, Glück R. On Jones-optimal specializers: A case study using Unmix. Programming Languages and Systems. Proceedings (Lecture Notes in Computer Science, vol. 4279), Kobayashi N (ed.). Springer: Berlin, 2006; 406–422.

[29]

Futamura Y. Partial computation of programs. RIMS Symposia on Software Science and Engineering. Proceedings (Lecture Notes in Computer Science, vol. 147), Goto E, Furukawa K, Nakajima R, Nakata I, Yonezawa A (eds). Springer: Berlin, 1983; 1–35.

[30]

Glück R. On the generation of specializers. Journal of Functional Programming 1994; 4(4):499–514.

[31]

Glück R. Towards multiple self-application. Partial Evaluation and Semantics-based Program Manipulation. Proceedings. ACM Press: New York, 1991; 309–320.

[32]

Glück R, Kawada Y, Hashimoto T. Transforming interpreters into inverse interpreters by partial evaluation. Partial Evaluation and Semantics-based Program Manipulation. Proceedings. ACM Press: New York, 2003; 10–19.

[33]

Mogensen TÆ. Self-applicable online partial evaluation of the pure lambda calculus. Partial Evaluation and Semantics-based Program Manipulation. Proceedings. ACM Press: New York, 1995; 39–44.

[34]

Sperber M. Self-applicable online partial evaluation. Partial Evaluation. Proceedings (Lecture Notes in Computer Science, vol. 1110), Danvy O, Glück R, Thiemann P (eds). Springer: Berlin, 1996; 465–480.

[35]

Sumii E, Kobayashi N. A hybrid approach to online and offline partial evaluation. Higher-order and Symbolic Computation 2001; 14(2–3):101–142.

[36]

Kleinrubatscher P, Kriegshaber A, Zöchling R, Glück R. Fortran program specialization. SIGPLAN Notices 1995; 30(4):61–70.

[37]

Romanenko SA. A compiler generator produced by a self-applicable specializer can have a surprisingly natural and understandable structure. Partial Evaluation and Mixed Computation, Bjørner D, Ershov AP, Jones ND (eds). North-Holland: Amsterdam, 1988; 445–463.

Cited By

Leißa RBoesche KHack SPérard-Gayot AMembarth RSlusallek PMüller ASchmidt B(2018)AnyDSL: a partial evaluation framework for programming high-performance librariesProceedings of the ACM on Programming Languages10.1145/32764892:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276489
Leißa RBoesche KHack SMembarth RSlusallek P(2015)Shallow embedding of DSLs via online partial evaluationACM SIGPLAN Notices10.1145/2936314.281420851:3(11-20)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2936314.2814208
Leißa RBoesche KHack SMembarth RSlusallek PKästner CGokhālé A(2015)Shallow embedding of DSLs via online partial evaluationProceedings of the 2015 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/2814204.2814208(11-20)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2814204.2814208
Show More Cited By

Recommendations

A self-applicable partial evaluator for the lambda calculus: correctness and pragmatics

We describe theoretical and a few practical aspects of an implemented self-applicable partial evaluator for the untyped lambda calculus with constants, conditionals, and a fixed point operator.

The purpose of this paper is first to announce the existence ...
Is there a fourth Futamura projection?
PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation

The three classic Futamura projections stand as a cornerstone in the development of partial evaluation. The observation by Futamura [1983], that compiler generators produced by his third projection are self-generating, and the insight by Klimov and ...
The Second Futamura Projection for Type-Directed Partial Evaluation

A generating extension of a program specializes the program with respect to part of the input. Applying a partial evaluator to the program trivially yields a generating extension, but specializing the partial evaluator with respect to the program often ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software

Software Volume 42, Issue 6

June 2012

126 pages

ISSN:0038-0644

EISSN:1097-024X

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 June 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Leißa RBoesche KHack SPérard-Gayot AMembarth RSlusallek PMüller ASchmidt B(2018)AnyDSL: a partial evaluation framework for programming high-performance librariesProceedings of the ACM on Programming Languages10.1145/32764892:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276489
Leißa RBoesche KHack SMembarth RSlusallek P(2015)Shallow embedding of DSLs via online partial evaluationACM SIGPLAN Notices10.1145/2936314.281420851:3(11-20)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2936314.2814208
Leißa RBoesche KHack SMembarth RSlusallek PKästner CGokhālé A(2015)Shallow embedding of DSLs via online partial evaluationProceedings of the 2015 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/2814204.2814208(11-20)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1145/2814204.2814208
Glück R(2011)Bootstrapping compiler generators from partial evaluatorsProceedings of the 8th international conference on Perspectives of System Informatics10.1007/978-3-642-29709-0_13(125-141)Online publication date: 27-Jun-2011
https://dl.acm.org/doi/10.1007/978-3-642-29709-0_13

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents