Is there a fourth Futamura projection?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Is there a fourth Futamura projection?

Full text

Pdf (599 KB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation table of contents

Savannah, GA, USA

SESSION: Partial evaluation and specialization table of contents

Pages 51-60

Year of Publication: 2009

ISBN:978-1-60558-327-3

Author

Robert Glück

University of Copenhagen, Copenhagen, Denmark

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 171, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1480945.1480954 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Lars Ole Andersen, Partial Evaluation of C and Automatic Compiler Generation (Extended Abstract), Proceedings of the 4th International Conference on Compiler Construction, p.251-257, October 05-07, 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	Lars Birkedal , Morten Welinder, Hand-Writing Program Generator Generators, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.198-214, September 14-16, 1994
	4	Anders Bondorf, A Self-Applicable Partial Evaluator for Term Rewriting Systems, 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.81-95, March 13-17, 1989
	5	Anders Bondorf , Olivier Danvy, Automatic autoprojection of recursive equations with global variable and abstract data types, Science of Computer Programming, v.16 n.2, p.151-195, Sept. 1991 [doi>10.1016/0167-6423(91)90002-F]
	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	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
	9	Charles Consel , Julia L. Lawall , Anne-Françoise Le Meur, A tour of tempo: a program specializer for the C language, Science of Computer Programming, v.52 n.1-3, p.341-370, August 2004 [doi>10.1016/j.scico.2004.03.011]
	10	Jay Earley , Howard Sturgis, A formalism for translator interactions, Communications of the ACM, v.13 n.10, p.607-617, Oct. 1970 [doi>10.1145/355598.362740]
	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	Yoshihiko Futamura, Partial Evaluation of Computation Process—AnApproach to a Compiler-Compiler, Higher-Order and Symbolic Computation, v.12 n.4, p.381-391, December 1999 [doi>10.1023/A:1010095604496]
	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	Yoshihiko Futamura, Parital Computation of Programs, Proceedings of RIMS Symposium on Software Science and Engineering, p.1-35, January 1983
	16	Yoshihiko Futamura, Partial Evaluation of Computation Process, Revisited, Higher-Order and Symbolic Computation, v.12 n.4, p.377-380, December 1999 [doi>10.1023/A:1010043619517]
	17	Yoshihiko Futamura , Zenjiro Konishi , Robert Glück, WSDFU: program transformation system based on generalized partial computation, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	18	R. Glück. On the generation of specializers. Journal of Functional Programming, 4(4):499--514, 1994.
	19	Robert Glück, On the Mechanics of Metasystem Hierarchies in Program Transformation, Proceedings of the 5th International Workshop on Logic Programming Synthesis and Transformation, p.234-251, September 20-22, 1995
	20	Robert Glück , Jesper Jørgensen, Efficient Multi-level Generating Extensions for Program Specialization, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.259-278, September 20-22, 1995
	21	Robert Glück , Jesper Jørgensen, An Automatic Program Generator for Multi-Level Specialization, Lisp and Symbolic Computation, v.10 n.2, p.113-158, July 1997 [doi>10.1023/A:1007763000430]
	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	Robert Glück , Andrei Klimov, A regeneration scheme for generating extensions, Information Processing Letters, v.62 n.3, p.127-134, May 14, 1997 [doi>10.1016/S0020-0190(97)00055-0]
	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	Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	29	Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, May 20-22, 1985, Dijon, France
	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	Jesper Jørgensen, Generating a compiler for a lazy language by partial evaluation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.258-268, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143220]
	32	Paul Kleinrubatscher , Albert Kriegshaber , Robert Zöchling , Robert Glück, Fortran program specialization, ACM SIGPLAN Notices, v.30 n.4, p.61-70, April 1995 [doi>10.1145/202176.202184]
	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	Torben Æ. Mogensen, Self-applicable online partial evaluation of the pure lambda calculus, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.39-44, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215469]
	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	Eijiro Sumii , Naoki Kobayashi, Online-and-offline partial evaluation (extended abstract): a mixed approach, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.12-21, January 22-23, 2000, Boston, Massachusetts, United States
	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	Scott Thibault , Charles Consel , Julia L. Lawall , Renaud Marlet , Gilles Muller, Static and Dynamic Program Compilation by Interpreter Specialization, Higher-Order and Symbolic Computation, v.13 n.3, p.161-178, Sept. 2000 [doi>10.1023/A:1010078412711]
	44	Peter J. Thiemann, Cogen in six lines, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.180-189, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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, ACM SIGPLAN Notices, v.14 n.2, p.46-54, February 1979 [doi>10.1145/954063.954069]
	47	Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
	48	Valentin F. Turchin, Metacomputation: Metasystem Transitions plus Supercompilation, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.481-509, February 12-16, 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).