Revisiting the Futamura Projections: A Diagrammatic Approach

• Autorzy: Williams B. M. , Perugini S.

Identyfikatory

DOI

10.20904/284015

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

compilation; compiler generation; Futamura Projections; Graal; interpretation; partial evaluation; program transformation; PyPy; Truffle

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2016
• Tom: Vol. 28, No. 4
• Strony: 15--32
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Williams B. M.

• Department of Computer Science University of Dayton 300 College Park Dayton, Ohio 45469-2160 USA

autor

Perugini S.

• Department of Computer Science University of Dayton 300 College Park Dayton, Ohio 45469-2160 USA

Bibliografia

• [1] Y. Futamura. Partial evaluation of computation process: An approach to a compilercompiler. Higher-Order and Symbolic Computation, 12(4):381-391, 1999.
• [2] Y. Futamura. Partial evaluation of computation process: An approach to a compilercompiler. Systems Computers Controls, 2(5):54-50, 1971.
• [3] A.P. Ershov. On the partial computation principle. Information Processing Letters, 6(2):38-41, 1977. DOI: 10.1016/0020-0190(77)90078-3.
• [4] N.D. Jones, C.K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.
• [5] R. Glück. 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.
• [6] N.D. Jones. An introduction to partial evaluation. ACM Computing Surveys, 28(3):480-503, 1996. DOI: 10.1145/243439.243447.
• [7] 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.
• [8] D.P. Friedman and M. Wand. Essentials of Programming Languages. MIT Press, Cambridge, MA, third edition, 2008.
• [9] 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.
• [10] 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.
• [11] 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.
• [12] C. Humer, C. Wimmer, C. Wirth, A. W Wöß , and T. Würthinger. 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. Also appears in ACM SIGPLAN Notices, Vol. 50(3):123-132, 2015.
• [13] T. Wŭrthinger, C. Wimmer, A. Wöß, 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.
• [14] PyPy Speed Center. http://speed.pypy.org. Last Accessed: March 17, 2017.
• [15] 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.
• [16] 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 (OOP-SLA), pages 821-839, New York, NY, 2015. ACM Press. Also appears in ACM SIGPLAN Notices, Vol. 50(10):821-839, 2015.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).