We investigate how to build sophisticated program generators like Spiral using modern language features.
What is it?
We reimplemented a subset of the original Spiral system using modern program language features. In the process we make heavy use of embedded DSLs in Scala and staging utilizing the Lightweight Modular Staging framework to achieve to following goals:
- Describing problem and algorithmic knowledge through multiple levels of DSLs.
- Specifying optimizations and algorithmic choices as rewrite rules on DSL programs.
- Build a infrastructure to easily abstract over recurring low-level transformations such as unrolling and scalarization; this is done by abstracting over staging decisions.
- Designing high-level data structures that can be parametrized to generate multiple low-level representations including different data layouts.
Multi-stage programming inherently fits nicely in the context of program generators. In this work we go one step further and explore the possibilities that staging done through types, as implemented in Lightweight Modular Staging, combined with modern program language constructs such as Type Parameterization and Type Classes offers. We give a teaser on some of the powerful constructs that can be build through this combination in the following sections. More details are in [1,2].
In the case of program generators its beneficial to selectively decide if code should be executed at compile time, or if it should be part of the final program. To avoid code duplication we can encode both behaviors by abstraction over the staging decision. Since LMS uses types to annotate staging, we can utilize parametric polymorphism to achieve this as depicted below:
type T can now be either
Rep[Double] (the staged type). This allows us to write code that is universal for precomputation and as part of the final program.
Different Code Styles
We observe that moving the staging annotation in the code changes the code style:
|Meta Program (Scala)||Resulting Intermediate Representation||Unparsed Result (C)|
Abstraction over Code Style
We then extend the idea of selective staging to also abstract over all these code styles.
We modify the function from above to the form:
This allows us to instantiate all of the above code styles from a single function.
Abstraction over Data Layout
We hide the type information into an abstract base class. We extend the base class with different types of instantiations of the typing such that we realize code such as:
The actual implementation is quite involved and is shown in full detail in [1,2].
Georg Ofenbeck, Tiark Rompf and Markus Püschel
Staging for Generic Programming in Space and Time
Proc. International Conference on Generative Programming: Concepts & Experiences (GPCE), pp. 15-28, 2017
Georg Ofenbeck, Tiark Rompf, Alen Stojanov, Martin Odersky and Markus Püschel
Spiral in Scala: Towards the Systematic Construction of Generators for Performance Libraries
Proc. International Conference on Generative Programming: Concepts Experiences (GPCE), pp. 125-134, 2013
Georg Ofenbeck, Tiark Rompf, Markus Püschel
RandIR: Differential Testing for Embedded Compilers
Proc. Scala Symposium, pp. 21-30, 2016
Tiark Rompf, Martin Odersky
Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs
Communications ACM 55(6): 121-130 (2012)
Markus Püschel, José M. F. Moura, Jeremy Johnson, David Padua, Manuela Veloso, Bryan Singer, Jianxin Xiong, Franz Franchetti, Aca Gacic, Yevgen Voronenko, Kang Chen, Robert W. Johnson and Nicholas Rizzolo
SPIRAL: Code Generation for DSP Transforms
Proceedings of the IEEE, special issue on “Program Generation, Optimization, and Adaptation”, Vol. 93, No. 2, pp. 232- 275, 2005
Franz Franchetti, Yevgen Voronenko and Markus Püschel
Formal Loop Merging for Signal Transforms
Proc. Programming Languages Design and Implementation (PLDI), pp. 315-326 , 2005