skip to main content
10.1145/1480945.1480954acmconferencesArticle/Chapter ViewAbstractPublication PagespepmConference Proceedingsconference-collections
research-article

Is there a fourth Futamura projection?

Published: 19 January 2009 Publication History

Abstract

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 Romanenko [1987], that Futamura's abstraction scheme can be continued beyond the three projections, are systematically investigated, and several new applications for compiler generators are proposed. Possible applications include the generation of quasi-online compiler generators and of compiler generators for domain-specific languages, and the bootstrapping of compiler generators from program specializers. From a theoretical viewpoint, there is equality between the class of self-generating compiler generators and the class of compiler generators produced by the third Futamura projection. This exposition may lead to new practical applications of compiler generators, as well as deepen our theoretical understanding of program specialization.

References

[1]
L. O. Andersen. Partial evaluation of C and automatic compiler generation. In U. Kastens, P. Pfahler (eds.), Compiler Construction. 4th International Conferences, Lecture Notes in Computer Science, Vol. 641, 251--257. Springer--Verlag, 1992.
[2]
L. O. Andersen. Program analysis and specialization for the C programming language. Ph.D. thesis. DIKU Report 94/19, Dept. of Computer Science, University of Copenhagen, 1994.
[3]
L. Birkedal, M. Welinder. Hand-writing program generator generators. In M. Hermenegildo, J. Penjam (eds.), Programming Language Implementation and Logic Programming. Proceedings, Lecture Notes in Computer Science, Vol. 844, 198--214. Springer-Verlag, 1994.
[4]
A. Bondorf. A self-applicable partial evaluator for term rewriting systems. In J. Diaz, F. Orejas (eds.), TAPSOFT'89, Lecture Notes inComputer Science, Vol. 352, 81--96. Springer-Verlag, 1989.
[5]
A. Bondorf, O. Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming, 16(2):151--195, 1991.
[6]
A. Bondorf, D. Dussart. Improving CPS-based partial evaluation: writing cogen by hand. In Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Technical Report 94/9, 1--9. University of Melbourne, Australia, 1994.
[7]
P. Bratley, J. Millo. Computer recreations: self-reproducing programs. Software -- Practice and Experience, 2(4):397--400, 1972.
[8]
C. Consel. New insights into partial evaluation: the Schism experiment. In H. Ganzinger (ed.), ESOP'88, Lecture Notes in Computer Science, Vol. 300, 236--247. Springer-Verlag, 1988.
[9]
C. Consel, J. L. Lawall, A.-F. Le Meur. A tour of Tempo: a program specializer for the C language. Science of Computer Programming, 52(1-3):341--370, 2004.
[10]
J. Earley, H. Sturgis. A formalism for translator interactions. Communications of the ACM, 13(10):607--617, 1970.
[11]
A. P. Ershov. On the partial computation principle. Information Processing Letters, 6(2):38--41, 1977.
[12]
A. P. Ershov. On the essence of compilation. In E. Neuhold (ed.), Formal Description of Programming Concepts, 391--420. North-Holland, 1978.
[13]
Y. Futamura. Partial evaluation of computing process -- an approach to a compiler-compiler. Systems, Computers, Controls, 2(5):45--50, 1971. Reprinted in Higher-Order and Symbolic Computation, 12(4): 381--391, 1999.
[14]
Y. Futamura. EL1 partial evaluator. Progress report, Center for Research in Computing Technology, Harvard University, 1973. Extract from the introduction reproduced in {16}.
[15]
Y. Futamura. Partial computation of programs. In E. Goto, K. Furukawa, R. Nakajima, I. Nakata, A. Yonezawa (eds.), RIMS Symposia on Software Science and Engineering, Lecture Notes in Computer Science, Vol. 147, 1--35. Springer-Verlag, 1983.
[16]
Y. Futamura. Partial evaluation of computation process, revisited. Higher-Order and Symbolic Computation, 12(4):377--380, 1999.
[17]
Y. Futamura, Z. Konishi, R. Glück. WSDFU: Program transformation system based on generalized partial computation. In T. Æ. Mogensen, D. Schmidt, I. H. Sudborough (eds.), The Essence of Computation: Complexity, Analysis, Transformation, Lecture Notes in Computer Science, Vol. 2566, 358--378. Springer-Verlag, 2002.
[18]
R. Glück. On the generation of specializers. Journal of Functional Programming, 4(4):499--514, 1994.
[19]
R. Glück. On the mechanics of metasystem hierarchies in program transformation. In M. Proietti (ed.), Logic Program Synthesis and Transformation. Proceedings, Lecture Notes in Computer Science, Vol. 1048, 234--251. Springer-Verlag, 1996.
[20]
R. Glück, J. Jørgensen. Efficient multi-level generating extensions for program specialization. In M. Hermenegildo, S. D. Swierstra (eds.), Programming Languages: Implementations, Logics and Programs. Proceedings, Lecture Notes in Computer Science, Vol. 982, 259--278. Springer-Verlag, 1995.
[21]
R. Glück, J. Jørgensen. An automatic program generator for multi-level specialization. Lisp and Symbolic Computation, 10(2):113--158, 1997.
[22]
R. Glück, A. V. Klimov. Metasystem transition schemes in computer science and mathematics. World Futures: the Journal of General Evolution, 45:213--243, 1995.
[23]
R. Glück, A. V. Klimov. A regeneration scheme for generating extensions. Information Processing Letters, 62(3):127--134, 1997.
[24]
C. K. Gomard, N. D. Jones. Compiler generation by partial evaluation: a case study. Structured Programming, 12:123--144, 1991.
[25]
C. K. Gomard, N. D. Jones. A partial evaluator for the untyped lambda calculus. Journal of Functional Programming, 1(1):21--69, 1991.
[26]
C. K. Holst. Language triplets: the Amix approach. In D. Bjørner, A. P. Ershov, N. D. Jones (eds.), Partial Evaluation and Mixed Computation, 167--185. North--Holland, 1988.
[27]
C. K. Holst, J. Launchbury. Handwriting cogen to avoid problems with static typing. In Fourth Annual Glasgow Workshop on Functional Programming. Draft Proceedings, 210--218, 1991.
[28]
N. D. Jones, C. K. Gomard, P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.
[29]
N. D. Jones, P. Sestoft, H. Søndergaard. An experiment in partial evaluation: the generation of a compiler generator. In J.-P. Jouannaud (ed.), Rewriting Techniques and Applications, Lecture Notes in Computer Science, Vol. 202, 124--140. Springer-Verlag, 1985.
[30]
N. D. Jones, P. Sestoft, H. Søndergaard. Mix: a self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation, 2(1):9--50, 1989.
[31]
J. Jørgensen. Generating a compiler for a lazy language by partial evaluation. In Conference Record of the Nineteenth Symposium on Principles of Programming Languages, 258--268. ACM Press, 1992.
[32]
P. Kleinrubatscher, A. Kriegshaber, R. Zöchling, R. Glück. Fortran program specialization. SIGPLAN Notices, 30(4):61--70, 1995.
[33]
A. V. Klimov, S. A. Romanenko. Metavychislitel' dlja jazyka Refal. Osnovnye ponjatija i primery. (A metaevaluator for the language Refal. Basic concepts and examples). Preprint 71, Keldysh Institute of Applied Mathematics, Academy of Sciences of the USSR, Moscow, 1987. (in Russian).
[34]
O. Lecarme, M.-C. Peyrolle-Thomas. Self-compiling compilers: an appraisal of their implementation and portability. Software -- Practice and Experience, 8:149--170, 1978.
[35]
M. Leuschel. The Ecce partial deduction system. In G. Puebla et al. (eds.), Proceedings of the ILPS'97 Workshop on Tools and Environments for (Constraint) Logic Programming, Technical Report CLIP7/97.1. Polytechnic University of Madrid, Spain, 1997.
[36]
M. Leuschel, J. Jørgensen. Efficient specialisation in Prolog using a hand-written compiler generator LOGEN. Electronic Notes in Theoretical Computer Science, 30(2):157--162, 2000.
[37]
T. Æ. Mogensen. Self-applicable online partial evaluation of the pure lambda calculus. In Symposium on Partial Evaluation and Semantics-Based Program Manipulation, 39--44. ACM Press, 1995.
[38]
T. Æ. Mogensen, A. Bondorf. Logimix: a self-applicable partial evaluator for Prolog. In K.-K. Lau, T. Clement (eds.), Logic Program Synthesis and Transformation, Workshops in Computing, 214--227. Springer-Verlag, 1993.
[39]
S. A. Romanenko. The specializer Unmix, 1990. Program and documentation available from ftp://ftp.diku.dk/pub/diku/dists/jones-book/Romanenko/.
[40]
M. H. Sørensen, R. Glück, N. D. Jones. A positive supercompiler. Journal of Functional Programming, 6(6):811--838, 1996.
[41]
E. Sumii, N. Kobayashi. Online-and-offline partial evaluation: a mixed approach. In Workshop on Partial Evaluation and Semantics-Based Program Manipulation, 12--21. ACM Press, 2000.
[42]
W. Taha. A gentle introduction to multi-stage programming. In C. Lengauer, D. Batory, C. Consel, M. Odersky (eds.), Domain-specific program generation. Proceedings, Vol. 3016, 30--50. Springer-Verlag, 2004.
[43]
S. Thibault, C. Consel, J. L. Lawall, R. Marlet, G. Muller. Static and dynamic program compilation by interpreter specialization. Higher-Order and Symbolic Computation, 13(3):161--178, 2000.
[44]
P. Thiemann. Cogen in six lines. In ACM International Conference on Functional Programming, 180--189. ACM Press, 1996.
[45]
P. Thiemann. The PGG system: User manual, 2003. Program and documentation available from http://www.informatik.uni-freiburg.de/proglang/software/pgg/.
[46]
V. F. Turchin. A supercompiler system based on the language Refal. SIGPLAN Notices, 14(2):46--54, 1979.
[47]
V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292--325, 1986.
[48]
V. F. Turchin. Metacomputation: metasystem transitions plus supercompilation. In O. Danvy, R. Glück, P. Thiemann (eds.), Partial Evaluation. Proceedings, Lecture Notes in Computer Science, Vol. 1110, 481--509. Springer-Verlag, 1996.
[49]
V. F. Turchin, And. V. Klimov, Ark. V. Klimov, V. F. Khoroshevsky, A. G.Krasovsky, S. A. Romanenko, I. B. Shchenkov, E. V. Travkina. Bazisnyj Refal i ego realizacija na vychislitel'nykh mashinakh (Basic Refal and its implementation on computers). GOSSTROJ SSSR, CNIPIASS, 1977. (in Russian).

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation
January 2009
208 pages
ISBN:9781605583273
DOI:10.1145/1480945
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 January 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Futamura projections
  2. bootstrapping
  3. cogen approach
  4. compiler generators
  5. domain-specific languages
  6. generator self-generation
  7. program specialization
  8. self-application

Qualifiers

  • Research-article

Conference

PEPM '09
Sponsor:
PEPM '09: Partial Evaluation and Program Manipulation
January 19 - 20, 2009
GA, Savannah, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)21
  • Downloads (Last 6 weeks)5
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
  • (2023)A Survey on Hypergraph Representation LearningACM Computing Surveys10.1145/360577656:1(1-38)Online publication date: 22-Jun-2023
  • (2023)Big Code Search: A BibliographyACM Computing Surveys10.1145/360490556:1(1-49)Online publication date: 26-Aug-2023
  • (2017)Jones-optimal partial evaluation by specialization-safe normalizationProceedings of the ACM on Programming Languages10.1145/31581022:POPL(1-28)Online publication date: 27-Dec-2017
  • (2016)On fast large-scale program analysis in DatalogProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892226(196-206)Online publication date: 17-Mar-2016
  • (2014)Moving computations from run-time to compile-timeProceedings of the 11th ACM Conference on Computing Frontiers10.1145/2597917.2597933(1-10)Online publication date: 20-May-2014
  • (2014)Building Code Generators for DSLs Using a Partial Evaluator for the Xtend LanguagePart I of the Proceedings of the 6th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change - Volume 880210.1007/978-3-662-45234-9_29(407-424)Online publication date: 8-Oct-2014
  • (2011)Justified terminological reasoningProceedings of the 8th international conference on Perspectives of System Informatics10.1007/978-3-642-29709-0_30(349-361)Online publication date: 27-Jun-2011
  • (2011)Multi-result supercompilation as branching growth of the penultimate level in metasystem transitionsProceedings of the 8th international conference on Perspectives of System Informatics10.1007/978-3-642-29709-0_19(210-226)Online publication date: 27-Jun-2011
  • (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
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media