Revisiting the Futamura Projections: A Diagrammatic Approach

Brandon M. Williams, Saverio Perugini


The advent of language implementation tools such as PyPy and Truffle/Graal have reinvigorated and broadened interest in topics related to automatic compiler generation and optimization.  Given this broader interest, we revisit the Futamura Projections using a novel diagram scheme.   Through these diagrams we emphasize the recurring patterns in the Futamura Projections while addressing their complexity and abstract nature.  We anticipate that this approach will improve the accessibility of the Futamura Projections and help foster analysis of those new tools through the lens of partial evaluation.

Full Text:



Y. Futamura. Partial evaluation of computation process: An approach to a compiler-compiler. Higher-Order and Symbolic Computation, 12(4):381--391, 1999.

Y. Futamura. Partial evaluation of computation process: An approach to a compiler-compiler. Systems Computers Controls, 2(5):54--50, 1971.

A.P. Ershov. On the partial computation principle. Information Processing Letters, 6(2):38--41, 1977. DOI:10.1016/0020-0190(77)90078-3

N.D. Jones, C.K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.

R. Gluck. Is there a fourth Futamura projection? In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM), pages 51--60, New York, NY, USA, 2009. ACM Press. DOI:10.1145/1480945.1480954

N.D. Jones. An introduction to partial evaluation. ACM Computing Surveys, 28(3):480--503, 1996. DOI:10.1145/243439.243447

P.J. Thiemann. Cogen in six lines. In Proceedings of the First ACM SIGPLAN International Conference on Functional Programming (ICFP), pages 180--189, New York, NY, 1996. ACM Press. DOI:10.1145/232627.232647

D.P. Friedman and M. Wand. Essentials of Programming Languages. MIT Press, Cambridge, MA, third edition, 2008.

L.O. Andersen. Partial evaluation of C and automatic compiler generation. In Proceedings of the Fourth International Conference on Compiler Construction, pages 251--257, London, UK, 1992. Springer-Verlag.

A. Bondorf and O. Danvy. Automatic autoprojection of recursive equations with global variable and abstract data types. Science of Computer Programming, 16(2):151--195, 1991. DOI:10.1016/0167-6423(91)90002-F

T. Mogensen and A. Bondorf. Logimix: A self-applicable partial evaluator for Prolog. In K.-K. Lau and T.P. Clement, editors, Proceedings of 1992 International Workshop on Logic Program Synthesis and Transformation (LOPSTR), pages 214--227. Springer London, London, UK, 1993. DOI:10.1007/978-1-4471-3560-9_15

C. Humer, C. Wimmer, C. Wirth, A. Woss, and T. Wurthinger. A domain-specific language for building self-optimizing AST interpreters. In Proceedings of the International Conference on Generative Programming: Concepts and Experiences (GPCE), pages 123--132, New York, NY, 2014. ACM Press.

T. Wurthinger, C. Wimmer, A. Woss, L. Stadler, G. Duboscq, C. Humer, G. Richards, D. Simon, and M. Wolczko. One VM to rule them all. In Proceedings of the ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, pages 187--204, New York, NY, 2013. ACM Press. DOI:10.1145/2509578.2509581

PyPy Speed Center. Last Accessed: March 17, 2017.

C.F. Bolz, A. Cuni, M. Fijalkowski, and A. Rigo. Tracing the meta-level: PyPy's tracing JIT compiler. In Proceedings of the Fourth Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS), pages 18--25, New York, NY, 2009. ACM Press. DOI:/10.1145/1565824.1565827

S. Marr and S. Ducasse. Tracing vs. partial evaluation: Comparing meta-compilation approaches for self-optimizing interpreters. In Proceedings of the ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 821-839, New York, NY, 2015. ACM Press. Also appears in ,ACM SIGPLAN Notices, Vol. 50(10):821--839, 2015.



  • There are currently no refbacks.

Copyright (c) 2017 Saverio Perugini, Brandon M. Williams

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN: 1896-5334 (print), 2300-889X (online)

Open Acces CrossRef Indexed in DOAJ