A practical unification of multi-stage programming and macros
Authors: 
Nicolas Stucki, 
Aggelos Biboudis, and 
Martin OderskyAuthors Info & Claims
Abstract
Program generation is indispensable. We propose a novel unification of two existing metaprogramming techniques: multi-stage programming and hygienic generative macros. The former supports runtime code generation and execution in a type-safe manner while the latter offers compile-time code generation.
In this work we draw upon a long line of research on metaprogramming, starting with Lisp, MetaML and MetaOCaml. We provide direct support for quotes, splices and top-level splices, all regulated uniformly by a level-counting Phase Consistency Principle. Our design enables the construction and combination of code values for both expressions and types. Moreover, code generation can happen either at runtime à la MetaML or at compile time, in a macro fashion, à la MacroML.
We provide an implementation of our design in Scala and we present two case studies. The first implements the Hidden Markov Model, Shonan Challenge for HPC. The second implements the staged streaming library Strymonas.
References
[1]
Baris Aktemur, Yukiyoshi Kameyama, Oleg Kiselyov, and Chung-chieh Shan. 2013. Shonan Challenge for Generative Programming: Short Position Paper. In Proc. of the ACM SIGPLAN 2013 Workshop on Partial Evaluation and Program Manipulation (PEPM '13). ACM, New York, NY, USA, 147-154.
[2]
Aggelos Biboudis, Nick Palladinos, and Yannis Smaragdakis. 2014. Clash of the Lambdas. In Proc. 9th International Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS '14). arXiv:cs.PL/1406.6631.
[3]
W. H. Burge. 1975. Stream Processing Functions. IBM J. Res. Dev. 19, 1 (Jan. 1975), 12-25.
[4]
Eugene Burmako. 2013. Scala Macros: Let Our Powers Combine!: On How Rich Syntax and Static Types Work with Metaprogramming. In Proc. of the 4th Workshop on Scala (SCALA '13). ACM, New York, NY, USA, Article 3, 10 pages.
[5]
Eugene Burmako. 2017. Unification of Compile-Time and Runtime Metaprogramming in Scala. Ph.D. Dissertation. Lausanne.
[6]
Cristiano Calcagno, Walid Taha, Liwen Huang, and Xavier Leroy. 2003. Implementing Multi-stage Languages Using ASTs, Gensym, and Reflection. In Proc. of the 2nd International Conference on Generative Programming and Component Engineering (GPCE '03). Springer-Verlag, Berlin, Heidelberg, 57-76. http://dl.acm.org/citation.cfm?id=954186.954190.
[7]
Albert Cohen, Sébastien Donadio, Maria-Jesus Garzaran, Christoph Herrmann, Oleg Kiselyov, and David Padua. 2006. In Search of a Program Generator to Implement Generic Transformations for High-performance Computing. Sci. Comput. Program. 62, 1 (Sept. 2006), 25-46.
[8]
Krzysztof Czarnecki, John T. O'Donnell, Jörg Striegnitz, and Walid Taha. 2004. DSL Implementation in MetaOCaml, Template Haskell, and C++. Springer Berlin Heidelberg, Berlin, Heidelberg, 51-72.
[9]
Krzysztof Czarnecki, Kasper Østerbye, and Markus Völter. 2002. Generative programming. In European Conference on Object-Oriented Programming. Springer, 15-29.
[10]
Rowan Davies and Frank Pfenning. 2001. A Modal Analysis of Staged Computation. J. ACM 48, 3 (May 2001), 555-604.
[11]
Matthew Flatt. 2002. Composable and Compilable Macros:: You Want It when?. In Proc. of the Seventh ACM SIGPLAN International Conference on Functional Programming (ICFP '02). ACM, New York, NY, USA, 72-83.
[12]
Steven E. Ganz, Amr Sabry, and Walid Taha. 2001. Macros As Multi-Stage Computations: Type-safe, Generative, Binding Macros in MacroML. In Proc. of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP '01). ACM, New York, NY, USA, 74-85.
[13]
Andrew Gill, John Launchbury, and Simon L. Peyton Jones. 1993. A Short Cut to Deforestation. In Proc. of the Conference on Functional Programming Languages and Computer Architecture (FPCA '93). ACM, 223-232.
[14]
J. Hughes. 1989. Why Functional Programming Matters. Comput. J. 32, 2 (April 1989), 98-107.
[15]
Simon Peyton Jones. 2016. Template Haskell, 14 years on. https://www.cl.cam.ac.uk/events/metaprog2016/Template-Haskell-Aug16.pptx.
[16]
Ulrik Jørring and William L. Scherlis. 1986. Compilers and Staging Transformations. In Proc. of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL '86). ACM, New York, NY, USA, 86-96.
[17]
Yukiyoshi Kameyama, Oleg Kiselyov, and Chung-chieh Shan. 2009. Shifting the Stage: Staging with Delimited Control. In Proc. of the 2009 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM '09). ACM, 111-120.
[18]
Yukiyoshi Kameyama, Oleg Kiselyov, and Chung-chieh Shan. 2015. Combinators for Impure Yet Hygienic Code Generation. Sci. Comput. Program. 112, P2 (Nov. 2015), 120-144.
[19]
Andrew J. Kennedy. 2004. FUNCTIONAL PEARL Pickler Combinators. J. Funct. Program. 14, 6 (Nov. 2004), 727-739.
[20]
Oleg Kiselyov. 2014. The Design and Implementation of BER MetaOCaml. In Functional and Logic Programming, Michael Codish and Eijiro Sumii (Eds.). Springer International Publishing, Cham, 86-102.
[21]
Oleg Kiselyov. 2018. Reconciling Abstraction with High Performance: A MetaOCaml approach. Foundations and Trends®in Programming Languages 5, 1 (2018), 1-101.
[22]
Oleg Kiselyov, Aggelos Biboudis, Nick Palladinos, and Yannis Smaragdakis. 2017. Stream Fusion, to Completeness. In Proc. of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL '17). ACM, 285-299.
[23]
Oleg Kiselyov and Chung-chieh Shan. 2010. The MetaOCaml files - Status report and research proposal. In ACM SIGPLAN Workshop on ML.
[24]
Fengyun Liu and Eugene Burmako. 2017. Two approaches to portable macros. (2017).
[25]
Stefan Monnier and Zhong Shao. 2003. Inlining As Staged Computation. J. Funct. Program. 13, 3 (May 2003), 647-676.
[26]
Flemming Nielson and Hanne Riis Nielson. 1992. Two-level Functional Languages. Cambridge University Press, New York, NY, USA.
[27]
Martin Odersky, Eugene Burmako, and Dmytro Petrashko. 2016. A TASTY Alternative. (2016).
[28]
Lionel Parreaux, Amir Shaikhha, and Christoph E. Koch. 2017. Quoted Staged Rewriting: A Practical Approach to Library-defined Optimizations. In Proc. of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2017). ACM, NewYork, NY, USA, 131-145.
[29]
Lionel Parreaux, Antoine Voizard, Amir Shaikhha, and Christoph E. Koch. 2017. Unifying Analytic and Statically-typed Quasiquotes. Proc. ACM Program. Lang. 2, POPL, Article 13 (Dec. 2017), 33 pages.
[30]
Simon Peyton Jones, Andrew Tolmach, and Tony Hoare. 2001. Playing by the Rules: Rewriting as a Practical Optimisation Technique in GHC. In Haskell workshop, Vol. 1. 203-233.
[31]
Tiark Rompf. 2016. Reflections on LMS: Exploring Front-end Alternatives. In Proc. of the 2016 7th ACM SIGPLAN Symposium on Scala (SCALA 2016). ACM, New York, NY, USA, 41-50.
[32]
Tiark Rompf and Martin Odersky. 2010. Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs. In Proc. of the Ninth International Conference on Generative Programming and Component Engineering (GPCE '10). ACM, New York, NY, USA, 127-136.
[33]
Denys Shabalin. 2014. Hygiene for scala. Technical Report.
[34]
Tim Sheard and Simon Peyton Jones. 2002. Template Metaprogramming for Haskell. In Proc. of the 2002 ACM SIGPLAN Workshop on Haskell (Haskell '02). ACM, New York, NY, USA, 1-16.
[35]
Aleksey Shipilev, Sergey Kuksenko, Anders Astrand, Staan Friberg, and Henrik Loef. 2007. OpenJDK Code Tools: JMH. http://openjdk.java.net/projects/code-tools/jmh/.
[36]
Yannis Smaragdakis, Aggelos Biboudis, and George Fourtounis. 2017. Structured Program Generation Techniques. In Grand Timely Topics in Software Engineering, Jácome Cunha, João P. Fernandes, Ralf Lämmel, João Saraiva, and Vadim Zaytsev (Eds.). Springer International Publishing, Cham, 154-178.
[37]
Walid Taha. 1999. Multi-Stage Programming: Its Theory and Applications. Ph.D. Dissertation. Oregon Graduate Institute of Science and Technology.
[38]
Walid Taha. 2004. A Gentle Introduction to Multi-stage Programming. In Domain-Specific Program Generation: International Seminar, Dagstuhl Castle, Germany, March 23-28, 2003. Revised Papers, Christian Lengauer, Don Batory, Charles Consel, and Martin Odersky (Eds.). Number 3016. Springer Berlin Heidelberg, 30-50.
[39]
Walid Taha and Tim Sheard. 1997. Multi-stage Programming with Explicit Annotations. In Proc. of the 1997 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation (PEPM '97). ACM, New York, NY, USA, 203-217.
[40]
The Dotty Team. 2018. Dotty Compiler: A Next Generation Compiler for Scala. https://web.archive.org/web/20180630221002/http://dotty.epfl.ch/.
[41]
The Dotty Team. 2018. Dotty Inline. https://web.archive.org/web/20171230163822/http://dotty.epfl.ch:80/docs/reference/inline.html. [Accessed: 2018-07-09].
[42]
Sam Tobin-Hochstadt, Vincent St-Amour, Ryan Culpepper, Matthew Flatt, and Matthias Felleisen. 2011. Languages As Libraries. In Proc. of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '11). ACM, New York, NY, USA, 132-141.
[43]
Laurence Tratt. 2008. Domain Specific Language Implementation via Compile-time Meta-programming. ACM Trans. Program. Lang. Syst. 30, 6, Article 31 (Oct. 2008), 40 pages.
[44]
T Veldhuizen and E Gannon. 1998. Active libraries: Rethinking the roles of compilers and libraries. In Proc. of the 1998 SIAM Workshop: Object Oriented Methods for Interoperable Scientific and Engineering Computing. 286-295.
[45]
Jeremy Yallop and Leo White. 2015. Modular macros.
Index Terms
- A practical unification of multi-stage programming and macros
Recommendations
Multi-stage programming with generative and analytical macros
GPCE 2021: Proceedings of the 20th ACM SIGPLAN International Conference on Generative Programming: Concepts and ExperiencesIn metaprogramming, code generation and code analysis are complementary. Traditionally, principled metaprogramming extensions for programming languages, like MetaML and BER MetaOCaml, offer strong foundations for code generation but lack equivalent ...
A practical unification of multi-stage programming and macros
GPCE 2018: Proceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and ExperiencesProgram generation is indispensable. We propose a novel unification of two existing metaprogramming techniques: multi-stage programming and hygienic generative macros. The former supports runtime code generation and execution in a type-safe manner while ...
Composable and compilable macros:: you want it when?
Many macro systems, especially for Lisp and Scheme, allow macro transformers to perform general computation. Moreover, the language for implementing compile-time macro transformers is usually the same as the language for implementing run-time functions. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2018
214 pages
November 2018214 pages
Copyright © 2018 ACM.
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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 April 2020
Published in SIGPLAN Volume 53, Issue 9
Check for updates
Author Tags
Qualifiers
- Article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations13Total Citations
- 329Total Downloads
- Downloads (Last 12 months)59
- Downloads (Last 6 weeks)11
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in